首页 > 其他 > 详细

BZOJ3626 [LNOI2014]LCA

时间:2017-03-02 12:22:52      阅读:133      评论:0      收藏:0      [点我收藏+]

Description

给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。
有q次询问,每次询问给出l r z,求sigma_{l<=i<=r}dep[LCA(i,z)]。
(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)

Input

第一行2个整数n q。
接下来n-1行,分别表示点1到点n-1的父节点编号。
接下来q行,每行3个整数l r z。

Output

输出q行,每行表示一个询问的答案。每个答案对201314取模输出

Sample Input

5 2
0
0
1
1
1 4 3
1 4 2

Sample Output

8
5

HINT

共5组数据,n与q的规模分别为10000,20000,30000,40000,50000。

 

未解决

bzoj上WA了,和qt666拍了极限数据没WA,我还能干什么

 

  1 #include <iostream>
  2 #include <iomanip>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <cmath>
  6 #include <cstring>
  7 #include <string>
  8 #include <algorithm>
  9 #define int long long
 10 #define RG register
 11 const int N = 500000;
 12 const int mod=201314;
 13 
 14 using namespace std;
 15 
 16 int gi()
 17 {
 18   int x=0,flag=1;
 19   char ch=getchar();
 20   while(ch<0||ch>9){if(ch==-) flag=-1;ch=getchar();}
 21   while(ch>=0&&ch<=9) x=x*10+ch-0,ch=getchar();
 22   return x*flag;
 23 }
 24 
 25 int fa[N],c[N][2],lazy[N],w[N],rev[N],st[N],siz[N],f[N];
 26 long long ans[N];
 27 
 28 struct date{
 29     int r,z,i,x;
 30     bool operator < (const date a) const {
 31         return r<a.r;
 32     }
 33 }qu[N];
 34 
 35 int isroot(int x){
 36     return c[fa[x]][0]!=x && c[fa[x]][1]!=x;
 37 }
 38 
 39 void pushdown(int x){
 40     if (lazy[x]){
 41         w[c[x][0]]+=lazy[x]*siz[c[x][0]],f[c[x][0]]+=lazy[x];
 42         w[c[x][1]]+=lazy[x]*siz[c[x][1]],f[c[x][1]]+=lazy[x];
 43         lazy[c[x][0]]+=lazy[x],lazy[c[x][1]]+=lazy[x];
 44         lazy[x]=0;
 45     }
 46     if (rev[x]==0) return;
 47     rev[x]^=1,rev[c[x][0]]^=1,rev[c[x][1]]^=1;
 48     swap(c[x][0],c[x][1]);
 49     return;
 50 }
 51 
 52 void update(int x){
 53     siz[x]=siz[c[x][0]]+siz[c[x][1]]+1;
 54     w[x]=w[c[x][0]]+w[c[x][1]]+f[x];
 55     return;
 56 }
 57 
 58 void rotate(int x){
 59     int y=fa[x],z=fa[y],l,r;
 60     if (c[y][0]==x) l=0;
 61     else l=1;r=l^1;
 62     if (!isroot(y))
 63         if (c[z][0]==y) c[z][0]=x;
 64         else c[z][1]=x;
 65     fa[c[x][r]]=y,fa[y]=x,fa[x]=z;
 66     c[y][l]=c[x][r],c[x][r]=y;
 67     update(y),update(x);
 68     return;
 69 }
 70 
 71 void splay(int x){
 72     int tot=0;st[++tot]=x;
 73     for (RG int i=x; !isroot(i); i=fa[i]) st[++tot]=fa[i];
 74     for (RG int i=tot; i; --i) pushdown(st[i]);
 75     while(!isroot(x)){
 76         int y=fa[x],z=fa[y];
 77         if (!isroot(y))
 78             if (c[y][0]==x ^ c[z][0]==y) rotate(x);
 79             else rotate(y);
 80         rotate(x);
 81     }
 82     return;
 83 }
 84 
 85 void access(int x){
 86     int t=0;
 87     while(x){
 88         splay(x);
 89         c[x][1]=t;update(x);
 90         t=x,x=fa[x];
 91     }
 92 }
 93 
 94 void rever(int x){
 95     access(x),splay(x),rev[x]^=1;
 96     return;
 97 }
 98 
 99 main(){
100     freopen("lct.in","r",stdin);
101     freopen("lct.out","w",stdout);
102     int n=gi(),q=gi(),head=1;
103     siz[1]=1;
104     for (RG int i=2; i<=n; ++i) fa[i]=gi()+1,siz[i]=1;
105     for (RG int i=1; i<=q; ++i){
106         int l=gi(),r=gi()+1,z=gi()+1;
107         qu[i]=(date){l,z,i,-1};
108         qu[i+q]=(date){r,z,i,1};
109     }
110     sort(qu+1,qu+2*q+1);q*=2;
111     for (RG int i=1; i<=n; ++i){
112         rever(1),access(i),splay(i);
113         ++lazy[i],++f[i],w[i]+=siz[i];
114         while(qu[head].r<=i && head<=q){
115             int z=qu[head].z;
116             rever(1),access(z),splay(z);
117             update(z);
118             ans[qu[head].i]+=w[qu[head].z]*qu[head].x;
119             ++head;
120         }
121     }
122     q/=2;
123     for (RG int i=1; i<=q; ++i) printf("%lld\n",(ans[i]+mod)%mod);
124     return 0;
125 }

 

BZOJ3626 [LNOI2014]LCA

原文:http://www.cnblogs.com/cjk2001/p/6489844.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!