Guest User

K-Query II

a guest
Jun 10th, 2015
1,163
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define all(x) x.begin(), x.end()
  3. #define f(i,a,b) for(int i = (a); i <= (b); i++)
  4.  
  5. const int BLOCK = 506;
  6. int A[30005], N, Q, T[180][10005];
  7. using namespace std;
  8.  
  9. void update(int t, int x, int v)
  10. {
  11.     while(x > 0)
  12.     {
  13.         T[t][x] += v;
  14.         x -= x&-x;
  15.     }
  16. }
  17.  
  18. int query(int t, int x)
  19. {
  20.     int ret = 0;
  21.     while(x <= 10000)
  22.     {
  23.         ret += T[t][x];
  24.         x += x&-x;
  25.     }
  26.     return ret;
  27. }
  28.  
  29. int main()
  30. {
  31.     cin >> N;
  32.  
  33.     f(i,1,N)
  34.     {
  35.         scanf("%d", &A[i]);
  36.         update(i/BLOCK,A[i],1);
  37.     }
  38.  
  39.     cin >> Q;
  40.  
  41.     while(Q--)
  42.     {
  43.         int t;
  44.         scanf("%d", &t);
  45.  
  46.         if(!t)
  47.         {
  48.             int x, v;
  49.             scanf("%d %d", &x, &v);
  50.             update(x/BLOCK,A[x],-1);
  51.             A[x] = v;
  52.             update(x/BLOCK,v,1);
  53.         }
  54.         else
  55.         {
  56.             int l,r,k;
  57.             scanf("%d %d %d", &l, &r, &k);
  58.             int ans = 0;
  59.             while(l%BLOCK != 0 && l <= r) ans += A[l++] > k;
  60.             while(r%BLOCK != BLOCK-1 && l <= r) ans += A[r--] > k;
  61.             if(r>l)
  62.             {
  63.                 int bl = l/BLOCK;
  64.                 int br = r/BLOCK;
  65.                 f(b,bl,br) ans += query(b,k+1);
  66.             }
  67.             printf("%d\n", ans);
  68.         }
  69.     }
  70. }
RAW Paste Data