fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 1e5 + 5;
  8.  
  9. struct item{
  10.   int x, pos;
  11. } A[MAXN];
  12.  
  13. int bit[MAXN], idx[MAXN], revidx[MAXN], N, Q, j, k;      
  14.  
  15. void add(int pos, int v){ for(; pos<=N; pos+=(pos & -pos)) bit[pos] += v; }
  16.  
  17. int query(int pos){
  18.   int res = 0;
  19.   for(; pos>0; pos-=(pos & -pos)) res += bit[pos];
  20.   return res;
  21. }
  22.  
  23. int LO(int x){
  24.   int lo = 0, hi = N, mid, cur;
  25.   if(query(N) < x) return N + 1;
  26.   while(lo < hi - 1) {
  27.     mid = (lo + hi)>>1;
  28.     cur = query(mid);
  29.     if(cur >= x) hi = mid;
  30.     else lo = mid;
  31.   }
  32.   return hi;
  33. }
  34.  
  35. int comp(item a, item b) {
  36.   return a.x < b.x;
  37. }
  38.  
  39. int main(){
  40.   scanf("%d %d", &N, &Q);
  41.   for(int i=1; i<=N; ++i){
  42.     scanf("%d", &A[i].x);
  43.     A[i].pos = i;
  44.   }
  45.   sort(A + 1, A + N + 1, comp);
  46.   for(int i=1; i<=N; ++i){
  47.     idx[A[i].pos] = i, revidx[i] = A[i].pos;
  48.     add(i, A[i].x - A[i-1].x);
  49.   } 
  50.   while(Q--){
  51.     scanf("%d %d", &k, &j);
  52.     if(k == 1){
  53.       int prev = j, cur, p;
  54.       j = idx[j];
  55.       cur = LO(query(j) + 1) - 1;
  56.       add(cur, 1); add(cur + 1, -1);
  57.       p = revidx[cur], idx[prev] = cur, revidx[cur] = prev;
  58.       idx[p] = j, revidx[j] = p;
  59.     }
  60.     else if(k == 2) printf("%d\n", N - LO(j) + 1);
  61.     else add(LO(j), -1);
  62.   }
  63.   return 0;
  64. }
Success #stdin #stdout 0s 5424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MBPXXz
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!