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