fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  6.  
  7. typedef long long ll;
  8.  
  9. struct node{
  10.     ll val,size,_max,prior;
  11.     node *l,*r;
  12. };
  13.  
  14. typedef node* pnode;
  15.  
  16. ll sz(pnode t){
  17.     return (t)?t->size:0;
  18. }
  19.  
  20.  
  21.  
  22.  
  23. ll rmax(pnode t){
  24.     return (t)?t->_max:-2e9;
  25. }
  26.  
  27. void operation(pnode t){
  28.     if(!t)  return;
  29.     t->size = sz(t->l)+1+sz(t->r);
  30.     t->_max = max(t->val,max(rmax(t->l),rmax(t->r)));
  31. }
  32.  
  33.  
  34. void split(pnode t, pnode& l, pnode& r, ll pos, ll add = 0){
  35.     if(!t){
  36.         l = r = NULL;
  37.         return;
  38.     }
  39.     ll curr_pos = add+sz(t->l);
  40.     if(curr_pos <= pos){
  41.         split(t->r,t->r,r,pos,curr_pos+1);
  42.         l = t;
  43.     }else{
  44.         split(t->l,l,t->l,pos,add);
  45.         r = t;
  46.     }
  47.     operation(t);
  48. }
  49.  
  50.  
  51. void merge(pnode& t, pnode l, pnode r){
  52.     if(!l || !r){
  53.         t=l?l:r;
  54.         return;
  55.     }
  56.     if(l->prior > r->prior){
  57.         merge(l->r,l->r,r);
  58.         t = l;
  59.     }else{
  60.         merge(r->l,l,r->l);
  61.         t = r;
  62.     }
  63.     operation(t);
  64. }
  65.  
  66.  
  67. pnode init(ll val){
  68.     pnode p = (pnode)malloc(sizeof(node));
  69.     p->val=p->_max = val;
  70.     p->prior = rand();
  71.     p->size = 1;
  72.     p->l=p->r=NULL;
  73.     return p;
  74. }
  75.  
  76.  
  77. pnode insert(pnode t, ll pos, ll val){
  78.     pnode L,mid,R;
  79.     split(t,L,mid,pos-1);
  80.     pnode p = init(val);
  81.     merge(R,L,p);
  82.     merge(t,R,mid);
  83.     return t;
  84. }
  85.  
  86. ll query(pnode t, ll l, ll r){
  87.     pnode L,mid,R;
  88.     split(t,L,mid,l-1);
  89.     split(mid,t,R,r-l);
  90.     ll ans = t->_max;
  91.     merge(mid,L,t);
  92.     merge(t,mid,R);
  93.     return ans;
  94. }
  95.  
  96.  
  97. int main(){
  98.     boost;
  99.     ll T,N,i,j,k,M;
  100.     pnode t = NULL;
  101.     char op[2];
  102. 	ll x, y, q;
  103. 	//freopen("in.txt", "r", stdin);
  104. 	scanf("%lld", &q);
  105. 	while(q--) {
  106. 		scanf("%s %lld %lld", op, &x, &y);
  107. 		if(*op == 'Q') printf("%lld\n", query(t,x-1,y-1));
  108. 		else t = insert(t, y-1, x);
  109. 	}
  110. 	return 0;
  111. }
  112.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
10
A 1 1
A 2 2
Q 1 2
A 3 1
A 4 3
Q 2 4
A 5 2
Q 2 3
A 6 3
Q 1 4
stdout
copy 
2
4
5
6
https://ideone.com/rYEpP8
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!