fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define f(a) ((a==NULL)?(0):(a->val))
  4. const int MAXN=(1<<15); 
  5. int N; 
  6. int arr [MAXN]; 
  7. struct node
  8. {
  9.     node * l; node * r; int val; 
  10.     node (node * a, node * b, int c){l=a, r=b; val=c;}
  11. }; 
  12. node * seg [2*MAXN]; 
  13. int find (int start, int end, node * a)
  14. {
  15.    if (start==end) return start;
  16.    if (f(a->l)) return find(start,(start+end)/2, a->l);
  17.    return find((start+end)/2+1, end, a->r); 
  18. }
  19. int query (int start, int end, int i, int node)
  20. {
  21.     if (start>i || end<i) return 0; 
  22.     if (start==end) {return find(1, 10000, seg[node]);} 
  23.     return max(query(start, (start+end)/2, i, 2*node), query((start+end)/2+1, end, i, 2*node+1)); 
  24. }
  25. void insert (node * &a, int start, int end, int x)
  26. {
  27.     if (start>x || end<x) return; 
  28.     if (a==NULL) a=new node (NULL, NULL, 0);
  29.     if (start==end){a->val++; return;}
  30.     insert(a->l, start, (start+end)/2, x); 
  31.     insert(a->r, (start+end)/2+1, end, x); 
  32.     a->val=f(a->l)+f(a->r); 
  33. }
  34. void build (int start, int end, int node)
  35. {
  36. 	if (start!=end){
  37. 	build(start,(start+end)/2, 2*node); 
  38.     build((start+end)/2+1,end, 2*node+1); }
  39.     for (int g=start; g<=end; g++) insert(seg[node], 1, 10000, arr[g]);
  40. }
  41. void remove (node * &a, int start, int end, int x)
  42. {
  43.     if (start>x || end<x) return; 
  44.     if (start==end)
  45.     {
  46.         a->val--; if (a->val==0) a=NULL; return; 
  47.     }
  48.     remove(a->l, start, (start+end)/2, x); 
  49.     remove(a->r, (start+end)/2+1, end, x); 
  50.     a->val=f(a->l)+f(a->r); 
  51.     if (a->val==0) a=NULL; 
  52. }
  53. int queryans (int start, int end, node * t, int k)
  54. {
  55.     if (t==NULL || t->val==0 || end<=k) return 0;
  56.     if (start>k) return t->val; 
  57.     return queryans(start,(start+end)/2, t->l, k)+queryans((start+end)/2+1, end, t->r, k);  
  58. }
  59. int findans (int start, int end, int i, int j, int node, int k)
  60. {
  61.     if (start>j || end<i) return 0; 
  62.     if(start>=i && end<=j)
  63.     {
  64.         return queryans (1, 10000, seg[node], k); 
  65.     }
  66.     return findans(start, (start+end)/2, i, j, 2*node, k)+findans((start+end)/2+1, end, i, j, 2*node+1, k); 
  67. }    
  68. void update (int start, int end, int i, int node, int toremove,int toinsert)
  69. {
  70.     if (start>i || end<i) return; 
  71.     remove (seg[node], 1, 10000, toremove); 
  72.     insert (seg[node], 1, 10000, toinsert); 
  73.     if (start!=end){update(start, (start+end)/2, i, 2*node, toremove, toinsert); update((start+end)/2+1, end, i, 2*node+1, toremove, toinsert);}
  74. }
  75. int main()
  76. {
  77.     scanf("%d", &N); for (int g=1; g<=N; g++) cin >> arr[g]; 
  78.     build (1, N, 1); 
  79.     int Q; scanf("%d", &Q); 
  80.     for (int g=0; g<Q; g++)
  81.     {
  82.         int type; scanf("%d", &type);
  83.         if (type)
  84.         {
  85.             int i, j, k; scanf("%d %d %d", &i, &j, &k); 
  86.             printf("%d\n", findans(1, N, i, j, 1, k));   
  87.         }
  88.         else
  89.         {
  90.             int i, v; scanf("%d %d", &i, &v); 
  91.             int x=query(1, N, i, 1);
  92.             update (1, N, i, 1, x, v);  
  93.         }
  94.     }
  95.     return 0; 
  96. }
Success #stdin #stdout 0s 3664KB
comments (?)
stdin
copy 
5
5 1 2 3 4
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2
stdout
copy 
2
1
2
https://ideone.com/CzlIZ0
language:
C++14 (gcc 8.3)
created:
9 years 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!