fork(1) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast_io ios_base::sync_with_stdio(0); //cin.tie(0);
  5. #define ll long long
  6. #define ld long double
  7. #define pb push_back
  8. #define ins insert
  9. #define in push
  10. #define out pop
  11. #define loop(i,n) for(i=1;i<=n;i++)
  12. #define loon(i,n) for(i=n;i>0;i--)
  13. #define vctr(x) vector< x >
  14. #define pii(x,y) pair< x,y >
  15. #define mkpr(x,y) make_pair(x,y)
  16. #define ft first
  17. #define sd second
  18. #define MX 200005
  19. #define mod 1000000007
  20. #define INF 10000000000000
  21.  
  22. struct node{
  23. node *left, *right;
  24. ll val;
  25.  
  26. node(ll v=0, node *l=NULL, node *r=NULL): left(l), right(r), val(v) {}
  27.  
  28. void build(ll l, ll r)
  29. {
  30. if(l==r)
  31. return;
  32. left = new node();
  33. right = new node();
  34. ll mid=(l+r)>>1;
  35. left->build(l,mid);
  36. right->build(mid+1,r);
  37. }
  38.  
  39. node* update(ll l, ll r, ll idx, ll v)
  40. {
  41. if(r<idx or l>idx)
  42. return this;
  43. if(l==r){
  44. node *ret = new node(val, left, right);
  45. ret->val+=v;
  46. return ret;
  47. }
  48. ll mid=(l+r)>>1;
  49. node *ret=new node(val);
  50. ret->left=left->update(l,mid,idx,v);
  51. ret->right=right->update(mid+1,r,idx,v);
  52. ret->val=ret->left->val+ret->right->val;
  53. return ret;
  54. }
  55.  
  56. ll query(ll l, ll r, ll i, ll j)
  57. {
  58. if(r<i or j<l)
  59. return 0;
  60. if(i<=l and r<=j)
  61. return val;
  62.  
  63. ll mid=(l+r)>>1;
  64. return left->query(l,mid,i,j)+right->query(mid+1,r,i,j);
  65. }
  66.  
  67. }*root[MX];
  68.  
  69.  
  70.  
  71. int main()
  72. {
  73.  
  74. fast_io;
  75. ll n,m,t,i,j,k,a,b,c,cs=1;
  76.  
  77. //freopen(input.txt, r, stdin);
  78. //freopen(output.txt, w, stdout);
  79.  
  80.  
  81. root[0]=new node();
  82.  
  83. cin>> n;
  84. ll num[n+1];
  85. root[0]->build(1,10005);
  86.  
  87. for(i=1;i<=n;i++){
  88. cin>> a;
  89. num[i]=a;
  90. root[i]=root[i-1]->update(1,10005,a,1);
  91. }
  92.  
  93. cin>> t;
  94. while(t--){
  95. cin>> m;
  96. if(m==0){
  97. cin>> a >> b;
  98. //root[a]=root[a-1]->update(1,10005,num[a],-1);
  99. root[a]=root[a-1]->update(1,10005,b,1);//Wrong Update
  100. num[a]=b;
  101. }
  102. else{
  103. cin>> a >> b >> c;
  104. ll p1=root[a-1]->query(1,10005,c+1,10005);
  105. ll p2=root[b]->query(1,10005,c+1,10005);
  106. cout<< p2-p1 << endl;
  107. }
  108. }
  109.  
  110. return 0;
  111. }
Runtime error #stdin #stdout 0s 16808KB
stdin
Standard input is empty
stdout
Standard output is empty