2
24
2016
0

[BZOJ2654] tree

怎么说呢……神奇的二分

每次把白色边加上一个二分的权值，再做最小生成树

如果大于need条边就说明加上的权值太小了需要增大

反之亦然(因为题目保证有解，所以必然会存在这样的一个权值)

注意排序时权值相等时白色边放在前面

?
bzoj 2654
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int V,E,need,f[100005],test=0,ne=0;
 
struct Edge{
int a,b,v,co;
friend bool operator<(Edge a,Edge b){
return a.v==b.v?a.co<b.co:a.v<b.v;
}
}e[100005];
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){
if(sa<sb)f[sb]=sa;
else f[sa]=sb;
}
 
int Check(int ans){
test=ne=0;
for(int i=1;i<=V;i++)f[i]=i;
for(int i=1;i<=E;i++){
    if(!e[i].co)e[i].v+=ans;
}
sort(e+1,e+E+1);
for(int i=1;i<=E;i++){
    if(Find(e[i].a)!=Find(e[i].b)){
        Union(Find(e[i].a),Find(e[i].b));
        test+=e[i].v;
        if(!e[i].co)ne++;
    }
}
for(int i=1;i<=E;i++){
    if(!e[i].co)e[i].v-=ans;
}
return ne>=need;
}
 
int main(){
freopen("2654.in","r",stdin);
freopen("2654.out","w",stdout);
scanf("%d %d %d",&V,&E,&need);
for(int i=1;i<=E;i++){
    scanf("%d %d %d %d",&e[i].a,&e[i].b,&e[i].v,&e[i].co);
    e[i].a++;
    e[i].b++;
}
int l=-105,r=105,ans;
while(l<=r){
    int mid=l+r>>1;
    if(Check(mid)){ans=test-need*mid;l=mid+1;}
    else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
23
2016
0

[BZOJ1305] [CQOI2009]dance跳舞

最大流

拆点，男孩和女孩各拆成2个点ix,iy,jx,jy，互相喜欢ix->jx:1 不互相喜欢iy->jy:1

然后ix->iy=k,jy->jx=k,S->ix=ans,jy->T=ans

枚举ans跑最大流，不满流答案就是ans-1

?
bzoj 1305
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
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
  
int en,n,k,level[1005],S,T,cur[1005],POINT_N,h[1005];
char s[55][55];
  
struct Edge{
int b,f,back,next;
}e[1000005];
  
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
  
int BFS(){
queue<int> Q;
Q.push(S);
memset(level,0,sizeof(level));
level[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
  
int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
  
int Dinic(){
int ans=0;
while(BFS()){
    for(int i=1;i<=POINT_N;i++)cur[i]=h[i];
    ans+=DFS(S,2100000000);
}
return ans;
}
  
int main(){
freopen("1305.in","r",stdin);
freopen("1305.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
S=4*n+1;
T=4*n+2;
POINT_N=4*n+2;
int ans=1;
while(ans<=1000){
    memset(h,0,sizeof(h));
    for(int i=1;i<=n;i++){
        AddEdge(i,i+n,k);
        AddEdge(i+3*n,i+2*n,k);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s[i][j]=='Y'){
                AddEdge(i,j+2*n,1);
            }
            else {
                AddEdge(i+n,j+3*n,1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        AddEdge(S,i,ans);
        AddEdge(i+2*n,T,ans);
    }
    int an=Dinic();
    //printf("%d\n",ans);
    if(an<ans*n){printf("%d\n",ans-1);return 0;}
    ans++;
}
return 0;
}

Category: BZOJ | Tags: OI bzoj
2
23
2016
0

[BZOJ1266] [AHOI2006]上学路线route

这题有2问

第一问SPFA

第二问先从1->n 求一遍最短路，再从n->1求一遍最短路，然后判定每条边是否可能在最短路上

即D[e[i].a]+Di[e[i].b]+e[i].t==ans

注意每条边的反向边也需要判断一下

然后跑一遍最大流就行了（最小割=最大流）

?
bzoj 1266
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
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
int h[505],n,m,en,en1,D[505],Di[505],flag[505],S,T,cur[505];
 
struct Es{
int a,b,t,c;
}E[200005];
 
struct Edge1{
int b,v,next;
}e1[300005];
 
struct Edge{
int b,f,next,back;
}e[300005];
 
void AddEdge1(int sa,int sb,int sc){
e1[++en1].b=sb;
e1[en1].v=sc;
e1[en1].next=h[sa];
h[sa]=en1;
}
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].next=h[sa];
e[en].back=en+1;
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].next=h[sa];
e[en].back=en-1;
h[sa]=en;
}
 
int Spfa(int S,int T){
queue<int> Q;
memset(D,127,sizeof(D));
memset(flag,0,sizeof(flag));
Q.push(S);
D[S]=0;
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e1[i].next){
        int v=e1[i].b;
        if(D[u]+e1[i].v<D[v]){
            D[v]=D[u]+e1[i].v;
            if(!flag[v]){
                Q.push(v);
                flag[v]=1;
            }
        }
    }
}
return D[T];
}
 
int Spfa2(int S,int T){
queue<int> Q;
memset(Di,127,sizeof(Di));
memset(flag,0,sizeof(flag));
Q.push(S);
Di[S]=0;
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e1[i].next){
        int v=e1[i].b;
        if(Di[u]+e1[i].v<Di[v]){
            Di[v]=Di[u]+e1[i].v;
            if(!flag[v]){
                Q.push(v);
                flag[v]=1;
            }
        }
    }
}
return Di[T];
}
 
