fork(2) download
copy 
  1. //
  2. //  main.cpp
  3. //  xrqrs
  4. //
  5. //  Created by Saras Gupta on 06/01/15.
  6. //  Copyright (c) 2015 sarasgupta. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <algorithm>
  11. #include <cmath>
  12. #include <vector>
  13.  
  14. #define N 524288
  15. //2^19=524288
  16. #define mp(x,y) make_pair(x,y)
  17.  
  18. using namespace std;
  19.  
  20. typedef struct node {
  21.     int lp[2],rp[2],l,r,ct,mx;
  22.     //lp and rp point to the node's left and right child. [0] refers to the segment tree no. and [1] refers to the node number
  23.     //l and r are the left and right limits of the node
  24.     //ct is the counter for that node
  25.     //mx stores the number of elements <=r
  26. }node;
  27.  
  28. vector<vector<node> > v(500005);//array of segment trees
  29. int ctr=1,bin[20];
  30. //ctr is the number of segment trees which are valid
  31. //bin[i]=2^i
  32.  
  33. //make a base segment tree when there are no elements in the array
  34. void init_tree(int it, int l, int r) {
  35.     v[0][it].l=l;
  36.     v[0][it].r=r;
  37.     v[0][it].ct=0;
  38.     v[0][it].mx=0;
  39.     if (l!=r) {
  40.         int mid=(l+r)/2;
  41.         init_tree((2*it)+1, l, mid);
  42.         init_tree((2*it)+2, mid+1, r);
  43.         v[0][it].lp[0]=0;
  44.         v[0][it].lp[1]=(2*it)+1;
  45.         v[0][it].rp[0]=0;
  46.         v[0][it].rp[1]=(2*it)+2;
  47.         //add the index of the node's left and right child.
  48.     }
  49. }
  50.  
  51. void q0(int it, int l, int r, pair<int, int> itm) {
  52.     if (v[ctr][it].l==l&&v[ctr][it].r==r) {
  53.         v[ctr][it].lp[0]=v[itm.first][itm.second].lp[0];
  54.         v[ctr][it].lp[1]=v[itm.first][itm.second].lp[1];
  55.         v[ctr][it].rp[0]=v[itm.first][itm.second].rp[0];
  56.         v[ctr][it].rp[1]=v[itm.first][itm.second].rp[1];
  57.         //since there are no more changes below this node, we can easily point to the children of the previous segment tree as this node's children
  58.         v[ctr][it].l=l;
  59.         v[ctr][it].r=r;
  60.         v[ctr][it].ct=v[itm.first][itm.second].ct+1;
  61.         v[ctr][it].mx=0;
  62.         if (l!=r) {
  63.             v[ctr][it].mx=v[v[ctr][it].rp[0]][v[ctr][it].rp[1]].mx+v[v[ctr][it].rp[0]][v[ctr][it].rp[1]].ct;
  64.         }
  65.     }
  66.     else {
  67.         int mid=(v[ctr][it].l+v[ctr][it].r)/2;
  68.         v[ctr][it].ct=v[itm.first][itm.second].ct;
  69.         if (l<=mid) {
  70.             //this means that we have to add a new node as the left child of this node and update this node accordingly
  71.             node tp;
  72.             v[ctr].push_back(tp);
  73.             v[ctr][it].lp[0]=ctr;
  74.             v[ctr][it].lp[1]=v[ctr].size()-1;
  75.             v[ctr][v[ctr].size()-1].l=v[ctr][it].l;
  76.             v[ctr][v[ctr].size()-1].r=mid;
  77.             q0(v[ctr].size()-1, l, min(mid, r), mp(v[itm.first][itm.second].lp[0], v[itm.first][itm.second].lp[1]));
  78.         }
  79.         else {
  80.             //else we can just point to the children of the prevous segment tree's node
  81.             v[ctr][it].lp[0]=v[itm.first][itm.second].lp[0];
  82.             v[ctr][it].lp[1]=v[itm.first][itm.second].lp[1];
  83.         }
  84.         if (r>mid) {
  85.             //this means that we have to add a new node as the right child of this node and update this node accordingly
  86.             node tp;
  87.             tp.l=mid+1;
  88.             tp.r=r;
  89.             v[ctr].push_back(tp);
  90.             v[ctr][it].rp[0]=ctr;
  91.             v[ctr][it].rp[1]=v[ctr].size()-1;
  92.             v[ctr][v[ctr].size()-1].l=mid+1;
  93.             v[ctr][v[ctr].size()-1].r=v[ctr][it].r;
  94.             q0(v[ctr].size()-1, max(mid+1, l), r, mp(v[itm.first][itm.second].rp[0], v[itm.first][itm.second].rp[1]));
  95.         }
  96.         else {
  97.             //else we can just point to the children of the prevous segment tree's node
  98.             v[ctr][it].rp[0]=v[itm.first][itm.second].rp[0];
  99.             v[ctr][it].rp[1]=v[itm.first][itm.second].rp[1];
  100.         }
  101.         v[ctr][it].mx=v[v[ctr][it].rp[0]][v[ctr][it].rp[1]].mx+v[v[ctr][it].rp[0]][v[ctr][it].rp[1]].ct;
  102.         //updating mx of this node
  103.     }
  104. }
  105.  
  106. int q3(pair<int, int> it, int r, int sum) {
  107.     if (v[it.first][it.second].l==r&&v[it.first][it.second].r==r) {
  108.         return v[it.first][it.second].ct+sum;
  109.     }
  110.     else {
  111.         int mid=(v[it.first][it.second].l+v[it.first][it.second].r)/2;
  112.         sum+=v[it.first][it.second].ct;
  113.         if (mid>=r) {
  114.             return q3(mp(v[it.first][it.second].lp[0], v[it.first][it.second].lp[1]), r, sum);
  115.         }
  116.         else {
  117.             return q3(mp(v[it.first][it.second].rp[0], v[it.first][it.second].rp[1]), r, sum);
  118.         }
  119.     }
  120. }
  121.  
  122. int q3f(int l, int r, int x) {
  123.     //ans(l,r,x)=ans(0, r, x)-ans(0, l-1, x)
  124.     int ans=q3(mp(r, 0), x, 0);
  125.     //{r, 0} refers to the index of the root of the segment tree
  126.     if (l>1) {
  127.         ans-=q3(mp(l-1, 0), x, 0);
  128.     }
  129.     return ans;
  130. }
  131.  
  132. int q4t(int l, int r, int k) {
  133.     //Res ipsa loquitur
  134.     pair<int, int> il(l-1, 0);
  135.     pair<int, int> ir(r, 0);
  136.     int p1=0,p2=0;
  137.     while (v[ir.first][ir.second].r-v[ir.first][ir.second].l>=1) {
  138.         p1+=v[ir.first][ir.second].ct;
  139.         p2+=v[il.first][il.second].ct;
  140.         int p=v[v[ir.first][ir.second].lp[0]][v[ir.first][ir.second].lp[1]].mx + v[v[ir.first][ir.second].lp[0]][v[ir.first][ir.second].lp[1]].ct+p1;
  141.         int q=v[v[il.first][il.second].lp[0]][v[il.first][il.second].lp[1]].mx + v[v[il.first][il.second].lp[0]][v[il.first][il.second].lp[1]].ct+p2;
  142.         if (p-q>=k) {
  143.             ir=mp(v[ir.first][ir.second].lp[0], v[ir.first][ir.second].lp[1]);
  144.             il=mp(v[il.first][il.second].lp[0], v[il.first][il.second].lp[1]);
  145.         }
  146.         else {
  147.             ir=mp(v[ir.first][ir.second].rp[0], v[ir.first][ir.second].rp[1]);
  148.             il=mp(v[il.first][il.second].rp[0], v[il.first][il.second].rp[1]);
  149.         }
  150.     }
  151.     return v[ir.first][ir.second].r;
  152. }
  153.  
  154. int q1t(int l, int r, int k) {
  155.     //if you understand q4t() than you can make this yourself
  156.     pair<int, int> il(l-1, 0);
  157.     pair<int, int> ir(r, 0);
  158.     int p1=0,p2=0;
  159.     int ctrr=r-l+1;
  160.     for (int i=18; i>=0; i--) {
  161.         int p=v[v[ir.first][ir.second].rp[0]][v[ir.first][ir.second].rp[1]].mx + v[v[ir.first][ir.second].rp[0]][v[ir.first][ir.second].rp[1]].ct  -  (v[v[ir.first][ir.second].lp[0]][v[ir.first][ir.second].lp[1]].mx + v[v[ir.first][ir.second].lp[0]][v[ir.first][ir.second].lp[1]].ct);
  162.         int q=v[v[il.first][il.second].rp[0]][v[il.first][il.second].rp[1]].mx + v[v[il.first][il.second].rp[0]][v[il.first][il.second].rp[1]].ct  -  (v[v[il.first][il.second].lp[0]][v[il.first][il.second].lp[1]].mx + v[v[il.first][il.second].lp[0]][v[il.first][il.second].lp[1]].ct);
  163.         if (bin[i]&k) {
  164.             if (p-q<ctrr) {
  165.                 ir=mp(v[ir.first][ir.second].lp[0], v[ir.first][ir.second].lp[1]);
  166.                 il=mp(v[il.first][il.second].lp[0], v[il.first][il.second].lp[1]);
  167.                 ctrr-=p-q;
  168.             }
  169.             else {
  170.                 ir=mp(v[ir.first][ir.second].rp[0], v[ir.first][ir.second].rp[1]);
  171.                 il=mp(v[il.first][il.second].rp[0], v[il.first][il.second].rp[1]);
  172.                 ctrr-=ctrr-(p-q);
  173.             }
  174.         }
  175.         else {
  176.             if (p-q==0) {
  177.                 ir=mp(v[ir.first][ir.second].lp[0], v[ir.first][ir.second].lp[1]);
  178.                 il=mp(v[il.first][il.second].lp[0], v[il.first][il.second].lp[1]);
  179.                 ctrr-=p-q;
  180.             }
  181.             else {
  182.                 ir=mp(v[ir.first][ir.second].rp[0], v[ir.first][ir.second].rp[1]);
  183.                 il=mp(v[il.first][il.second].rp[0], v[il.first][il.second].rp[1]);
  184.                 ctrr-=ctrr-(p-q);
  185.             }
  186.         }
  187.     }
  188.     return v[ir.first][ir.second].r;
  189. }
  190.  
  191. int main(int argc, const char * argv[]) {
  192.     int m,type,l,r,x,cctt=0;
  193.     cin>>m;
  194.     for (int i=0; i<20; i++) {
  195.         bin[i]=1<<i;
  196.     }
  197.     v[0].resize((long long int)((2*(pow(2, ceil(log2(N)))))-1));
  198.     init_tree(0, 0, N-1);
  199.     for (int i=0; i<m; i++) {
  200.         cin>>type;
  201.         if (type==0) {
  202.             cctt++;
  203.             cin>>x;
  204.             v[ctr].clear();
  205.             node tp;
  206.             tp.l=0;
  207.             tp.r=N-1;
  208.             v[ctr].push_back(tp);
  209.             //initializing the root for this segment tree
  210.             q0(0, x, N-1, mp(ctr-1, 0));
  211.             ctr++;
  212.         }
  213.         else if (type==1) {
  214.             cin>>l>>r>>x;
  215.             cout<<q1t(l, r, x)<<endl;
  216.         }
  217.         else if (type==2) {
  218.             cin>>x;
  219.             ctr-=x;
  220.             //for deleting the last k elements just forget that the last k elements ever existed, it doesn't affect the trees before it.
  221.         }
  222.         else if  (type==3) {
  223.             cin>>l>>r>>x;
  224.             cout<<q3f(l, r, x)<<endl;
  225.         }
  226.         else {
  227.             cin>>l>>r>>x;
  228.             cout<<q4t(l, r, x)<<endl;
  229.         }
  230.     }
  231.     return 0;
  232. }
  233.  
Success #stdin #stdout 0.05s 3100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GbXyme
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!