Jiu Yuan Wants to Eat(树链剖分+线段树延迟标记)
Jiu Yuan Wants to Eat
https://nanti.jisuanke.com/t/31714
You ye Jiu yuan is the daughter of the Great GOD Emancipator. And when she becomes an adult, she will be queen of Tusikur, so she wanted to travel the world while she was still young. In a country, she found a small pub called Whitehouse. Just as she was about to go in for a drink, the boss Carola appeared. And ask her to solve this problem or she will not be allowed to enter the pub. The problem description is as follows:
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。There is a tree with nn nodes, each node ii contains weight a[i]a[i], the initial value of a[i]a[i] is 00. The root number of the tree is 11. Now you need to do the following operations:
1)1) Multiply all weight on the path from uu to vv by xx
2)2) For all weight on the path from uu to vv, increasing xx to them
3)3) For all weight on the path from uu to vv, change them to the bitwise NOT of them
4)4) Ask the sum of the weight on the path from uu to vv
The answer modulo 2^{64}264.
Jiu Yuan is a clever girl, but she was not good at algorithm, so she hopes that you can help her solve this problem. Ding\backsim\backsim\backsim∽∽∽
The bitwise NOT is a unary operation that performs logical negation on each bit, forming the ones' complement of the given binary value. Bits that are 00 become 11, and those that are 11 become 00. For example:
NOT 0111 (decimal 7) = 1000 (decimal 8)
NOT 10101011 = 01010100
Input
The input contains multiple groups of data.
For each group of data, the first line contains a number of nn, and the number of nodes.
The second line contains (n - 1)(n−1) integers b_ibi, which means that the father node of node (i +1)(i+1) is b_ibi.
The third line contains one integer mm, which means the number of operations，
The next mm lines contain the following four operations:
At first, we input one integer opt
1)1) If opt is 11, then input 33 integers, u, v, xu,v,x, which means multiply all weight on the path from uu to vv by xx
2)2) If opt is 22, then input 33 integers, u, v, xu,v,x, which means for all weight on the path from uu to vv, increasing xx to them
3)3) If opt is 33, then input 22 integers, u, vu,v, which means for all weight on the path from uu to vv, change them to the bitwise NOT of them
4)4) If opt is 44, then input 22 integers, u, vu,v, and ask the sum of the weights on the path from uu to vv
1 \le n,m,u,v \le 10^51≤n,m,u,v≤105
1 \le x < 2^{64}1≤x<264
Output
For each operation 44, output the answer.
样例输入
7 1 1 1 2 2 4 5 2 5 6 1 1 1 6 2 4 5 6 3 5 2 4 2 2 2 1 4 3 1 2 4 1 2 3 1 1 4 1 1
样例输出
5 18446744073709551613 18446744073709551614 0
题目来源
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<cstdio> 6 #include<algorithm> 7 #include<vector> 8 #define maxn 100005 9 #define lson l,mid,rt<<1 10 #define rson mid+1,r,rt<<1|1 11 typedef unsigned long long ull; 12 using namespace std; 13 14 ull tree[maxn<<3],lazya[maxn<<3],lazym[maxn<<3]; 15 int n; 16 ull v[maxn],val[maxn]; 17 int dep[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn],top[maxn],cnt; 18 vector<ull>ve[maxn]; 19 20 void pushup(int rt){ 21 tree[rt]=tree[rt<<1]+tree[rt<<1|1]; 22 } 23 24 void pushdown(int len,int rt){ 25 if(lazya[rt]||lazym[rt]!=1){ 26 lazym[rt<<1]*=lazym[rt]; 27 lazym[rt<<1|1]*=lazym[rt]; 28 lazya[rt<<1]*=lazym[rt]; 29 lazya[rt<<1|1]*=lazym[rt]; 30 lazya[rt<<1]+=lazya[rt]; 31 lazya[rt<<1|1]+=lazya[rt]; 32 tree[rt<<1]*=lazym[rt]; 33 tree[rt<<1|1]*=lazym[rt]; 34 tree[rt<<1]+=(len-len/2)*lazya[rt]; 35 tree[rt<<1|1]+=len/2*lazya[rt]; 36 lazya[rt]=0; 37 lazym[rt]=1; 38 } 39 } 40 41 void build(int l,int r,int rt){ 42 lazya[rt]=0; 43 lazym[rt]=1; 44 if(l==r){ 45 tree[rt]=0; 46 return; 47 } 48 int mid=(l+r)/2; 49 build(lson); 50 build(rson); 51 pushup(rt); 52 } 53 54 void mul(int L,int R,ull k,int l,int r,int rt){ 55 if(L<=l&&R>=r){ 56 pushdown(r-l+1,rt); 57 tree[rt]*=k; 58 lazym[rt]*=k; 59 lazya[rt]*=k; 60 return; 61 } 62 int mid=(l+r)/2; 63 pushdown(r-l+1,rt); 64 if(L<=mid) mul(L,R,k,lson); 65 if(R>mid) mul(L,R,k,rson); 66 pushup(rt); 67 } 68 69 void add(int L,int R,ull k,int l,int r,int rt){ 70 if(L<=l&&R>=r){ 71 pushdown(r-l+1,rt); 72 tree[rt]+=(r-l+1)*k; 73 lazya[rt]+=k; 74 return; 75 } 76 int mid=(l+r)/2; 77 pushdown(r-l+1,rt); 78 if(L<=mid) add(L,R,k,lson); 79 if(R>mid) add(L,R,k,rson); 80 pushup(rt); 81 } 82 83 void Not(int L,int R,int l,int r,int rt){ 84 if(L<=l&&R>=r){ 85 pushdown(r-l+1,rt); 86 tree[rt]+=(r-l+1); 87 tree[rt]=-tree[rt]; 88 lazym[rt]=-lazym[rt]; 89 lazya[rt]++; 90 lazya[rt]=-lazya[rt]; 91 return; 92 } 93 int mid=(l+r)/2; 94 pushdown(r-l+1,rt); 95 if(L<=mid) Not(L,R,lson); 96 if(R>mid) Not(L,R,rson); 97 pushup(rt); 98 } 99 100 ull query(int L,int R,int l,int r,int rt){ 101 if(L<=l&&R>=r){ 102 return tree[rt]; 103 } 104 int mid=(l+r)/2; 105 pushdown(r-l+1,rt); 106 ull ans=0; 107 if(L<=mid) ans+=query(L,R,lson); 108 if(R>mid) ans+=query(L,R,rson); 109 pushup(rt); 110 return ans; 111 } 112 113 void dfs1(int now,int f,int deep){ 114 dep[now]=deep; 115 siz[now]=1; 116 fa[now]=f; 117 int maxson=-1; 118 for(int i=0;i<ve[now].size();i++){ 119 if(ve[now][i]==f) continue; 120 dfs1(ve[now][i],now,deep+1); 121 siz[now]+=siz[ve[now][i]]; 122 if(siz[ve[now][i]]>maxson){ 123 maxson=siz[ve[now][i]]; 124 son[now]=ve[now][i]; 125 } 126 } 127 } 128 129 void dfs2(int now,int topp){ 130 id[now]=++cnt; 131 val[cnt]=v[now]; 132 top[now]=topp; 133 if(!son[now]) return; 134 dfs2(son[now],topp); 135 for(int i=0;i<ve[now].size();i++){ 136 if(ve[now][i]==son[now]||ve[now][i]==fa[now]) continue; 137 dfs2(ve[now][i],ve[now][i]); 138 } 139 } 140 141 ull qRange(int x,int y){ 142 ull ans=0; 143 while(top[x]!=top[y]){ 144 if(dep[top[x]]<dep[top[y]]) swap(x,y); 145 ans+=query(id[top[x]],id[x],1,n,1); 146 x=fa[top[x]]; 147 } 148 if(dep[x]>dep[y]) swap(x,y); 149 ans+=query(id[x],id[y],1,n,1); 150 return ans; 151 } 152 153 void addRange(int x,int y,int k){ 154 while(top[x]!=top[y]){ 155 if(dep[top[x]]<dep[top[y]]) swap(x,y); 156 add(id[top[x]],id[x],k,1,n,1); 157 x=fa[top[x]]; 158 } 159 if(dep[x]>dep[y]) swap(x,y); 160 add(id[x],id[y],k,1,n,1); 161 } 162 163 void mulRange(int x,int y,int k){ 164 while(top[x]!=top[y]){ 165 if(dep[top[x]]<dep[top[y]]) swap(x,y); 166 mul(id[top[x]],id[x],k,1,n,1); 167 x=fa[top[x]]; 168 } 169 if(dep[x]>dep[y]) swap(x,y); 170 mul(id[x],id[y],k,1,n,1); 171 } 172 173 void notRange(int x,int y){ 174 while(top[x]!=top[y]){ 175 if(dep[top[x]]<dep[top[y]]) swap(x,y); 176 Not(id[top[x]],id[x],1,n,1); 177 x=fa[top[x]]; 178 } 179 if(dep[x]>dep[y]) swap(x,y); 180 Not(id[x],id[y],1,n,1); 181 } 182 183 int main(){ 184 int m,r; 185 while(~scanf("%d",&n)){ 186 memset(v,0,sizeof(v)); 187 memset(val,0,sizeof(val)); 188 memset(dep,0,sizeof(dep)); 189 memset(fa,0,sizeof(fa)); 190 memset(siz,0,sizeof(siz)); 191 memset(son,0,sizeof(son)); 192 memset(id,0,sizeof(id)); 193 memset(top,0,sizeof(top)); 194 int pos,z,x,y; 195 for(int i=0;i<=n;i++){ 196 ve[i].clear(); 197 } 198 for(int i=2;i<=n;i++){ 199 scanf("%d",&x); 200 ve[x].push_back(i); 201 ve[i].push_back(x); 202 } 203 cnt=0; 204 dfs1(1,0,1); 205 dfs2(1,1); 206 build(1,n,1); 207 scanf("%d",&m); 208 for(int i=1;i<=m;i++){ 209 scanf("%d %d %d",&pos,&x,&y); 210 if(pos==1){ 211 scanf("%d",&z); 212 mulRange(x,y,z); 213 } 214 else if(pos==2){ 215 scanf("%d",&z); 216 addRange(x,y,z); 217 } 218 else if(pos==3){ 219 notRange(x,y); 220 } 221 else{ 222 printf("%llu\n",qRange(x,y)); 223 } 224 } 225 } 226 }View Code