int Bfs(){
queue<int> Q;
Q.push(S);
memset(flag,0,sizeof(flag));
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(flag[v] || !e[i].f)continue;
        flag[v]=flag[u]+1;
        Q.push(v);
    }
}
return flag[T];
}
 
int Dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(flag[v]==flag[u]+1 && e[i].f && (fl=Dfs(v,min(f,e[i].f)))){
        f-=fl;
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
int Dinic(){
int ans=0;
while(Bfs()){
    for(int i=1;i<=n;i++)cur[i]=h[i];
    ans+=Dfs(S,2100000000);
}
return ans;
}
 
int main(){
freopen("1266.in","r",stdin);
freopen("1266.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
    scanf("%d %d %d %d",&E[i].a,&E[i].b,&E[i].t,&E[i].c);
    AddEdge1(E[i].a,E[i].b,E[i].t);
    AddEdge1(E[i].b,E[i].a,E[i].t);
}
int ans1=Spfa(1,n),ans2=Spfa2(n,1);
memset(h,0,sizeof(h));
printf("%d\n",ans1);
for(int i=1;i<=m;i++){
    if(D[E[i].a]+Di[E[i].b]+E[i].t==ans1){AddEdge(E[i].a,E[i].b,E[i].c);}
    if(Di[E[i].a]+D[E[i].b]+E[i].t==ans1){AddEdge(E[i].b,E[i].a,E[i].c);}
}
S=1;T=n;
ans2=Dinic();
printf("%d\n",ans2);
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
22
2016
0

[BZOJ1269] [AHOI2006]文本编辑器editor

这题写了我1.5h……

以后写题目必须认真、仔细！

Pushdown居然写错了……调试了半天

所以以后必须仔细想好细节再写，这样才能节省时间。

?
bzoj 1296
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,move_to=0;
char s[2000005];
 
struct Node{
char v;
int rev,siz;
Node *ch[2],*fa;
Node(char ch,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;
 
Node::Node(char c,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
siz=1;
rev=0;
v=c;
}
 
void Node::Pushdown(){
if(rev){
    rev=0;
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}
 
void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x,Node *place){
while(x->fa!=place){
    Node *y=x->fa,*z=y->fa;
    if(z==Null || z==place)Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else {Rotate(y,1);Rotate(x,1);}
    }
}
if(place==Null)root=x;
}
 
Node *Find(Node *splay,int k){
splay->Pushdown();
if(k==splay->ch[0]->siz+1)return splay;
if(k<=splay->ch[0]->siz)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}
 
Node *Split(int pos,int tot){
Node *x=Find(root,pos),*y=Find(root,pos+tot+1);
Splay(x,Null);
Splay(y,root);
return y->ch[0];
}
 
Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(s[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}
 
void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}
 
Node *GetNull(){
Node *p=new Node('#',Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->siz=p->rev=0;
}
 
void Build_First(){
Null=GetNull();
s[1]='H';
s[2]='i';
root=Build(1,2);
}
 
void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}
 
void Delete(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}
 
void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->rev^=1;
swap(seq->ch[0],seq->ch[1]);
fat->Pushup();
fat->fa->Pushup();
}
 
char GetKey(int pos){
Node *u=Split(pos,1);
return u->v;
}
 
void GetString(int len){
char ch;
while((ch=getchar())=='\n');
s[1]=ch;
for(int i=2;i<=len;i++){s[i]=getchar();}
s[len+1]='\0';
}
 
int main(){
freopen("1269.in","r",stdin);
freopen("1269.out","w",stdout);
scanf("%d",&n);
Build_First();
for(int i=1;i<=n;i++){
    char opt[10];
    scanf("%s",opt);
    if(opt[0]=='M'){
        int k;
        scanf("%d",&k);
        move_to=k;
    }
    if(opt[0]=='I'){
        int tot;
        scanf("%d",&tot);
        GetString(tot);
        Insert(move_to,tot);
    }
    if(opt[0]=='D'){
        int tot;
        scanf("%d",&tot);
        Delete(move_to+1,tot);
    }
    if(opt[0]=='R'){
        int tot;
        scanf("%d",&tot);
        Reverse(move_to+1,tot);
    }
    if(opt[0]=='G'){
        printf("%c\n",GetKey(move_to+1));
    }
    if(opt[0]=='P')move_to--;
    if(opt[0]=='N')move_to++;
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
22
2016
0

[BZOJ3673&3674] 可持久化并查集 by zky & 可持久化并查集加强版

两个都是可持久化线段树，相当于复习一下算法。。

第一个程序我没加路径压缩，第二个加了

第二个读入的操作编号不要异或lastans……在这里卡了一下

?
bzoj 3673
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
struct SegTree{
int l,r,ls,rs,v;
}tree[2000005];
 
int root[20005],cnt,deep[200005],n,m;
 
void Build(int &rt,int l,int r){
if(!rt)rt=++cnt;
if(l==r){tree[rt].v=l;return;}
int mid=l+r>>1;
tree[rt].l=l;
tree[rt].r=r;
Build(tree[rt].ls,l,mid);
Build(tree[rt].rs,mid+1,r);
}
 
void Change(int x,int &y,int pos,int val){
y=++cnt;
tree[y].l=tree[x].l;
tree[y].r=tree[x].r;
if(tree[x].l==tree[x].r){tree[y].v=val;deep[y]=deep[x];return;}
tree[y].ls=tree[x].ls;
tree[y].rs=tree[x].rs;
int mid=tree[x].l+tree[x].r>>1;
if(pos<=mid)Change(tree[x].ls,tree[y].ls,pos,val);
if(pos>mid)Change(tree[x].rs,tree[y].rs,pos,val);
}
 
int Query(int rt,int pos){
if(tree[rt].l==tree[rt].r)return rt;
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(tree[rt].ls,pos);
if(pos>mid)return Query(tree[rt].rs,pos);
}
 
void Add(int rt,int pos){
if(tree[rt].l==tree[rt].r){deep[rt]++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Add(tree[rt].ls,pos);
if(pos>mid)Add(tree[rt].rs,pos);
}
 
int Find(int rt,int x){
int tp=Query(rt,x);
if(x==tree[tp].v)return tp;
return Find(rt,tree[tp].v);
}
 
int main(){
freopen("3673.in","r",stdin);
freopen("3673.out","w",stdout);
scanf("%d %d",&n,&m);
Build(root[0],1,n);
for(int i=1;i<=m;i++){
    int opt;
    scanf("%d",&opt);
    if(opt==1){
        int x,y,px,py;
        scanf("%d %d",&x,&y);
        root[i]=root[i-1];
        px=Find(root[i],x);py=Find(root[i],y);
        if(tree[px].v==tree[py].v)continue;
        if(deep[px]>deep[py])swap(px,py);
        Change(root[i-1],root[i],tree[px].v,tree[py].v);
        if(deep[px]==deep[py])Add(root[i],tree[py].v);
    }
    if(opt==2){
        int k;
        scanf("%d",&k);
        root[i]=root[k];
    }
    if(opt==3){
        int x,y;
        root[i]=root[i-1];
        scanf("%d %d",&x,&y);
        if(tree[Find(root[i],x)].v!=tree[Find(root[i],y)].v)puts("0");
        else puts("1");
    }
}
return 0;
}
?
bzoj 3674
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,m,cnt,lastans=0,deep[10000005],root[200005];
 
struct SegTree{
int l,r,ls,rs,v;
}tree[10000005];
 
void Build(int &rt,int l,int r){
if(!rt)rt=++cnt;
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].v=l;return;}
int mid=l+r>>1;
Build(tree[rt].ls,l,mid);
Build(tree[rt].rs,mid+1,r);
}
 
void Change(int x,int &y,int pos,int val){
y=++cnt;
tree[y].l=tree[x].l;
tree[y].r=tree[x].r;
if(tree[x].l==tree[x].r){tree[y].v=val;deep[y]=deep[x];return;}
tree[y].ls=tree[x].ls;
tree[y].rs=tree[x].rs;
int mid=tree[x].l+tree[x].r>>1;
if(pos<=mid)Change(tree[x].ls,tree[y].ls,pos,val);
if(pos>mid)Change(tree[x].rs,tree[y].rs,pos,val);
}
 
void Add(int rt,int pos){
if(tree[rt].l==tree[rt].r){deep[rt]++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Add(tree[rt].ls,pos);
if(pos>mid)Add(tree[rt].rs,pos);
}
 
int Query(int rt,int pos){
if(tree[rt].l==tree[rt].r){return rt;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(tree[rt].ls,pos);
if(pos>mid)return Query(tree[rt].rs,pos);
}
 
int Find(int rt,int x){
int p=Query(rt,x);
if(x==tree[p].v){return p;}
int tp=Find(rt,tree[p].v);
Change(rt,rt,tree[p].v,tp);
return tp;
}
 
int main(){
freopen("3674.in","r",stdin);
freopen("3674.out","w",stdout);
scanf("%d %d",&n,&m);
Build(root[0],1,n);
for(int i=1;i<=m;i++){
    int opt;
    scanf("%d",&opt);
    if(opt==1){
        int x,y,p,q;
        scanf("%d %d",&x,&y);
        x^=lastans;y^=lastans;
        root[i]=root[i-1];
        p=Find(root[i],x);
        q=Find(root[i],y);
        if(tree[p].v==tree[q].v)continue;
        if(deep[p]>deep[q])swap(p,q);
        Change(root[i-1],root[i],tree[p].v,tree[q].v);
        if(deep[p]==deep[q])Add(root[i],tree[q].v);
    }
    if(opt==2){
        int k;
        scanf("%d",&k);
        k^=lastans;
        root[i]=root[k];
    }
    if(opt==3){
        int x,y;
        scanf("%d %d",&x,&y);
        x^=lastans;y^=lastans;
        root[i]=root[i-1];
        if(tree[Find(root[i],x)].v==tree[Find(root[i],y)].v){puts("1");lastans=1;}
        else {puts("0");lastans=0;}
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
21
2016
0

[BZOJ1500] [NOI2005]维修数列

Splay模版题

调试两天总算A啦！

2016/2/21 *1

2016/3/20 *1

?
bzoj 1500
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,a[1000005],m;
 
struct Node{
int v,mx,sum,lx,rx,siz,tag,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;
 
Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=sum=mx=val;
tag=rev=0;
siz=1;
if(v>=0)lx=rx=v;
else lx=rx=0;
}
 
void Node::Pushdown(){
if(tag){
    tag=rev=0;
    if(ch[0]!=Null){ch[0]->tag=1;ch[0]->sum=ch[0]->siz*v;ch[0]->v=v;}
    if(ch[1]!=Null){ch[1]->tag=1;ch[1]->sum=ch[1]->siz*v;ch[1]->v=v;}
    if(v>=0){
        if(ch[0]!=Null){ch[0]->lx=ch[0]->mx=ch[0]->rx=v*ch[0]->siz;}
        if(ch[1]!=Null){ch[1]->lx=ch[1]->mx=ch[1]->rx=v*ch[1]->siz;}
    }
    else {
        if(ch[0]!=Null){ch[0]->mx=v;ch[0]->lx=ch[0]->rx=0;}
        if(ch[1]!=Null){ch[1]->mx=v;ch[1]->lx=ch[1]->rx=0;}
    }
}
if(rev){
    rev=0;
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
    swap(ch[0]->lx,ch[0]->rx);
    swap(ch[1]->lx,ch[1]->rx);
}
}
 
void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
sum=ch[0]->sum+ch[1]->sum+v;
mx=max(ch[0]->mx,ch[1]->mx);
mx=max(mx,ch[0]->rx+v+ch[1]->lx);
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x,Node *place){
while(x->fa!=place){
    Node *y=x->fa,*z=y->fa;
    if(z==Null || z==place)Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else {Rotate(y,0);Rotate(x,0);}
    }
}
if(place==Null)root=x;
}
 
Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}
 
Node *Split(int pos,int tot){
Node *x=Find(root,pos);
Splay(x,Null);
Node *y=Find(root,pos+tot+1);
Splay(y,root);
return y->ch[0];
}
 
Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}
 
void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}
 
Node *GetNull(){
Node *p=new Node(0,Null);
p->fa=p->ch[0]=p->ch[1]=p;
p->mx=p->v=-1000000000;
p->rev=p->tag=p->siz=p->sum=p->lx=p->rx=0;
return p;
}
 
void Build_First(){
Null=GetNull();
a[1]=-1000000000;
a[n+2]=-1000000000;
root=Build(1,n+2);
}
 
void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}
 
void Delete(int pos,int val){
Node *seq=Split(pos,val),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}
 
void MakeSame(int pos,int tot,int val){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->tag=1;
seq->sum=seq->siz*val;
seq->v=val;
if(val>=0)seq->lx=seq->rx=seq->mx=seq->siz*val;
else seq->lx=seq->rx=0,seq->mx=val;
fat->Pushup();
fat->fa->Pushup();
}
 
void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
if(!seq->tag){
    seq->rev^=1;
    swap(seq->ch[0],seq->ch[1]);
    swap(seq->lx,seq->rx);
    fat->Pushup();
    fat->fa->Pushup();
}
}
 
int GetSum(int pos,int tot){
Node *seq=Split(pos,tot);
return seq->sum;
}
 
int main(){
freopen("1500.in","r",stdin);
freopen("1500.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);
Build_First();
for(int i=1;i<=m;i++){
    char s[10];
    scanf("%s",s);
    if(s[0]=='I'){
        int pos,tot;
        scanf("%d %d",&pos,&tot);
        for(int i=1;i<=tot;i++)scanf("%d",&a[i]);
        Insert(pos,tot);
    }
    if(s[0]=='D'){
        int pos,tot;
        scanf("%d %d",&pos,&tot);
        Delete(pos,tot);
    }
    if(s[0]=='M' && s[2]=='K'){
        int pos,tot,val;
        scanf("%d %d %d",&pos,&tot,&val);
        MakeSame(pos,tot,val);
    }
    if(s[0]=='M' && s[2]=='X'){
        printf("%d\n",root->mx);
    }
    if(s[0]=='R'){
        int pos,tot;
        scanf("%d %d",&pos,&tot);
        Reverse(pos,tot);
    }
    if(s[0]=='G'){
        int pos,tot;
        scanf("%d %d",&pos,&tot);
        printf("%d\n",GetSum(pos,tot));
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
20
2016
0

[BZOJ3306] 树

无语了……

参考hzwer的题解，我自己没想出来……

具体就是先搞一遍LCA，再分三种情况判断

详见hzwer题解：传送门

判定ROOT时居然写了if(ROOT=x)简直爆炸

没救了

?
bzoj 3306
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
#include<cstdio>
#include<algorithm>
using namespace std;
  
int h[100005],en,fa[100005][18],data[100005],dfn,L[100005],R[100005],pre[100005],ROOT=1,bits[20],dep[100005],n,q;
  
struct Edge{
int b,next;
}e[200005];
  
struct SegTree{
int l,r,mn;
}tree[400005];
  
void Pushup(int root){
tree[root].mn=min(tree[root*2].mn,tree[root*2+1].mn);
}
  
void Build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(l==r){
    tree[root].mn=data[pre[l]];
    return;
}
int mid=l+r>>1;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
Pushup(root);
}
  
void Change(int root,int pos,int val){
if(tree[root].l==tree[root].r){
    tree[root].mn=val;
    return;
}
int mid=tree[root].l+tree[root].r>>1;
if(pos<=mid)Change(root*2,pos,val);
if(pos>mid)Change(root*2+1,pos,val);
Pushup(root);
}
  
int GtMn(int root,int l,int r){
if(l>r)return 2100000000;
if(tree[root].l>=l && tree[root].r<=r){
    return tree[root].mn;
}
int mid=tree[root].l+tree[root].r>>1,ans=2100000000;
if(l<=mid)ans=min(ans,GtMn(root*2,l,r));
if(r>mid)ans=min(ans,GtMn(root*2+1,l,r));
return ans;
}
  
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
  
void dfs(int u){
L[u]=++dfn;
pre[dfn]=u;
for(int i=1;i<=18;i++){
    if(bits[i]<=dep[u])fa[u][i]=fa[fa[u][i-1]][i-1];
    else break;
}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    dep[v]=dep[u]+1;
    fa[v][0]=u;
    dfs(v);
}
R[u]=dfn;
}
  
int main(){
freopen("3306.in","r",stdin);
freopen("3306.out","w",stdout);
bits[0]=1;
for(int i=1;i<=18;i++)bits[i]=bits[i-1]<<1;
scanf("%d %d",&n,&q);
//printf("%d %d\n",n,q);
for(int i=1;i<=n;i++){
    int u;
    scanf("%d %d",&u,&data[i]);
    //printf("%d %d\n",u,data[i]);
    if(u)AddEdge(u,i);
}
dfs(ROOT=1);
Build(1,1,n);
for(int i=1;i<=q;i++){
    char s[5];
    int x,y;
    scanf("%s",s);
    if(s[0]=='V'){
        scanf("%d %d",&x,&y);
        Change(1,L[x],y);
    }
    if(s[0]=='E'){
        scanf("%d",&x);
        ROOT=x;
    }
    if(s[0]=='Q'){
        scanf("%d",&x);
        if(ROOT==x){printf("%d\n",tree[1].mn);continue;}
        if(L[x]<=L[ROOT] && R[x]>=R[ROOT]){
            y=ROOT;
            int deep=dep[y]-dep[x]-1;
            for(int i=0;i<=18;i++){
                if(bits[i]&deep)y=fa[y][i];
            }
            printf("%d\n",min(GtMn(1,1,L[y]-1),GtMn(1,R[y]+1,n)));
            continue;
        }
        printf("%d\n",GtMn(1,L[x],R[x]));
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
19
2016
0

[BZOJ2836] 魔法树

因为一棵树的子树一定在dfs序上是连续的

所以直接修改就行了

?
bzoj 2836
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
struct Edge{
int b,next;
}e[1000005];
 
struct SegTree{
int l,r;
long long tag,sum;
}tree[1000005];
 
int n,q,en,cnt,top[400005],id[400005],pre[400005],dep[400005],son[400005],h[400005],siz[400005],fa[400005];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
void Pushdown(int root){
if(tree[root].tag){
    tree[root*2].tag+=tree[root].tag;
    tree[root*2].sum+=tree[root].tag*(tree[root*2].r-tree[root*2].l+1);
    tree[root*2+1].tag+=tree[root].tag;
    tree[root*2+1].sum+=tree[root].tag*(tree[root*2+1].r-tree[root*2+1].l+1);
    tree[root].tag=0;
}
}
 
void Pushup(int root){
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}
 
void Build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(l==r){
    tree[root].sum=0;
    return;
}
int mid=(l+r)/2;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
}
 
void Add(int root,int l,int r,long long v){
if(tree[root].l>=l && tree[root].r<=r){
    tree[root].tag+=v;
    tree[root].sum+=v*(tree[root].r-tree[root].l+1);
    return;
}
Pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
if(l<=mid)Add(root*2,l,r,v);
if(r>mid)Add(root*2+1,l,r,v);
Pushup(root);
}
 
long long Sum(int root,int l,int r){
if(tree[root].l>=l && tree[root].r<=r){
    return tree[root].sum;
}
Pushdown(root);
int mid=tree[root].l+tree[root].r>>1;
long long ans=0;
if(l<=mid)ans+=Sum(root*2,l,r);
if(r>mid)ans+=Sum(root*2+1,l,r);
return ans;
}
 
void dfs1(int u,int father,int deep){
fa[u]=father;
dep[u]=deep;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==father)continue;
    dfs1(v,u,deep+1);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]){
        son[u]=v;
    }
}
}
  
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++cnt;
pre[cnt]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=son[u] && v!=fa[u]){dfs2(v,v);}
}
}
 
