fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define rep(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
  3. #define MAXN 101010
  4. using namespace std;
  5.  
  6. struct Node{
  7. 	int qt, l, r;
  8. 	Node():qt(0),l(0),r(0){}
  9. }st[10101010];
  10. int ptr = 1;
  11.  
  12. int upd(int node, int l, int r, int p, int v){
  13. 	if(p < l || r < p) return node; 
  14. 	if(l == r){
  15. 		st[ptr].qt = st[node].qt + v, st[ptr].l = st[node].l, st[ptr].r = st[node].r;
  16. 		return ptr++;
  17. 	}
  18. 	int mid = (l+r)>>1, fe, fd;
  19. 	fe = upd(st[node].l, l, mid, p, v);
  20. 	fd = upd(st[node].r, mid+1,r,p, v);
  21. 	st[ptr].qt = st[fe].qt + st[fd].qt, st[ptr].l = fe, st[ptr].r = fd;
  22. 	return ptr++;
  23. }
  24.  
  25. int query(int a, int b, int l, int r, int k){
  26. 	if(l==r) return l;
  27. 	int mid = (l+r)>>1;
  28. 	int tesq = st[st[b].l].qt - st[st[a].l].qt;
  29. 	if(tesq >= k) return query(st[a].l, st[b].l, l, mid, k);
  30. 	return query(st[a].r, st[b].r, mid+1, r, k-tesq);
  31. }
  32.  
  33. int n, m, vet[MAXN], aux[MAXN], tree[MAXN];
  34.  
  35. int main(){
  36. 	scanf("%d%d", &n, &m);
  37. 	rep(i,1,n+1) scanf("%d", vet+i), aux[i] = vet[i];
  38. 	sort(aux+1,aux+n+1);
  39. 	rep(i,1,n+1){
  40. 		vet[i] = lower_bound(aux+1, aux+n+1, vet[i]) - aux;
  41. 		tree[i] = upd(tree[i-1], 1, n, vet[i], 1);
  42. 	}
  43. 	while(m--){
  44. 		char op;
  45. 		scanf(" %c", &op);
  46. 		if(op == 'Q'){
  47. 			int a, b, k;
  48. 			scanf("%d%d%d", &a, &b, &k);
  49. 			printf("%d\n", aux[query(tree[a-1], tree[b], 1, n, k)]);
  50. 		}else{
  51. 			int p;
  52. 			scanf("%d", &p);
  53. 			tree[p] = upd(tree[p], 1, n, vet[p],-1);
  54. 			swap(vet[p], vet[p+1]);
  55. 			tree[p] = upd(tree[p], 1, n, vet[p], 1);
  56. 		}
  57. 	}
  58. }
Success #stdin #stdout 0.02s 123008KB
comments (?)
stdin
copy 
4 3
33333333 22222222 44444444 11111111
Q 3 3 1
S 1
Q 2 4 2
stdout
copy 
44444444
33333333
https://ideone.com/HdOhu1
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!