【bzoj 3786】星系探索-布布扣-bubuko.com

物理学家小C的研究正遇到某个瓶颈。

他正在研究的是一个星系，这个星系中有n个星球，其中有一个主星球(方便起见我们默认其为1号星球)，其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。

我们定义依赖关系如下：若星球a的依赖星球是b，则有星球a依赖星球b。此外，依赖关系具有传递性，即若星球a依赖星球b，星球b依赖星球c，则有星球a依赖星球c。

对于这个神秘的星系中，小C初步探究了它的性质，发现星球之间的依赖关系是无环的。并且从星球a出发只能直接到达它的依赖星球b。

每个星球i都有一个能量系数wi。小C想进行若干次实验，第i次实验，他将从飞船上向星球di发射一个初始能量为0的能量收集器，能量收集器会从星球di开始前往主星球，并收集沿途每个星球的部分能量，收集能量的多少等于这个星球的能量系数。

但是星系的构成并不是一成不变的，某些时刻，星系可能由于某些复杂的原因发生变化。

有些时刻，某个星球能量激发，将使得所有依赖于它的星球以及他自己的能量系数均增加一个定值。还有可能在某些时刻，某个星球的依赖星球会发生变化，但变化后依然满足依赖关系是无环的。

现在小C已经测定了时刻0时每个星球的能量系数，以及每个星球(除了主星球之外)的依赖星球。接下来的m个时刻，每个时刻都会发生一些事件。其中小C可能会进行若干次实验，对于他的每一次实验，请你告诉他这一次实验能量收集器的最终能量是多少。

n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。注意w_i>=0。

纪念一下一道调了两天发现自己忘开long long的题>_<