void AddLine(int u,int v,long long val){
int f1=top[u],f2=top[v];
while(f1!=f2){
    if(dep[f1]<dep[f2]){swap(u,v);swap(f1,f2);}
    Add(1,id[f1],id[u],val);
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v])swap(u,v);
//printf("%d %d\n",id[u],id[v]);
Add(1,id[u],id[v],val);
}
 
int main(){
freopen("2836.in","r",stdin);
freopen("2836.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    AddEdge(u+1,v+1);
    AddEdge(v+1,u+1);
}
Build(1,1,n);
dfs1(1,0,1);
dfs2(1,1);
scanf("%d",&q);
while(q--){
    int u,v;
    long long val;
    char s[3];
    scanf("%s",s);
    if(s[0]=='A'){
        scanf("%d %d %lld",&u,&v,&val);
        AddLine(u+1,v+1,val);
    }
    if(s[0]=='Q'){
        scanf("%d",&u);
        //printf("IS:%d %d %d\n",id[u+1],siz[u+1],u+1);
        printf("%lld\n",Sum(1,id[u+1],id[u+1]+siz[u+1]-1));
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
19
2016
0

[BZOJ3651] 网络通信

LCT

?
bzoj 3651
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
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
 
int n,m,c,t,have[10005][105];
map<int,int> Mp[1000005];
 
struct Node{
int rev;
Node *ch[2],*fa;
Node(Node *fat);
void Pushdown();
}*root[1000005],*Null;
 
Node::Node(Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
rev=0;
}
 
Node *GetNull(){
Node *re=new Node(re);
re->rev=0;
re->ch[0]=re->fa=re->ch[1]=re;
return re;
}
 
void Node::Pushdown(){
if(rev){
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0],ch[1]);
    rev=0;
}
}
 
int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}
 
