2798. Query on a tree again! - #include <Seter> - using namespace Orz;
2798. Query on a tree again!
http://www.spoj.pl/problems/QTREE3/
| ID | DATE | USER | PROBLEM | RESULT | TIME | MEM | LANG |
|---|---|---|---|---|---|---|---|
| 5491666 | 2011-08-10 05:31:14 | Seter | Query on a tree again! |
100 edit run |
5.44 | 10M |
C |
| ID | DATE | USER | PROBLEM | RESULT | TIME | MEM | LANG |
|---|---|---|---|---|---|---|---|
| 5488548 | 2011-08-09 15:21:47 | Seter | Query on a tree again! |
100 edit run |
6.16 | 11M |
C |
OrzNOI的神犇们……原来7k+是GYZ大神 - - 我果断被神犇们华丽BS了……RP掉光了啊……
在被Tim大神（Orz！！）虐了以后我下定必死的决心去写了轻重边树链剖分。一开始想写QTREE结果边权把我弄得晕头转向（我果然是苣蒻），所以只能去写写QTREE3……QTREE3由于有一个点是定点，所以不用LCA了，代码奇短无比，比块状树还短啊……
由于剖的题解太多了……我就说几个trick罢……
1.所有的线段树（或者其他什么东西）保存在一个数组里，给每个点记录一个数据结构的起始位置就可以了。
2.DFS只需要一遍就可以了……第一部分求LCA||找重链，第二部分对轻链边的孩子们循环构链
3.建超级根
4.变量名尽量定义得规则一点……避免2掉
5.不能1Y就对拍去！！！线段树那个我没对拍调了六小时才发现BUG（对某个点下的每条轻链都要把初始位置调零……我画的树是颗二叉树于是我就二叉了）。堆那个我没对拍又调了一晚上（8个0……昨天晚上果然脑子进浆糊了），今天早上和线段树那个拍了拍半小时就找到问题了（删点的时候要更新a与d我只更新了a……）
就这样罢……贴我的2X代码……线段树的那个加了getint只有35行……堆的45行，主要是sink与float太长了唉。我看了看最快的代码5.05s……看来我的剖还是挺快的！
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 | #include <stdio.h>int n,m,a[262144],as=0,r[100001],f[100001],s[100001],l[100001],d[100001],pos[262144];struct edge{struct edge *next;int y;}*map[100001],st[200000],*h[100001];getint(){ int re=0,ch=getchar(); while(ch<'0'||ch>'9')if((ch=getchar())<=0)return -1; for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return 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;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,as--;q;q=h[q->y])pos[(s[q->y]=as)+(l[q->y]=l[r[q->y]=k])+(d[q->y]=dp++)]=q->y; as+=l[k]<<1; }}main(){ int i,x,y; (map[0]=st)->y=1;n=getint();m=getint(); for(i=n-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(make(0);m--&&(i=getint(),x=getint());)if(i){ for(i=-1;x;x=f[r[x]])if(a[s[x]+1]){ for(y=1;y<l[x];y=a[s[x]+(y<<1)]?y<<1:y<<1^1); if(y<=l[x]+d[x])i=pos[s[x]+y]; }printf("%d\n",i); }else{ i=a[s[x]+l[x]+d[x]]?-1:1; for(y=l[x]+d[x];y;y>>=1)a[s[x]+y]+=i; }return 0;} |
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 | #include <stdio.h>int n,m,a[100000],as=-1,r[100001],f[100001],s[100001],l[100001],d[100001],o[100001],de[100001];struct edge{struct edge *next;int y;}*map[100001],st[200000],*h[100001];getint(){ int re=0,ch=getchar(); while(ch<'0'||ch>'9')if((ch=getchar())<=0)return -1; for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return re;}void make(i){ struct edge *p=map[i],*q; 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]){ s[p->y]=as;as+=l[p->y]; for(l[p->y]=0;q;q=h[q->y])s[q->y]=s[r[q->y]=p->y]; }}main(){ int i,x,y,t1,t2,j; (map[0]=st)->y=1;n=getint();m=getint(); for(i=n-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(make(0);m--&&(i=getint(),x=getint());)if(i){ for(i=-1;x;x=f[r[x]])if(l[r[x]]&&de[a[s[x]+1]]<=de[x])i=a[s[x]+1]; printf("%d\n",i); }else if(o[x]){ for(i=d[a[s[x]+d[x]]=a[s[x]+l[r[x]]--]]=d[x];i<<1<=l[r[x]];i=j){ j=i<<1==l[r[x]]?i<<1:de[a[s[x]+(i<<1)]]<de[a[s[x]+(i<<1^1)]]?i<<1:i<<1^1; if(de[a[s[x]+j]]>de[a[s[x]+i]])break; y=a[t1=s[x]+i];a[t1]=a[t2=s[x]+j];a[t2]=y; y=d[t1=a[t1]];d[t1]=d[t2=a[t2]];d[t2]=y; }for(;i!=1&&(de[a[s[x]+(i>>1)]]>de[a[s[x]+i]]);i>>=1){ y=a[t1=s[x]+i];a[t1]=a[t2=s[x]+(i>>1)];a[t2]=y; y=d[t1=a[t1]];d[t1]=d[t2=a[t2]];d[t2]=y; }o[x]=0; }else{ a[++l[r[x]]+s[x]]=x; for(i=d[x]=l[r[x]];i!=1&&de[a[s[x]+(i>>1)]]>de[a[s[x]+i]];i>>=1){ y=a[t1=s[x]+i];a[t1]=a[t2=s[x]+(i>>1)];a[t2]=y; y=d[t1=a[t1]];d[t1]=d[t2=a[t2]];d[t2]=y; }o[x]=1; }return 0;} |
By Seter
评论 (0)