1 #include<cstdio> 2 3 #include<iostream> 4 #include<algorithm> 5 #include<cstring> 6 #include<map> 7 #include<set> 8 #include<cmath> 9 #define ll int 10 #define fur(i,x,y) for(i=x;i<=y;i++) 11 #define fdr(i,x,y) for(i=x;i>=y;i--) 12 #define Fur(i,x,y) for(ll i=x;i<=y;i++) 13 #define Fdr(x,y) for(ll i=x;i>=y;i--) 14 #define forl(i,x) for(ll i=head[x],to;to=e[i].to,i;i=e[i].next) 15 #define in2(x,y) in(x);in(y) 16 #define in3(x,y,z) in2(x,y);in(z) 17 #define in4(a,b,c,d) in2(a,b);in2(c,d) 18 #define clr(x,y) memset(x,y,sizeof(x)) 19 #define cpy(x,y) memcpy(x,y,sizeof(x)) 20 21 using namespace std; 22 /*---------------------------------------*/ 23 namespace fib{char b[300000]= {},*f=b;} 24 #define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1)) 25 inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;} 26 namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;} 27 #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0) 28 #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0) 29 struct foce{~foce(){pob;fflush(stdout);}} _foce; 30 namespace ib{char b[100];} 31 inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);} 32 inline void outn(ll x){out(x);pc(' ');} 33 inline void swap(ll &x,ll &y){ll t=x;x=y;y=t;} 34 inline ll jdz(ll x){return x>0?x:-x;} 35 inline ll max(ll x,ll y){return x>y?x:y;} 36 inline ll min(ll x,ll y){return x<y?x:y;} 37 /*------------------------------------------------------------------------------------------------*/ 38 39 /*------------------------------------------------------------------------------------------------*/ 40 #define N 300010 41 #define lc c[x][0] 42 #define rc c[x][1] 43 ll c[N][2],f[N],s[N],v[N]; 44 bool r[N]; 45 inline bool g(ll x){return c[f[x]][1]==x;} 46 inline bool irt(ll x){return c[f[x]][0]!=x&&c[f[x]][1]!=x;} 47 inline void re(ll x){swap(lc,rc);r[x]^=1;} 48 inline void pu(ll x){s[x]=v[x]^s[lc]^s[rc];} 49 inline void pd(ll x){if(r[x]){if(lc)re(lc);if(rc)re(rc);r[x]=0;}} 50 inline void pr(ll x){if(!irt(x))pr(f[x]);pd(x);} 51 inline void turn(ll x){ 52 ll y=f[x],z=f[y],l=g(x),r=l^1; 53 if(!irt(y))c[z][g(y)]=x; 54 f[x]=z;f[y]=x;if(c[x][r])f[c[x][r]]=y; 55 c[y][l]=c[x][r];c[x][r]=y; 56 pu(y); 57 } 58 inline void splay(ll x){ 59 pr(x); 60 while(!irt(x)){ 61 if(!irt(f[x]))turn((g(x)^g(f[x]))?f[x]:x); 62 turn(x); 63 } 64 pu(x); 65 } 66 inline void access(ll x){for(ll t=0;x;t=x,x=f[x]){splay(x);rc=t;pu(x);}} 67 inline void mrt(ll x){access(x);splay(x);re(x);} 68 inline void sl(ll x,ll y){mrt(x);access(y);splay(y);} 69 inline void cut(ll x,ll y){sl(x,y);c[y][0]=f[x]=0;} 70 inline void link(ll x,ll y){mrt(x);f[x]=y;} 71 inline ll find(ll x){access(x);splay(x);while(c[x][0])x=c[x][0];return x;} 72 int main(){ 73 ll n,m,p,x,y; 74 in2(n,m); 75 Fur(i,1,n){in(v[i]);s[i]=v[i];} 76 while(m--){ 77 in3(p,x,y); 78 if(p==0){sl(x,y);outn(s[y]);} 79 if(p==1){if(find(x)!=find(y))link(x,y);} 80 if(p==2){if(find(x)==find(y))cut(x,y);} 81 if(p==3){access(x);splay(x);v[x]=y;pu(x);} 82 } 83 }
P1501 [国家集训队]Tree II
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<cmath> 8 #define ll long long 9 #define fur(i,x,y) for(i=x;i<=y;i++) 10 #define fdr(i,x,y) for(i=x;i>=y;i--) 11 #define Fur(i,x,y) for(ll i=x;i<=y;i++) 12 #define Fdr(x,y) for(ll i=x;i>=y;i--) 13 #define forl(i,x) for(ll i=head[x],to;to=e[i].to,i;i=e[i].next) 14 #define in2(x,y) in(x);in(y) 15 #define in3(x,y,z) in2(x,y);in(z) 16 #define in4(a,b,c,d) in2(a,b);in2(c,d) 17 #define clr(x,y) memset(x,y,sizeof(x)) 18 #define cpy(x,y) memcpy(x,y,sizeof(x)) 19 20 using namespace std; 21 /*---------------------------------------*/ 22 namespace fib{char b[300000]= {},*f=b;} 23 #define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1)) 24 inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;} 25 namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;} 26 #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0) 27 #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0) 28 struct foce{~foce(){pob;fflush(stdout);}} _foce; 29 namespace ib{char b[100];} 30 inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);} 31 inline void outn(ll x){out(x);pc(' ');} 32 inline void swap(ll &x,ll &y){ll t=x;x=y;y=t;} 33 inline ll jdz(ll x){return x>0?x:-x;} 34 inline ll max(ll x,ll y){return x>y?x:y;} 35 inline ll min(ll x,ll y){return x<y?x:y;} 36 /*------------------------------------------------------------------------------------------------*/ 37 38 /*------------------------------------------------------------------------------------------------*/ 39 #define N 100009 40 #define P 51061 41 #define lc c[x][0] 42 #define rc c[x][1] 43 #define mul(x) x*=c;x%=P 44 #define add(x,c) x+=c;x%=P 45 ll c[N][2],f[N],s[N],v[N],lm[N],la[N],sz[N]; 46 bool r[N]; 47 inline bool g(ll x){return c[f[x]][1]==x;} 48 inline bool irt(ll x){return c[f[x]][0]!=x&&c[f[x]][1]!=x;} 49 inline void re(ll x){swap(lc,rc);r[x]^=1;} 50 inline void pu(ll x){ 51 s[x]=(v[x]+s[lc]+s[rc])%P; 52 sz[x]=sz[lc]+sz[rc]+1; 53 } 54 inline void pm(ll x,ll c){mul(s[x]);mul(v[x]);mul(lm[x]);mul(la[x]);} 55 inline void pa(ll x,ll c){add(s[x],c*sz[x]);add(v[x],c);add(la[x],c);} 56 inline void pd(ll x){ 57 if(lm[x]!=1){pm(lc,lm[x]);pm(rc,lm[x]);lm[x]=1;} 58 if(la[x]){pa(lc,la[x]);pa(rc,la[x]);la[x]=0;} 59 if(r[x]){if(lc)re(lc);if(rc)re(rc);r[x]=0;} 60 } 61 inline void pr(ll x){if(!irt(x))pr(f[x]);pd(x);} 62 inline void turn(ll x){ 63 ll y=f[x],z=f[y],l=g(x),r=l^1; 64 if(!irt(y))c[z][g(y)]=x; 65 f[x]=z;f[y]=x;if(c[x][r])f[c[x][r]]=y; 66 c[y][l]=c[x][r];c[x][r]=y; 67 pu(y); 68 } 69 inline void splay(ll x){ 70 pr(x); 71 while(!irt(x)){ 72 if(!irt(f[x]))turn((g(x)^g(f[x]))?f[x]:x); 73 turn(x); 74 } 75 pu(x); 76 } 77 inline void access(ll x){for(ll t=0;x;t=x,x=f[x]){splay(x);rc=t;pu(x);}} 78 inline void mrt(ll x){access(x);splay(x);re(x);} 79 inline void sl(ll x,ll y){mrt(x);access(y);splay(y);} 80 inline void cut(ll x,ll y){sl(x,y);c[y][0]=f[x]=0;} 81 inline void link(ll x,ll y){mrt(x);f[x]=y;} 82 int main(){ 83 ll n,m,x,y,c; 84 in2(n,m); 85 Fur(i,1,n)v[i]=sz[i]=lm[i]=1; 86 Fur(i,1,n-1){in2(x,y);link(x,y);} 87 char u[2]; 88 while(m--){ 89 scanf("%s",u);in2(x,y); 90 if(u[0]=='+'){in(c);sl(x,y);pa(y,c);} 91 if(u[0]=='-'){cut(x,y);in2(x,y);link(x,y);} 92 if(u[0]=='*'){in(c);sl(x,y);pm(y,c);} 93 if(u[0]=='/'){sl(x,y);outn(s[y]);} 94 } 95 }
P3203 [HNOI2010]弹飞绵羊
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<cmath> 8 #define ll long long 9 #define fur(i,x,y) for(i=x;i<=y;i++) 10 #define fdr(i,x,y) for(i=x;i>=y;i--) 11 #define Fur(i,x,y) for(ll i=x;i<=y;i++) 12 #define Fdr(x,y) for(ll i=x;i>=y;i--) 13 #define forl(i,x) for(ll i=head[x],to;to=e[i].to,i;i=e[i].next) 14 #define in2(x,y) in(x);in(y) 15 #define in3(x,y,z) in2(x,y);in(z) 16 #define in4(a,b,c,d) in2(a,b);in2(c,d) 17 #define clr(x,y) memset(x,y,sizeof(x)) 18 #define cpy(x,y) memcpy(x,y,sizeof(x)) 19 20 using namespace std; 21 /*---------------------------------------*/ 22 namespace fib{char b[300000]= {},*f=b;} 23 #define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1)) 24 inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;} 25 namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;} 26 #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0) 27 #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0) 28 struct foce{~foce(){pob;fflush(stdout);}} _foce; 29 namespace ib{char b[100];} 30 inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);} 31 inline void outn(ll x){out(x);pc(' ');} 32 inline void swap(ll &x,ll &y){ll t=x;x=y;y=t;} 33 inline ll jdz(ll x){return x>0?x:-x;} 34 inline ll max(ll x,ll y){return x>y?x:y;} 35 inline ll min(ll x,ll y){return x<y?x:y;} 36 /*------------------------------------------------------------------------------------------------*/ 37 38 /*------------------------------------------------------------------------------------------------*/ 39 #define N 200100 40 #define lc c[x][0] 41 #define rc c[x][1] 42 ll c[N][2],f[N],s[N],v[N],l[N]; 43 bool r[N]; 44 inline bool g(ll x){return c[f[x]][1]==x;} 45 inline bool irt(ll x){return c[f[x]][0]!=x&&c[f[x]][1]!=x;} 46 inline void re(ll x){swap(lc,rc);r[x]^=1;} 47 inline void pu(ll x){s[x]=v[x]+s[lc]+s[rc];} 48 inline void pd(ll x){if(r[x]){if(lc)re(lc);if(rc)re(rc);r[x]=0;}} 49 inline void pr(ll x){if(!irt(x))pr(f[x]);pd(x);} 50 inline void turn(ll x){ 51 ll y=f[x],z=f[y],l=g(x),r=l^1; 52 if(!irt(y))c[z][g(y)]=x; 53 f[x]=z;f[y]=x;if(c[x][r])f[c[x][r]]=y; 54 c[y][l]=c[x][r];c[x][r]=y; 55 pu(y); 56 } 57 inline void splay(ll x){ 58 pr(x); 59 while(!irt(x)){ 60 if(!irt(f[x]))turn((g(x)^g(f[x]))?f[x]:x); 61 turn(x); 62 } 63 pu(x); 64 } 65 inline void access(ll x){for(ll t=0;x;t=x,x=f[x]){splay(x);rc=t;pu(x);}} 66 inline void mrt(ll x){access(x);splay(x);re(x);} 67 inline void sl(ll x,ll y){mrt(x);access(y);splay(y);} 68 inline void cut(ll x,ll y){sl(x,y);c[y][0]=f[x]=0;} 69 inline void link(ll x,ll y){mrt(x);f[x]=y;} 70 int main(){ 71 ll n,m,p,x,c; 72 in(n); 73 Fur(i,1,n){ 74 v[i]=s[i]=1; 75 in(x);x+=i;if(x>n)x=n+1; 76 link(i,x);l[i]=x; 77 } 78 in(m); 79 while(m--){ 80 in2(p,x);x++; 81 if(p==1){sl(x,n+1);outn(s[n+1]);} 82 else{in(c);cut(x,l[x]);c+=x;if(c>n)c=n+1;link(x,c);l[x]=c;} 83 } 84 }