void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
}
 
void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
    Node *y=x->fa,*z=y->fa;
    if(!Notroot(y))Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else {Rotate(y,0);Rotate(x,0);}
    }
}
}
 
void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;}
}
 
void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}
 
void Link(Node *u,Node *v){
Makeroot(u);
u->fa=v;
}
 
void Cut(Node *u,Node *v){
Makeroot(u);
Access(v);
Splay(v);
if(v->ch[0]==u){v->ch[0]=Null;u->fa=Null;}
}
 
Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}
 
int GetPoint(int x,int y){
return x+(y-1)*n;
}
 
Node *ToLct(int x,int c){
return root[GetPoint(x,c)];
}
 
void Change(int x,int y,int z){
int Tok=Mp[x][y];
if(Tok==0){puts("No such cable.");return;}
if(Tok==z){puts("Already owned.");return;}
//printf("%d %d\n",have[x][z],have[y][z]);
if(have[x][z]==2 || have[y][z]==2){puts("Forbidden: monopoly.");return;}
Node *u1=ToLct(x,Tok),*u2=ToLct(x,z),*v1=ToLct(y,Tok),*v2=ToLct(y,z);
//printf("%d %d\n",Find(u2),Find(v2));
if(Find(u2)==Find(v2)){puts("Forbidden: redundant.");return;}
Cut(u1,v1);
have[x][Tok]--;
have[y][Tok]--;
have[x][z]++;
have[y][z]++;
Mp[x][y]=z;
Link(u2,v2);
puts("Sold.");
}
 