直接查找前驱后继【Time:25484 ms】

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 using namespace std;
  5 const int inf=0x3f3f3f3f;
  6 const int N=100010;
  7 struct node{int ch[2],size,fa,t,num;long long v,sum,tag;}tr[N<<1];
  8 struct edge{int next,to;}e[N];
  9 int n,m,f,root,cnt;
 10 int head[N],q[N<<1],s[N];
 11 int read()
 12 {
 13     int x=0,f=1;char c=getchar();
 14     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
 15     while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
 16     return x*f;
 17 }
 18 void insert(int a,int b){cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt;}
 19 void dfs(int x)
 20 {
 21     q[++cnt]=x+1;
 22     for(int i=head[x];i;i=e[i].next)dfs(e[i].to);
 23     q[++cnt]=x+n+1;
 24 }
 25 void pushup(int x)
 26 {
 27     int l=tr[x].ch[0],r=tr[x].ch[1];
 28     tr[x].size=tr[l].size+tr[r].size+1;
 29     tr[x].num=tr[l].num+tr[r].num+tr[x].t;
 30     tr[x].sum=tr[l].sum+tr[r].sum+tr[x].v;
 31 }
 32 void pushdown(int x)
 33 {
 34     int l=tr[x].ch[0],r=tr[x].ch[1];long long tag=tr[x].tag;
 35     if(l)tr[l].tag+=tag,tr[l].sum+=tag*tr[l].num,tr[l].v+=tag*tr[l].t;
 36     if(r)tr[r].tag+=tag,tr[r].sum+=tag*tr[r].num,tr[r].v+=tag*tr[r].t;
 37     tr[x].tag=0;
 38 }
 39 void rotate(int x,int& k)
 40 {
 41     int y=tr[x].fa,z=tr[y].fa,l,r;
 42     if(tr[y].ch[0]==x)l=0;else l=1;r=l^1;
 43     if(y==k)k=x;
 44     else{if(tr[z].ch[0]==y)tr[z].ch[0]=x;else tr[z].ch[1]=x;}
 45     tr[x].fa=z;tr[y].fa=x;tr[tr[x].ch[r]].fa=y;
 46     tr[y].ch[l]=tr[x].ch[r];tr[x].ch[r]=y;
 47     pushup(y);pushup(x);
 48 }
 49 void splay(int x,int& k)
 50 {
 51     int top=0;s[++top]=x;
 52     for(int i=x;tr[i].fa;i=tr[i].fa)s[++top]=tr[i].fa;
 53     for(int i=top;i;i--)if(tr[s[i]].tag)pushdown(s[i]);
 54     while(x!=k)
 55     {
 56         int y=tr[x].fa,z=tr[y].fa;
 57         if(y!=k)
 58         {
 59             if((tr[y].ch[0]==x)^(tr[z].ch[0]==y))rotate(x,k);
 60             else rotate(y,k);
 61         }
 62         rotate(x,k);
 63     }
 64 }
 65 int fmin(int x){while(tr[x].ch[0])x=tr[x].ch[0];return x;}
 66 int fmax(int x){while(tr[x].ch[1])x=tr[x].ch[1];return x;}
 67 void split(int l,int r)
 68 {
 69     splay(l,root);int x=fmax(tr[l].ch[0]);
 70     splay(r,root);int y=fmin(tr[r].ch[1]);
 71     splay(x,root);splay(y,tr[x].ch[1]);
 72 }
 73 void build(int l,int r,int last)
 74 {
 75     if(l>r)return;
 76     int mid=(l+r)>>1;
 77     tr[q[mid]].fa=q[last];
 78     tr[q[last]].ch[mid>last]=q[mid];
 79     build(l,mid-1,mid);build(mid+1,r,mid);
 80     pushup(q[mid]);
 81 }
 82 void print(int x)
 83 {
 84     printf("[%d] [fa]%d [v]%lld [sum]%lld [t]%d [num]%d\n",x,tr[x].fa,tr[x].v,tr[x].sum,tr[x].t,tr[x].num);
 85     int l=tr[x].ch[0],r=tr[x].ch[1];
 86     if(l)print(l);if(r)print(r);
 87 }
 88 void query()
 89 {
 90     int x=read();
 91     splay(x+1,root);
 92     printf("%lld\n",tr[tr[x+1].ch[0]].sum+tr[x+1].v);
 93 }
 94 void change()
 95 {
 96     int x=read(),y=read();
 97     split(x+1,x+n+1);
 98     int yi=tr[root].ch[1],xi=tr[yi].ch[0];
 99     tr[yi].ch[0]=0;pushup(yi);pushup(root);
100     splay(y+1,root);
101     int u=fmin(tr[y+1].ch[1]);
102     splay(u,tr[y+1].ch[1]);
103     tr[xi].fa=u;
104     tr[u].ch[0]=xi;
105     pushup(u);pushup(root);
106 }
107 void add()
108 {
109     int x=read();long long tag=read();
110     split(x+1,x+n+1);
111     int yi=tr[root].ch[1],xi=tr[yi].ch[0];
112     tr[xi].tag+=tag;tr[xi].sum+=tag*tr[xi].num;tr[xi].v+=tag*tr[xi].t;
113     pushup(yi);pushup(root);
114 }
115 int main()
116 {
117     char str[1];
118     n=read();
119     for(int i=2;i<=n;i++)f=read(),insert(f,i);
120     for(int i=1;i<=n;i++)f=read(),tr[i+1].v=f,tr[i+1].t=1,tr[i+n+1].v=-f,tr[i+n+1].t=-1;
121     cnt=1;dfs(1);root=q[n+1];
122     q[1]=1;q[2*n+2]=2*n+2;
123     build(1,2*n+2,0);
124     m=read();
125     while(m--)
126     {
127         scanf("%s",str);
128         if(str[0]==‘Q‘)query();
129         if(str[0]==‘C‘)change();
130         if(str[0]==‘F‘)add();
131     }
132     return 0;
133 }

View Code

