fork(9) download
copy 
  1. ///HEADERS
  2. #include    <bits/stdc++.h>
  3. ///PREPROCESSORS
  4. #define     ll              long long int
  5. #define     ull             unsigned ll
  6. #define     vii             vector<int>
  7. #define     vll             vector<ll>
  8. #define     pb              push_back
  9. #define     LIM             100000
  10. #define     MOD             1000000007
  11. #define     MAX             10000000
  12. #define     pi              acos(-1)
  13. #define     segVar          int lft = node << 1 , rgt = (node << 1) + 1 , md = (st+ed) >> 1;
  14. #define     pii             pair<int,int>
  15. #define     mpr             make_pair
  16. #define     EPS             1e-9
  17. #define     sqr(x)          ((x)*(x))
  18. #define     gamma           0.5772156649
  19. #define     harm(x)         log(x) + gamma + 1.0/(2*x) - 1.0/(12*sqr(x))
  20. #define     joshephus(n,k)  j(int n, int k) {ll res = 1; for(ll i=2; i<=n; i++) res = (res+k-1) % i + 1; return res;}
  21.  
  22. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
  23.  
  24. ///IMPORTANT EQUATIONS
  25. ///STARS AND BARS   : (n+k-1)C(k-1)
  26. ///STIRLING TWO     : F(n,k) = F(n-1,k-1) + k*(n-1,k); F(n,1) = 1 , F(n,n) = 1;
  27. ///STIRLING ONE     : F(n,k) = F(n-1,k-1) + (n-1)*(n-1,k); F(n,1) = (n-1)! , F(n,n) = 1;
  28. ///CATALAN NUMBER   : Cat(n) = Comb(2n,n) - Comb(2n,n-1) = Comb(2n,n)/(n+1);
  29.  
  30. using namespace std;
  31.  
  32. struct info{
  33.     char cmd;
  34.     int x,y,z;
  35.     info() {x = y = z = 0;}
  36.     info(char c, int xx, int yy = 0, int zz = 0) {
  37.         cmd = c; x = xx; y = yy; z = zz;
  38.     }
  39. };
  40.  
  41. int n,q,v, mxx,seg;
  42. int a[LIM+10], val[2*LIM+10];
  43. info qry[LIM + 10];
  44. map<int, int> mp;
  45. int BIT[400][LIM+100];
  46.  
  47. void update(int node, int pos, int val) {
  48.     while(node <= seg+1) {
  49.         int tp = pos;
  50.         while(tp <= mxx) {
  51.             BIT[node][tp] += val;
  52.             tp += (tp & -tp);
  53.         }
  54.         node += (node & -node);
  55.     }
  56. }
  57. int query(int node, int pos) {
  58.     int ans = 0;
  59.     while(node > 0) {
  60.         int tp = pos;
  61.         while(tp > 0) {
  62.             ans += BIT[node][tp];
  63.             tp -= (tp & -tp);
  64.         }
  65.         node -= (node & -node);
  66.     }
  67.     return ans;
  68. }
  69.  
  70. int f(int x, int y, int z) {
  71.     int ans = 0;
  72.     while(x%seg) {
  73.         if(a[x] <= z) ans++;
  74.         x++;
  75.     }
  76.     while(y%seg != seg-1) {
  77.         if(a[x] <= z) ans++;
  78.         y--;
  79.     }
  80.     ans += query(y/seg+1, mp[z]) - (query(x/seg, mp[z]));
  81.     return ans;
  82. }
  83.  
  84. int main() {
  85.  
  86. //    freopen("i.txt", "r", stdin);
  87. //    freopen("o.txt", "w",stdout);
  88.  
  89.     scanf("%d %d", &n,&q);
  90.     for(int i=0; i<n; i++) scanf("%d", &a[i]) , val[v++] = a[i] ;
  91.     for(int i=0; i<q; i++) {
  92.         char c; int x,y,z;
  93.         getchar();
  94.         scanf("%c", &c);
  95.         if(c == 'M') {
  96.             scanf("%d %d", &x,&y);
  97.             x--;
  98.             val[v++] = y;
  99.             qry[i] = info(c, x, y);
  100.         }
  101.         else {
  102.             scanf("%d %d %d", &x,&y,&z);
  103.             val[v++] = z;
  104.             x--; y--;
  105.             qry[i] = info(c,x,y,z);
  106.         }
  107.     }
  108.     sort(val, val+v);
  109.     for(int i=0; i<v; i++) if(!mp[ val[i] ]) mp[ val[i] ] = ++mxx;
  110.  
  111.     seg = sqrt(n);
  112.     for(int i=0; i<n; i++) update(i/seg+1, mp[ a[i] ], 1);
  113.  
  114.     for(int i=0; i<q; i++) {
  115.         char c; int x,y,z;
  116.         c = qry[i].cmd ; x = qry[i].x; y = qry[i].y; z = qry[i].z;
  117.         if(c == 'M') {
  118.             update(x/seg+1, mp[ a[x] ], -1);
  119.             a[x] = y;
  120.             update(x/seg+1, mp[ y ], 1);
  121.         }
  122.         else printf("%d\n", f(x,y,z));
  123.     }
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0s 174400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MKJHKj
language:
C++14 (gcc 8.3)
created:
7 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!