int main(){
freopen("3651.in","r",stdin);
freopen("3651.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&c,&t);
Null=GetNull();
for(int i=1;i<=n*c;i++){root[i]=new Node(Null);}
//printf("%d %d %d %d\n",Null,Null->ch[0],Null->ch[1],Null->fa);
for(int i=1;i<=m;i++){
    int s1,s2,k;
    scanf("%d %d %d",&s1,&s2,&k);
    if(s1>s2)swap(s1,s2);
    have[s1][k]++;
    have[s2][k]++;
    Mp[s1][s2]=k;
    //printf("%d %d %d | %d %d N*C:%d\n",s1,s2,k,GetPoint(s1,k),GetPoint(s2,k),n*c);
    Node *x=ToLct(s1,k),*y=ToLct(s2,k);
    Link(x,y);
}
for(int i=1;i<=t;i++){
    int s1,s2,k;
    scanf("%d %d %d",&s1,&s2,&k);
    if(s1>s2)swap(s1,s2);
    Change(s1,s2,k);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
19
2016
0

[BZOJ2002] [Hnoi2010]Bounce 弹飞绵羊

LCT直接上

记录子树的大小

?
bzoj 2002
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,m,Next[200005];
 
struct Node{
int siz,rev;
Node *ch[2],*fa;
Node(Node *fat);
void Pushup();
void Pushdown();
}*root[200005],*Null;
 
Node::Node(Node *fat){
ch[0]=ch[1]=Null;
fa=fat;
siz=1;
rev=0;
}
 
void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
}
 
void Node::Pushdown(){
if(rev){
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0],ch[1]);
    rev=0;
}
}
 
