fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5. using i64  = long long;
  6. using f64  = long double;
  7. using ui64 = unsigned long long;
  8. using pII  = pair<int,int>;
  9. using pLL  = pair<i64,i64>;
  10. mt19937 rng32(time(0));
  11. mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
  12. int t,n,q,a[100009],b[100009],bb[100009][10],seg[500009][10],lazy[500009][10];
  13. int ci,cp,sz[100009],head[100009],par[100009],pos[100009],rL[500009],rR[500009];
  14. vector<int> adj[100009];
  15. void buildrange(int node,int l,int r)
  16. {
  17.     if(l==r) rL[node]=l,rR[node]=r;
  18.     else
  19.     {
  20.         buildrange(2*node,l,(l+r)/2);
  21.         buildrange(2*node+1,(l+r)/2+1,r);
  22.         rL[node]=rL[2*node];rR[node]=rR[2*node+1];
  23.     }
  24. }
  25. void build(int node,int l,int r,int8_t _b)
  26. {
  27.     lazy[node][_b]=0;
  28.     if(l==r) seg[node][_b]=bb[l][_b];
  29.     else
  30.     {
  31.         build(2*node,l,(l+r)/2,_b);
  32.         build(2*node+1,(l+r)/2+1,r,_b);
  33.         seg[node][_b]=seg[2*node][_b]+seg[2*node+1][_b];
  34.     }
  35. }
  36. void down(int node,int8_t _b)
  37. {
  38.     if(lazy[node][_b]&1)
  39.     {
  40.         seg[2*node][_b]=rR[2*node]-rL[2*node]+1-seg[2*node][_b];
  41.         seg[2*node+1][_b]=rR[2*node+1]-rL[2*node+1]+1-seg[2*node+1][_b];
  42.     }
  43.     lazy[2*node][_b]^=lazy[node][_b];
  44.     lazy[2*node+1][_b]^=lazy[node][_b];
  45.     lazy[node][_b]=0;
  46. }
  47. void update(int node,int tl,int tr,int l,int r,bool v,int8_t _b)
  48. {
  49.     if(tr<l or r<tl) return;
  50.     if(l<=tl and tr<=r)
  51.     {
  52.         if(v&1) seg[node][_b]=rR[node]-rL[node]+1-seg[node][_b];
  53.         lazy[node][_b]^=v;
  54.         return;
  55.     }
  56.     down(node,_b);
  57.     update(2*node,tl,(tl+tr)/2,l,r,v,_b);
  58.     update(2*node+1,(tl+tr)/2+1,tr,l,r,v,_b);
  59.     seg[node][_b]=seg[2*node][_b]+seg[2*node+1][_b];
  60. }
  61. void real_update(int l,int r,int v){
  62.     for(short i=0;i<10;++i) update(1,1,n,l,r,(v>>i)&1,i);
  63. }
  64. int sum(int node,int tl,int tr,int l,int r,int8_t _b)
  65. {
  66.     if(tr<l or r<tl) return 0;
  67.     if(l<=tl and tr<=r) return seg[node][_b];
  68.     down(node,_b);
  69.     return sum(2*node,tl,(tl+tr)/2,l,r,_b)+sum(2*node+1,(tl+tr)/2+1,tr,l,r,_b);
  70. }
  71. int real_sum(int l,int r){
  72.     int s=0;
  73.     for(short i=0;i<10;++i) s+=(1<<i)*sum(1,1,n,l,r,i);
  74.     return s;
  75. }
  76. void DFS(int u,int pu)
  77. {
  78.     par[u]=pu; sz[u]=1;
  79.     for(int v:adj[u])
  80.     {
  81.         if(v!=pu)
  82.         {
  83.             DFS(v,u);
  84.             sz[u]+=sz[v];
  85.         }
  86.     }
  87. }
  88. void HLD(int u,int pu)
  89. {
  90.     b[ci]=u;pos[u]=ci;++ci;
  91.     head[u]=b[cp];
  92.     int mx=-1;
  93.     for(int v:adj[u])
  94.         if(v!=pu and sz[v]>sz[mx]) mx=v;
  95.     if(mx<0) {cp=ci;return;}
  96.     HLD(mx,u);
  97.     for(int v:adj[u])
  98.         if(v!=mx and v!=pu) HLD(v,u);
  99. }
  100. int LCA(int u,int v)
  101. {
  102.     while(head[u]!=head[v])
  103.     {
  104.         if(sz[head[u]]<sz[head[v]]) u=par[head[u]];
  105.         else v=par[head[v]];
  106.     }
  107.     return sz[u]>sz[v]?u:v;
  108. }
  109. void even_real_update(int u,int v,int val)
  110. {
  111.     int L=LCA(u,v);
  112.     while(head[u]!=head[L])
  113.     {
  114.         real_update(pos[head[u]],pos[u],val);
  115.         u=par[head[u]];
  116.     }
  117.     while(head[v]!=head[L])
  118.     {
  119.         real_update(pos[head[v]],pos[v],val);
  120.         v=par[head[v]];
  121.     }
  122.     if(sz[u]>sz[v]) real_update(pos[u],pos[v],val);
  123.     else real_update(pos[v],pos[u],val);
  124. }
  125. int even_real_sum(int u,int v)
  126. {
  127.     int L=LCA(u,v),res=0;
  128.     while(head[u]!=head[L])
  129.     {
  130.         res+=real_sum(pos[head[u]],pos[u]);
  131.         u=par[head[u]];
  132.     }
  133.     while(head[v]!=head[L])
  134.     {
  135.         res+=real_sum(pos[head[v]],pos[v]);
  136.         v=par[head[v]];
  137.     }
  138.     if(sz[u]>sz[v]) res+=real_sum(pos[u],pos[v]);
  139.     else res+=real_sum(pos[v],pos[u]);
  140.     return res;
  141. }
  142. void azarathmetrionzithos()
  143. {
  144.     cin>>n; ci=cp=1;
  145.     for(int i=1;i<=n;++i)
  146.     {
  147.         cin>>a[i];
  148.         adj[i].clear();
  149.         adj[i].shrink_to_fit();
  150.     }
  151.     for(int u,v,i=1;i<n;++i)
  152.     {
  153.         cin>>u>>v;
  154.         adj[u].push_back(v);
  155.         adj[v].push_back(u);
  156.     }
  157.     adj[1].push_back(0);
  158.     DFS(1,0); sz[0]=1+sz[1];
  159.     HLD(1,0); buildrange(1,1,n);
  160.     for(int i=1;i<=n;++i)
  161.         for(int8_t j=0;j<10;++j) bb[i][j]=(a[b[i]]>>j)&1;
  162.     for(int8_t i=0;i<10;++i) build(1,1,n,i);
  163.     cin>>q;
  164.     for(int cmd,u,v,p;q>0;--q)
  165.     {
  166.         cin>>cmd;
  167.         if(cmd==1)
  168.         {
  169.             cin>>u>>v>>p;
  170.             even_real_update(u,v,p);
  171.         }
  172.         else
  173.         {
  174.             cin>>u>>v;
  175.             cout<<even_real_sum(u,v)<<'\n';
  176.         }
  177.     }
  178. }
  179. signed main()
  180. {
  181.     if(fopen("XORTREE.INP","r"))
  182.     {
  183.         freopen("XORTREE.INP","r",stdin);
  184.         freopen("XORTREE.OUT","w",stdout);
  185.     }
  186.     ios_base::sync_with_stdio(0);
  187.     cin.tie(0);cout.tie(0);
  188.     cin>>t;
  189.     while(t--) azarathmetrionzithos();
  190. }
  191.  
Success #stdin #stdout 0.01s 6264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3rwGBO
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!