1036: [ZJOI2008]树的统计Count - #include <Seter> - using namespace Orz;
1036: [ZJOI2008]树的统计Count
http://www.zybbs.org/JudgeOnline/problem.php?id=1036
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 141431 | Seter | 1036 | Accepted | 5064 kb | 1524 ms | C/Edit | 2456 B | 2011-08-12 10:20:45 |
用轻重边树链剖分写了下……由于已经写了QTREE3了所以这个很快就写出来了……而且速度也还理想……（真心懒得再写个树状数组……）囧……剖的东西看我的QTREE3代码罢……
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 | #include <stdio.h>#include <string.h>int n,m,a[2][65536],as=-1,r[30001],f[30001],s[30001],l[30001],d[30001],w[30001],de[30001],ans,t;struct edge{struct edge *next;int y;}*map[30001],st[60000],*h[30001];getint(){ int re=0,ch=getchar(),k; while((ch<'0'||ch>'9')&&ch!='-')if((ch=getchar())<=0)return -1; for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return k?-re:re;}void make(i){ struct edge *p=map[i],*q;int k,dp; for(l[i]=s[i]=1;p;p=p->next)if(p->y!=f[i]){ f[p->y]=i;de[p->y]=de[i]+1;make(p->y);s[i]+=s[p->y]; if(i&&(!h[i]||s[h[i]->y]<s[p->y]))l[i]=l[(h[i]=p)->y]+1; }for(p=map[i];q=p;p=p->next)if(p->y!=f[i]&&p!=h[i]){ for(k=p->y;l[k]!=(l[k]&-l[k]);l[k]+=l[k]&-l[k]); for(dp=0;q;q=h[q->y]){ a[0][(s[q->y]=as)+(l[q->y]=l[r[q->y]=k])+(d[q->y]=dp)]=w[q->y]; a[1][as+l[k]+dp++]=w[q->y]; }for(dp=l[k]-1;dp>0;dp--){ a[0][s[k]+dp]=a[0][s[k]+(dp<<1)]>a[0][s[k]+(dp<<1^1)]?a[0][s[k]+(dp<<1)]:a[0][s[k]+(dp<<1^1)]; a[1][s[k]+dp]=a[1][s[k]+(dp<<1)]+a[1][s[k]+(dp<<1^1)]; }as+=(l[k]<<1)-1; }}__inline void update(s,x,y){ for(x=l[x]+d[x]-1,y=l[y]+d[y]+1;x^y^1;x>>=1,y>>=1){ if(~x&1){ if(t=='S')ans+=a[1][s+(x^1)]; else if(ans<a[0][s+(x^1)])ans=a[0][s+(x^1)]; }if(y&1){ if(t=='S')ans+=a[1][s+(y^1)]; else if(ans<a[0][s+(y^1)])ans=a[0][s+(y^1)]; } }}main(){ int i,x,y,z[2],xx; (map[0]=st)->y=1; for(i=(n=getint())-1<<1;i;i-=2){ st[i^1].y=x=getint();st[i].y=y=getint(); st[i].next=map[x];st[i^1].next=map[y]; map[x]=st+i;map[y]=st+(i^1); }for(i=1;i<=n;i++)w[i]=getint(); memset(a[0],0x8F,n<<3); for(make(0),m=getint(),getchar();m--&&(t=getchar(),z[0]=getint(),z[1]=getint(),getchar());)if(t!='H'){ for(ans=t=='M'?0x8F8F8F8F:0;r[z[0]]!=r[z[1]];z[i]=f[r[z[i]]]){ xx=z[i=de[r[z[0]]]==de[r[z[1]]]?de[z[0]]>de[z[1]]?0:1:de[r[z[0]]]>de[r[z[1]]]?0:1]; update(s[xx],r[xx],xx); }update(s[z[0]],z[de[z[0]]>de[z[1]]],z[de[z[0]]<de[z[1]]]); printf("%d\n",ans); }else for(a[0][s[z[0]]+l[z[0]]+d[z[0]]]=a[1][s[z[0]]+l[z[0]]+d[z[0]]]=z[1],z[1]=l[z[0]]+d[z[0]]>>1;z[1];z[1]>>=1){ a[0][s[z[0]]+z[1]]=a[0][s[z[0]]+(z[1]<<1)]>a[0][s[z[0]]+(z[1]<<1^1)]?a[0][s[z[0]]+(z[1]<<1)]:a[0][s[z[0]]+(z[1]<<1^1)]; a[1][s[z[0]]+z[1]]=a[1][s[z[0]]+(z[1]<<1)]+a[1][s[z[0]]+(z[1]<<1^1)]; }return 0;} |
以下是以前的做法（块状树）：
用WJBZBMR神犇的块状树做的。。2K代码内牛满面。LCT等等5K代码退散啊。。。
不过时间有点悲剧。。呃。。这算掐时过么。。
块状树&题解移步：http://hi.baidu.com/wjbzbmr/blog/item/3d7741a0ade48ba0cbefd085.htm
块状数据结构秒杀一切水题！秒杀一切水题！
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 <stdio.h>#include <math.h>int n,w[5][30000],sq,t;struct edge{struct edge *next;int y;}map[30000],starr[59998],*tail[30000];make(i,d,f){ int s=1,sc;struct edge *p=map[i].next; for(w[3][i]=w[4][i]=w[0][i],w[1][i]=d,map[i].y=f;p;p=p->next)if(p->y!=f){ sc=make(p->y,d+1,i); if(s+sc-sq<=10)s+=sc,w[2][p->y]=i; }return s;}void dfs(i){ struct edge *p=map[i].next; for(;p;p=p->next)if(p->y!=map[i].y&&w[2][p->y]!=p->y){ w[3][p->y]=w[3][p->y]>w[3][i]?w[3][p->y]:w[3][i]; w[4][p->y]+=w[4][i]; w[2][p->y]=t; dfs(p->y); }}void update(i){ struct edge *p=map[i].next; w[3][i]=w[3][map[i].y]>w[0][i]&&w[2][i]!=i?w[3][map[i].y]:w[0][i]; w[4][i]=(w[2][i]!=i?w[4][map[i].y]:0)+w[0][i]; for(;p;p=p->next)if(p->y!=map[i].y&&w[2][p->y]!=p->y)update(p->y);}static __inline void get(i,j,f){ int ans=f==3?-30000:0; while(w[2][i]!=w[2][j]){ if(w[1][w[2][i]]<w[1][w[2][j]])i^=j^=i^=j; ans=f==3?ans>w[3][i]?ans:w[3][i]:ans+w[4][i]; i=map[w[2][i]].y; }while(i!=j){ if(w[1][i]<w[1][j])i^=j^=i^=j; ans=f==3?ans>w[0][i]?ans:w[0][i]:ans+w[0][i]; i=map[i].y; }printf("%d\n",f==3?ans>w[0][i]?ans:w[0][i]:ans+w[0][i]);}static __inline getint(){ int re=0,k=1;char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); for(ch=='-'?ch=getchar(),k=0:0;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return k?re:-re;}main(){ int x,y,i; char str[10]; for(sq=sqrt(n=getint()),i=0;i<n;i++)tail[w[2][i]=i]=map+i; for(i=0;i<n-1;i++){ x=getint()-1; (tail[x]=tail[x]->next=starr+(i<<1))->y=y=getint()-1; (tail[y]=tail[y]->next=starr+(i<<1)+1)->y=x; tail[x]->next=tail[y]->next=0; }for(i=0;i<n;i++)w[0][i]=getint(); make(0,0,0); for(i=0;i<n;i++)if(w[2][i]==i)dfs(t=i); for(getint();scanf("%s",str)>0;){ x=getint()-1; if(str[1]=='H')w[0][x]=getint(),update(x); else get(x,getint()-1,4-(str[1]=='M')); }return 0;} |
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 179539 | Seter | 1036 | Accepted | 2284 kb | 3460 ms | C/Edit | 2284 B | 2011-12-19 18:00:11 |
用LCT做了下，1A，不过有一个沙茶错误调了半天……还好数据没坑爹否则就……我真是太若了……
速度是剖的两倍……真是悲剧……懒得加IO优化了……
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 | #include <stdio.h>#define maxn 30000#define max(a,b) ((a)>(b)?(a):(b))struct edge{struct edge *next;int y}*map[maxn],stm[maxn<<1],*p;typedef struct _Splay{struct _Splay *c[2],*f,*p;int v,m,s}Splay,*PSplay;Splay null,st[maxn];int n,que[maxn],bq=-1,eq=1;inline PSplay updt(PSplay x){x->s=x->c[0]->s+x->c[1]->s+x->v;x->m=max(max(x->c[0]->m,x->c[1]->m),x->v);return x;}inline PSplay extr(PSplay x,_Bool c){while(x->c[c]!=&null)x=x->c[c];return x;}inline PSplay node(PSplay x,PSplay p){x->f=x->c[0]=x->c[1]=&null;return x->p=p;}inline PSplay rot(PSplay x){ PSplay fx=x->f,ffx=fx->f; _Bool c=fx->c[1]==x,fc=ffx->c[1]==fx; if(fx!=&null){ if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx; if((x->f=ffx)!=&null)ffx->c[fc]=x; updt((fx->f=x)->c[!c]=fx); }return x;}inline PSplay splay(PSplay x,PSplay p){ if(x==&null)return x;for(;x->f!=p;rot(x))if(x->f->f!=p)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x); return updt(x);}inline getint(){ int re=0,ch=getchar();_Bool k; while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1; for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return k?-re:re;}inline PSplay Access(PSplay x){ PSplay t=splay(x,&null);x->c[1]=x->c[1]->f=&null; while((x=splay(extr(x,0),&null))->p!=&null){ splay(x->p,&null)->c[1]->f=&null; t=x=(x->p->c[1]=x)->f=x->p; }return t;}main(){ int i,x,y;PSplay q,t; node(st,null.f=null.c[0]=null.c[1]=&null)->m=-30000; for(i=(n=getint())<<1;i-=2;map[y]=(map[x]=stm+i)+1){ stm[i].next=map[stm[i^1].y=x=getint()-1]; stm[i^1].next=map[stm[i].y=y=getint()-1]; }for(i=-1;++i!=n;st[i].v=st[i].m=st[i].s=getint()); while(++bq!=eq)for(p=map[que[bq]];p;p=p->next)if(st+p->y!=st[que[bq]].p)node(st+(que[eq++]=p->y),st+que[bq]); for(n=getint();n--;){ while((i=getchar())!='Q'&&i!='C'); if(i=='C')((q=splay(st+getint()-1,&null))->v)=getint(),updt(q); else{ i=getchar();Access(st+(x=getint()-1)); t=(q=splay(Access(st+(y=getint()-1)),&null))->c[0]; q->c[0]=st+x==q?&null:splay(st+x,&null); printf("%d\n",i=='M'?updt(q)->m:updt(q)->s); q->c[0]=t;updt(q); } }return 0;} |
By Seter
2013年9月22日 19:38
话说大神，这道题不可以用主席树写的么，为什么都是用了树链剖分。。？