分裂合并【Time:19964 ms】

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 using namespace std;
  5 const int N=100010;
  6 struct node{int ch[2],fa,t,num;long long v,sum,tag;}tr[N<<1];
  7 struct edge{int next,to;}e[N];
  8 int n,m,f,root,cnt;
  9 int head[N],q[N<<1],s[N<<1];
 10 int read()
 11 {
 12     int x=0,f=1;char c=getchar();
 13     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
 14     while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
 15     return x*f;
 16 }
 17 void insert(int a,int b){cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt;}
 18 void dfs(int x)
 19 {
 20     q[++cnt]=x+1;
 21     for(int i=head[x];i;i=e[i].next)dfs(e[i].to);
 22     q[++cnt]=x+n+1;
 23 }
 24 void add(int x,long long tag){tr[x].sum+=tag*tr[x].num;tr[x].v+=tag*tr[x].t;}
 25 void pushup(int x)
 26 {
 27     int l=tr[x].ch[0],r=tr[x].ch[1];
 28     tr[x].num=tr[l].num+tr[r].num+tr[x].t;
 29     tr[x].sum=tr[l].sum+tr[r].sum+tr[x].v;
 30 }
 31 void pushdown(int x)
 32 {
 33     int l=tr[x].ch[0],r=tr[x].ch[1];long long tag=tr[x].tag;
 34     if(l)tr[l].tag+=tag,add(l,tag);
 35     if(r)tr[r].tag+=tag,add(r,tag);
 36     tr[x].tag=0;
 37 }
 38 void rotate(int x,int& k)
 39 {
 40     int y=tr[x].fa,z=tr[y].fa,l,r;
 41     if(tr[y].ch[0]==x)l=0;else l=1;r=l^1;
 42     if(y==k)k=x;
 43     else{if(tr[z].ch[0]==y)tr[z].ch[0]=x;else tr[z].ch[1]=x;}
 44     tr[x].fa=z;tr[y].fa=x;tr[tr[x].ch[r]].fa=y;
 45     tr[y].ch[l]=tr[x].ch[r];tr[x].ch[r]=y;
 46     pushup(y);pushup(x);
 47 }
 48 void splay(int x,int& k)
 49 {
 50     int top=0;s[++top]=x;
 51     for(int i=x;tr[i].fa;i=tr[i].fa)s[++top]=tr[i].fa;
 52     for(int i=top;i;i--)if(tr[s[i]].tag)pushdown(s[i]);
 53     while(x!=k)
 54     {
 55         int y=tr[x].fa,z=tr[y].fa;
 56         if(y!=k)
 57         {
 58             if((tr[y].ch[0]==x)^(tr[z].ch[0]==y))rotate(x,k);
 59             else rotate(y,k);
 60         }
 61         rotate(x,k);
 62     }
 63 }
 64 int find(int x){while(tr[x].ch[1])x=tr[x].ch[1];return x;}
 65 void build(int l,int r,int last)
 66 {
 67     if(l>r)return;
 68     int mid=(l+r)>>1;
 69     tr[q[mid]].fa=q[last];
 70     tr[q[last]].ch[mid>last]=q[mid];
 71     build(l,mid-1,mid);build(mid+1,r,mid);
 72     pushup(q[mid]);
 73 }
 74 int merge(int r1,int r2)
 75 {
 76     int w=find(r1);
 77     splay(w,r1);
 78     tr[w].ch[1]=r2;
 79     tr[r2].fa=w;
 80     pushup(w);
 81     return w;
 82 }
 83 void cutl(int x,int rt,int& r1,int& r2)
 84 {
 85     splay(x,rt);
 86     r1=tr[x].ch[0];r2=x;
 87     tr[x].ch[0]=0;
 88     tr[r1].fa=0;
 89     pushup(x);
 90 }
 91 void cutr(int x,int rt,int& r1,int& r2)
 92 {
 93     splay(x,rt);
 94     r1=x;r2=tr[x].ch[1];
 95     tr[x].ch[1]=0;
 96     tr[r2].fa=0;
 97     pushup(x);
 98 }
 99 void query()
100 {
101     int x=read()+1;
102     splay(x,root);
103     printf("%lld\n",tr[tr[x].ch[0]].sum+tr[x].v);
104 }
105 void change()
106 {
107     int x=read()+1,y=x+n,k=read()+1,p1,p2,p3;
108     cutl(x,root,p1,p2);
109     cutr(y,p2,p2,p3);
110     cutr(k,merge(p1,p3),p1,p3);
111     root=merge(merge(p1,p2),p3);
112 }
113 void add()
114 {
115     int x=read()+1,y=x+n;long long tag=read();
116     splay(x,root);splay(y,tr[x].ch[1]);
117     int z=tr[y].ch[0];
118     add(x,tag);add(y,tag);
119     add(z,tag);tr[z].tag+=tag;
120     pushup(y);pushup(x);
121 }
122 int main()
123 {
124     char str[5];
125     n=read();
126     for(int i=2;i<=n;i++)f=read(),insert(f,i);
127     for(int i=2;i<=n+1;i++)f=read(),tr[i].v=f,tr[i].t=1,tr[i+n].v=-f,tr[i+n].t=-1;
128     cnt=0;q[++cnt]=1;dfs(1);q[++cnt]=2*n+2;
129     build(1,2*n+2,0);root=q[n+1];
130     m=read();
131     while(m--)
132     {
133         scanf("%s",str);
134         if(str[0]==‘Q‘)query();
135         if(str[0]==‘C‘)change();
136         if(str[0]==‘F‘)add();
137     }
138     return 0;
139 }

View Code

【bzoj 3786】星系探索

Description

Input

Output

Sample Input

Sample Output

HINT