fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef int ll;
  4. template <typename T>
  5. inline void in(T &a) {
  6. 	register T c;
  7. 	a = 0;
  8. 	do c = getchar_unlocked(); while(c < '0');
  9. 	do {
  10. 		a = (a << 1) + (a << 3) + c - '0';
  11. 		c = getchar_unlocked();
  12. 	} while (c >= '0');
  13. }
  14. template <typename T>
  15. inline void pr(T a) {
  16. 	char s[11];
  17. 	T t = -1;
  18. 	do {
  19. 		s[++t] = a % 10 + '0';
  20. 		a /= 10;
  21. 	} while (a > 0);
  22. 	while (t >= 0) putchar_unlocked(s[t--]);
  23. 	putchar_unlocked('\n');
  24. }
  25. struct node
  26. {
  27.     ll key,prio,size;
  28.     node* left,*right;
  29. };
  30. struct alone
  31. {
  32.     node* root=NULL;
  33.     node* create(ll x)
  34.     {
  35.         node* p=new node;
  36.         p->key=x;
  37.         p->prio=rand();
  38.         p->size=1;
  39.         p->left=NULL;
  40.         p->right=NULL;
  41.         return p;
  42.     }
  43.     ll usize(node* p)
  44.     {
  45.         if(p)
  46.         return p->size;
  47.         return 0;
  48.     }
  49.     void nsize(node* p)
  50.     {
  51.         p->size=1+usize(p->left)+usize(p->right);
  52.     }
  53.     pair<node*,node*>split(node* root,ll x)
  54.     {
  55.         if(root==NULL)
  56.         return make_pair(root,root);
  57.         if(root->key<=x)
  58.         {
  59.             pair<node*,node*>p=split(root->right,x);
  60.             root->right=p.first;
  61.             if(root)
  62.             nsize(root);
  63.             if(p.second)
  64.             nsize(p.second);
  65.             return make_pair(root,p.second);
  66.         }
  67.         pair<node*,node*>p=split(root->left,x);
  68.         root->left=p.second;
  69.         if(root)
  70.         nsize(root);
  71.         if(p.first)
  72.         nsize(p.first);
  73.         return make_pair(p.first,root);
  74.     }
  75.     node* merge(node* root1,node* root2)
  76.     {
  77.         if(root1==NULL||root2==NULL)
  78.         return (root1==NULL)?root2:root1;
  79.         if(root1->prio>root2->prio)
  80.         {
  81.             node* p=merge(root1->right,root2);
  82.             root1->right=p;
  83.             if(root1)
  84.             nsize(root1);
  85.             return root1;
  86.         }
  87.         node* p=merge(root1,root2->left);
  88.         root2->left=p;
  89.         if(root2)
  90.         nsize(root2);
  91.         return root2;
  92.     }
  93.     node* insert(node* root,ll x)
  94.     {
  95.         node* tmp=create(x);
  96.         pair<node*,node*>p=split(root,x);
  97.         node* p1=merge(p.first,tmp);
  98.         if(p1)
  99.         nsize(p1);
  100.         node* p2=merge(p1,p.second);
  101.         if(p2)
  102.         nsize(p2);
  103.         return p2;
  104.     }
  105.     node* del(node* root,ll x)
  106.     {
  107.         if(root==NULL)
  108.         return root;
  109.         if(root->key==x)
  110.         {
  111.             node* p=merge(root->left,root->right);
  112.             delete root;
  113.             if(p)
  114.             nsize(p);
  115.             return p;
  116.         }
  117.         if(root->key<x)
  118.         root->right=del(root->right,x);
  119.         else
  120.         root->left=del(root->left,x);
  121.         if(root)
  122.         nsize(root);
  123.         return root;
  124.     }
  125.     ll count(node* root,ll k,ll val)
  126.     {
  127.         if(root==NULL)
  128.         return val;
  129.         if(root->key==k)
  130.         return val+usize(root->left);
  131.         if(root->key<k)
  132.         return count(root->right,k,val+usize(root->left)+1);
  133.         return count(root->left,k,val);
  134.     }
  135. }seg[4000005];
  136. void build(ll s,ll e,ll p,ll indx,ll val)
  137. {
  138.     if(s==e)
  139.     {
  140.         seg[p].root=seg[p].insert(seg[p].root,val);
  141.         return;
  142.     }
  143.     ll mid=(s+e)/2;
  144.     if(indx<=mid)
  145.     {
  146.         build(s,mid,2*p+1,indx,val);
  147.         seg[p].root=seg[p].insert(seg[p].root,val);
  148.     }
  149.     else
  150.     {
  151.         build(mid+1,e,2*p+2,indx,val);
  152.         seg[p].root=seg[p].insert(seg[p].root,val);
  153.     }
  154. }
  155. void update(ll s,ll e,ll p,ll indx,ll val)
  156. {
  157.     if(s==e)
  158.     {
  159.         seg[p].root=seg[p].del(seg[p].root,val);
  160.         return;
  161.     }
  162.     ll mid=(s+e)/2;
  163.     if(indx<=mid)
  164.     {
  165.         update(s,mid,2*p+1,indx,val);
  166.         seg[p].root=seg[p].del(seg[p].root,val);
  167.     }
  168.     else
  169.     {
  170.         update(mid+1,e,2*p+2,indx,val);
  171.         seg[p].root=seg[p].del(seg[p].root,val);
  172.     }
  173. }
  174. ll querry(ll s,ll e,ll p,ll ql,ll qh,ll x)
  175. {
  176.     if(s>qh||e<ql)
  177.     return 0;
  178.     if(s>=ql&&e<=qh)
  179.     {
  180.         ll u=seg[p].count(seg[p].root,x,0);
  181.         ll z=seg[p].usize(seg[p].root);
  182.         return z-u;
  183.     }
  184.     ll mid=(s+e)/2;
  185.     ll k1=querry(s,mid,2*p+1,ql,qh,x);
  186.     ll k2=querry(mid+1,e,2*p+2,ql,qh,x);
  187.     return k1+k2;
  188. }
  189. int main()
  190. {
  191.     ll n,i,q,qt,l,r,x;
  192.     in(n);
  193.     ll a[n];
  194.     for(i=0;i<n;i++)
  195.     {
  196.         in(a[i]);
  197.         build(0,n-1,0,i,a[i]);
  198.     }
  199.     in(q);
  200.     while(q--)
  201.     {
  202.         in(qt);
  203.         if(qt==0)
  204.         {
  205.             in(l);
  206.             in(r);
  207.             in(x);
  208.             l--;
  209.             r--;
  210.             ll ans=querry(0,n-1,0,l,r,x);
  211.             pr(ans);
  212.         }
  213.         else
  214.         {
  215.             in(l);
  216.             in(x);
  217.             l--;
  218.             update(0,n-1,0,l,a[l]);
  219.             a[l]=x;
  220.             build(0,n-1,0,l,a[l]);
  221.         }
  222.     }
  223. }
Time limit exceeded #stdin #stdout 5s 46536KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/hfsNLf
problem GIVEAWAY, based on SPOJ submission 23750328 (CPP14), 2019-05-11 19:36:18
language:
C++14 (gcc 8.3)
created:
6 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!