int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}
 
void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
    Node *y=x->fa,*z=y->fa;
    if(!Notroot(y)){Rotate(x,y->ch[0]==x);}
    else {
        if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else {Rotate(x,1);Rotate(x,0);}
    }
}
}
 
void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}
 
void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}
 
void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}
 
void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}
}
 
Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}
 
Node *ToLct(int x){
return root[x];
}
 
Node *GetNull(){
Node *u=new Node(Null);
u->fa=u->ch[0]=u->ch[1]=u;
u->siz=0;
u->rev=0;
return u;
}
 
int Jump(int x){
Node *u=ToLct(x);
Makeroot(ToLct(n+1));
Access(u);
Splay(u);
return u->ch[0]->siz;
}
 
void Change(int x,int y){
//Node *u=ToLct(x),*v=ToLct(Next[x]);
//printf("Tp%d\n",Next[x]);
int t=min(x+y,n+1);
//printf("Tpt%d\n",t);
Cut(ToLct(x),ToLct(Next[x]));
Link(ToLct(x),ToLct(t));
Next[x]=t;
}
 
int main(){
freopen("2002.in","r",stdin);
freopen("2002.out","w",stdout);
Null=GetNull();
scanf("%d",&n);
root[n+1]=new Node(Null);
for(int i=1;i<=n;i++){
    int tp;
    scanf("%d",&tp);
    root[i]=new Node(Null);
    Next[i]=min(n+1,tp+i);
}
for(int i=1;i<=n;i++){
    Link(ToLct(i),ToLct(Next[i]));
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
    int opt,x,y;
    scanf("%d",&opt);
    if(opt==1){scanf("%d",&x);printf("%d\n",Jump(x+1));}
    if(opt==2){scanf("%d %d",&x,&y);Change(x+1,y);}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com