【SPOJ-QTREE3】树链剖分

http://www.spoj.com/problems/QTREE3/

时间限制:2s 代码长度限制:50000B 内存限制：1536MB

【题目描述】

给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白

有两种操作：

0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）

1 v : 询问1到v的路径上的第一个黑点，若无，输出-1

总共有12组数据。

1/3 的数据, N=5000, Q=400000.

1/3 的数据, N=10000, Q=300000.

1/3 的数据，N=100000, Q=100000.

【输入格式】

单组数据的。

第一行 N and Q.表示N个点和Q个操作

下来N-1条无向边

下来 Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).

【输出格式】

遇到 "1 v"操作的时候，输出结果。

这题就是树链剖分，线段树维护当前区间最左边的黑点的编号。因为是单点修改，所以根本不用lazy，也不用记录点的颜色（看它所维护的最左边的点这个值是否为0）。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int N=;

 struct trnode{

     int lc,rc,l,r,c,d,lazy;

 }t[*N];

 struct node{

     int x,y,next;

 }a[*N];

 int n,m,tl,z,len;

 int first[N],tot[N],son[N],fa[N],dep[N],ys[N],yss[N],top[N];

 void ins(int x,int y)

 {

     len++;

     a[len].x=x;a[len].y=y;

     a[len].next=first[x];first[x]=len;

 }

 int maxx(int x,int y){return x>y ? x:y;}

 int minn(int x,int y){return x<y ? x:y;}

 int build_tree(int l,int r)

 {

     int x=++tl;

     t[x].l=l;t[x].r=r;

     t[x].c=t[x].d=t[x].lazy=;

     t[x].lc=t[x].rc=;

     if(l<r)

     {

         int mid=(l+r)>>;

         t[x].lc=build_tree(l,mid);

         t[x].rc=build_tree(mid+,r);

     }

     return x;

 }

 void change(int x,int p)

 {

     int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>;

     if(t[x].l==t[x].r)

     {

         if(t[x].d==) t[x].d=t[x].l;

         else t[x].d=;

         return;

     }

     if(p<=mid) change(lc,p);

     else change(rc,p);

     if(t[lc].d) t[x].d=t[lc].d;

     else if(t[rc].d) t[x].d=t[rc].d;

     else t[x].d=;

 }

 int query(int x,int l,int r)

 {

     if(t[x].l==l && t[x].r==r) return t[x].d;

     int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>;

     if(r<=mid) return query(lc,l,r);

     else if(l>mid) return query(rc,l,r);

     else

     {

         int t1=query(lc,l,mid);

         if(t1) return t1;

         int t2=query(rc,mid+,r);

         if(t2) return t2;

         return ;

     }

 }

 void dfs1(int x)

 {

     tot[x]=;son[x]=;

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa[x]) continue;

         fa[y]=x;

         dep[y]=dep[x]+;

         dfs1(y);

         if(tot[son[x]]<tot[y]) son[x]=y;

         tot[x]+=tot[y];

     }

 }

 void dfs2(int x,int tp)

 {

     ys[x]=++z;yss[z]=x;top[x]=tp;

     if(son[x]) dfs2(son[x],tp);

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa[x] || y==son[x]) continue;

         dfs2(y,y);

     }

 }

 int solve(int y)

 {

     int ty=top[y],ans=-;

     while(ty!=)

     {

         int t=query(,ys[ty],ys[y]);

         if(t) ans=yss[t];

         y=fa[ty];ty=top[y];

     }

     int t;

     if(y==) t=query(,,);

     else t=query(,,ys[y]);

     if(t) ans=yss[t];

     return ans;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     // freopen("me.out","w",stdout);

     scanf("%d%d",&n,&m);

     tl=;len=;z=;

     memset(first,,sizeof(first));

     for(int i=;i<n;i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         ins(x,y),ins(y,x);

     }

     build_tree(,n);

     fa[]=;dep[]=;dfs1();

     dfs2(,);

     for(int i=;i<=m;i++)

     {

         int tmp,x;

         scanf("%d%d",&tmp,&x);

         if(!tmp) change(,ys[x]);

         else

         {

             int ans=solve(x);

             if(ans) printf("%d\n",ans);

             else printf("-1\n");

         }

     }

     return ;

 }

巴特西

【SPOJ-QTREE3】树链剖分

最新文章

热门文章