latex預處理

\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2017年4月27日 星期四

[ uvaLive 5031 ] Graph and Queries

題目:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=33&problem=3032

解法:
這題很明顯是名次樹的題目。把所有操作存起來,然後再到著做回來,就可以把刪邊變成增邊。用並查集維護那些點連通,用Treap紀錄那些點的權重,當增加邊的操作造成兩個集合要合併時,使用啟發式合併,總複雜度大約為$\ord{n log n log n}$

我的code中沒有用到任何旋轉的操作,全部都用split和merge完成,證明了只需要會split和merge一樣是可以拿來寫名次樹的

code:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
#define MAXN 100005
#define MAXM 1000005
struct node{
    node *l,*r;
    int key;
    unsigned s;
    node(int k):l(0),r(0),key(k),s(1){}
    void up(){
        s=1;
        if(l)s+=l->s;
        if(r)s+=r->s;
    }
};
inline unsigned ran(){
    static unsigned x=time(0);
    return x=x*0xdefaced+1;
}
inline unsigned size(node *o){
    return o?o->s:0;
}
node *merge(node *a,node *b){
    if(!a||!b)return a?a:b;
    if(ran()%(a->s+b->s)<a->s){
        a->r=merge(a->r,b);
        a->up();
        return a;
    }else{
        b->l=merge(a,b->l);
        b->up();
        return b;
    }
}
void split(node *o,node *&a,node *&b,int k){
    if(!o)a=b=0;
    else{
        if(o->key<k){
            a=o;
            split(o->r,a->r,b,k);
        }else{
            b=o;
            split(o->l,a,b->l,k);
        }
        o->up();
    }
}
void insert(node *&o,int k){
    node *a,*b;
    split(o,a,b,k);
    o=merge(a,merge(new node(k),b));
}
void split2(node *o,node *&a,node *&b,unsigned k){
    if(!o)a=b=0;
    else{
        if(k<=size(o->l)){
            b=o;
            split2(o->l,a,b->l,k);
        }else{
            a=o;
            split2(o->r,a->r,b,k-size(o->l)-1);
        }
        o->up();
    }
}
bool erase(node *&o,int k){
    node *a,*b,*c;
    split(o,a,b,k);
    if(!b)return 0;
    split2(b,b,c,1);
    if(b->key==k){
        delete b;
        return o=merge(a,c),1;
    }
    return o=merge(a,merge(b,c)),0;
}
inline int kth(node *&o,int k){
    if((int)size(o)<k||k<1)return 0;
    //注意這裡他會給你不合法的測資,被坑很久
    node *a,*b,*c;
    split2(o,a,c,size(o)-k);
    split2(c,b,c,1);
    o=merge(a,merge(b,c));
    return b->key;
}
struct edge{
    int u,v,use;
    edge():use(0){}
}E[MAXM];
struct XDD{
    char c;
    int p,w;
}g;
vector<XDD> P;
int n,m,t;
int st[MAXN];
int s[MAXN];
int find(int x){
    return st[x]==x?x:st[x]=find(st[x]);
}
node *sa[MAXN];
void dfs(node *&o,node *&x){
    if(!o)return;
    insert(x,o->key);
    dfs(o->l,x);
    dfs(o->r,x);
    delete o;
    o=0;
}
node *strong_merge(node *&a,node *&b){
    if(size(a)<size(b))swap(a,b);
    dfs(b,a);
    return a;
}
int main(){
    int _=0;
    while(scanf("%d%d",&n,&m),n||m){
        for(int i=1;i<=n;++i){
            scanf("%d",&s[i]);
            st[i]=i;
        }
        for(int i=1;i<=m;++i){
            scanf("%d%d",&E[i].u,&E[i].v);
            E[i].use=0;
        }
        P.clear();
        for(char c[10];scanf("%s",c),c[0]!='E';){
            g.c=c[0];
            if(c[0]=='D'){
                scanf("%d",&g.p);
                E[g.p].use=1;
            }else{
                scanf("%d%d",&g.p,&g.w);
                if(c[0]=='C'){
                    swap(s[g.p],g.w);
                }
            }
            P.push_back(g);
        }
        for(int i=1;i<=n;++i){
            sa[i]=new node(s[i]);
        }
        for(int i=1;i<=m;++i){
            int u=find(E[i].u),v=find(E[i].v);
            if(!E[i].use&&u!=v){
                st[u]=v;
                sa[v]=strong_merge(sa[v],sa[u]);
            }
        }
        vector<int> ans;
        for(int i=(int)P.size()-1;i>=0;--i){
            if(P[i].c=='D'){
                int u=find(E[P[i].p].u),v=find(E[P[i].p].v);
                if(u!=v){
                    st[u]=v;
                    sa[v]=strong_merge(sa[v],sa[u]);
                }
            }else if(P[i].c=='Q'){
                ans.push_back(kth(sa[find(P[i].p)],P[i].w));
            }else{
                int p=find(P[i].p);
                erase(sa[p],s[P[i].p]);
                insert(sa[p],P[i].w);
                s[P[i].p]=P[i].w;
            }
        }
        double V=(double)ans.size();
        long long tot=0;
        for(auto i=ans.rbegin();i!=ans.rend();++i)tot+=*i;
        printf("Case %d: %.6lf\n",++_,tot/V);
    }
    return 0;
}

沒有留言:

張貼留言