fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long ll;
  4. struct node
  5. {
  6.     ll key;
  7.     ll size,prio;
  8.     node* left,*right;
  9. };
  10. struct treap
  11. {
  12.     node* root;
  13. }seg[2000005];
  14. node* create(ll x)
  15. {
  16.     node* p=new node;
  17.     p->key=x;
  18.     p->size=1;
  19.     p->prio=rand();
  20.     p->left=p->right=NULL;
  21.     return p;
  22. }
  23. ll usize(node* root)
  24. {
  25.     return root?root->size:0;
  26. }
  27. ll nsize(node* root)
  28. {
  29.     return 1+usize(root->left)+usize(root->right);
  30. }
  31. pair<node*,node*> split(node* root,ll x)
  32. {
  33.     if(!root)
  34.     return make_pair(root,root);
  35.     if(root->key<x)
  36.     {
  37.         pair<node*,node*> p=split(root->right,x);
  38.         root->right=p.first;
  39.         root->size=nsize(root);
  40.         return make_pair(root,p.second);
  41.     }
  42.     else
  43.     {
  44.         pair<node*,node*>p=split(root->left,x);
  45.         root->left=p.second;
  46.         root->size=nsize(root);
  47.         return make_pair(p.first,root);
  48.     }
  49. }
  50. node* merge(node* l,node* r)
  51. {
  52.     if(!l||!r)
  53.     return l?l:r;
  54.     if(l->prio>r->prio)
  55.     {
  56.         l->right=merge(l->right,r);
  57.         l->size=nsize(l);
  58.         return l;
  59.     }
  60.     else
  61.     {
  62.         r->left=merge(l,r->left);
  63.         r->size=nsize(r);
  64.         return r;
  65.     }
  66. }
  67. node* insert(node* root,ll x)
  68. {
  69.     node* tmp=create(x);
  70.     pair<node*,node*>p=split(root,x);
  71.     return merge(merge(p.first,tmp),p.second);
  72. }
  73. node* erase(node* root,ll x)
  74. {
  75.     pair<node*,node*>p1=split(root,x);
  76.     pair<node*,node*>p2=split(p1.second,x+1);
  77.     if(!p2.first)
  78.         return merge(p1.first,p2.second);
  79.     if(p2.first->size==1)
  80.     {
  81.         delete p2.first;
  82.         return merge(p1.first,p2.second);
  83.     }
  84.     return merge(p1.first,merge(p2.first->left,p2.first->right));
  85. }
  86. ll count(node* root,ll k,ll val)
  87. {
  88.     if(!root)
  89.     return val;
  90.     if(root->key==k)
  91.     return val+usize(root->left);
  92.     if(root->key<k)
  93.     return count(root->right,k,val+usize(root->left)+1);
  94.     return count(root->left,k,val);
  95. }
  96. void intr(ll s,ll e,ll p,ll indx,ll val)
  97. {
  98.     if(s==e)
  99.     {
  100.         seg[p].root=insert(seg[p].root,val);
  101.         return;
  102.     }
  103.      ll mid=(s+e)/2;
  104.      if(indx<=mid)
  105.      intr(s,mid,2*p+1,indx,val);
  106.      else
  107.      intr(mid+1,e,2*p+2,indx,val);
  108.      seg[p].root=insert(seg[p].root,val);
  109. }
  110. void otr(ll s,ll e,ll p,ll indx,ll val)
  111. {
  112.     if(s==e)
  113.     {
  114.         seg[p].root=erase(seg[p].root,val);
  115.         return;
  116.     }
  117.      ll mid=(s+e)/2;
  118.      if(indx<=mid)
  119.      otr(s,mid,2*p+1,indx,val);
  120.      else
  121.      otr(mid+1,e,2*p+2,indx,val);
  122.      seg[p].root=erase(seg[p].root,val);
  123. }
  124. ll querry(ll s,ll e,ll p,ll ql,ll qh,ll k)
  125. {
  126.     if(s>qh||e<ql)
  127.     return 0;
  128.     if(s>=ql&&e<=qh)
  129.     return usize(seg[p].root)-count(seg[p].root,k,0);
  130.     ll mid=(s+e)/2;
  131.     ll u=querry(s,mid,2*p+1,ql,qh,k);
  132.     ll v=querry(mid+1,e,2*p+2,ql,qh,k);
  133.     return v+u;
  134. }
  135. int main()
  136. {
  137.     ll q,qt,l,r,i,n;
  138.     ll x;
  139.     scanf("%lld",&n);
  140.     for(i=0;i<2000005;i++)
  141.     seg[i].root=NULL;
  142.     ll a[n];
  143.     for(i=0;i<n;i++)
  144.     {
  145.         scanf("%lld",&a[i]);
  146.         intr(0,n-1,0,i,a[i]);
  147.     }
  148.     scanf("%lld",&q);
  149.     while(q--)
  150.     {
  151.         scanf("%lld",&qt);
  152.         if(qt==0)
  153.         {
  154.             scanf("%lld%lld%lld",&l,&r,&x);
  155.             l--;
  156.             r--;
  157.             ll ans=querry(0,n-1,0,l,r,x);
  158.             printf("%lld\n",ans);
  159.         }
  160.         else
  161.         {
  162.             scanf("%lld%lld",&l,&x);
  163.             l--;
  164.             otr(0,n-1,0,l,a[l]);
  165.             a[l]=x;
  166.             intr(0,n-1,0,l,a[l]);
  167.         }
  168.     }
  169. }
Runtime error #stdin #stdout 0s 30864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FeEtTv
problem GIVEAWAY, based on SPOJ submission 23769902 (CPP), 2019-05-15 20:34:13
language:
C++ (gcc 8.3)
created:
4 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!