fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sz(x) (int)x.size()
  5. typedef long long int ll;
  6.  
  7. const ll N = 5e5+20, MOD = 1e9+7;
  8.  
  9. ll n,q,l,r,tree[6*N],lazy[6*N],a[N];
  10. set<ll> in,out;
  11. set<ll>::iterator itr;
  12.  
  13. void lazyUpd(ll node,ll st,ll en,ll l,ll r,ll val){
  14.     if(lazy[node]){
  15.        tree[node]+=(en-st+1)*lazy[node];
  16.        if(st!=en)
  17.        {
  18.            lazy[2*node]+=lazy[node];
  19.            lazy[2*node+1]+=lazy[node];
  20.        }
  21.        lazy[node]=0;
  22.     }
  23.  
  24.     if(st>en || l > en || r < st)
  25.         return ;
  26.     if(l<=st && en<=r)
  27.     {
  28.         tree[node]+=(en-st+1)*val;
  29.         if(st!=en)
  30.         {
  31.             lazy[2*node]+=val;
  32.             lazy[2*node+1]+=val;
  33.         }
  34.         return ;
  35.     }
  36.     ll mid=(st+en)/2;
  37.     lazyUpd(2*node,st,mid,l,r,val);
  38.     lazyUpd(2*node+1,mid+1,en,l,r,val);
  39.     tree[node]=tree[2*node]+tree[2*node+1];
  40. }
  41.  
  42. ll lazyQuery(ll node,ll st,ll en,ll l,ll r)
  43. {
  44.     if(st>en || l > en || r < st)
  45.         return 0;
  46.     if(lazy[node])
  47.     {
  48.         tree[node]+=(en-st+1)*lazy[node];
  49.         if(st!=en)
  50.         {
  51.             lazy[2*node]+=lazy[node];
  52.             lazy[2*node+1]+=lazy[node];
  53.         }
  54.         lazy[node]=0;
  55.     }
  56.     if(st>=l && r>=en)
  57.         return tree[node];
  58.     ll mid=(st+en)/2;
  59.     ll p1=lazyQuery(2*node,st,mid,l,r);
  60.     ll p2=lazyQuery(2*node+1,mid+1,en,l,r);
  61.     return (p1+p2);
  62. }
  63.  
  64. void cal(ll *cur,ll *aft,ll *bef,set<ll> s, ll y){
  65. 	itr=s.upper_bound(y);
  66. 	if(itr==s.end())
  67. 		(*aft)=n+1;
  68. 	else
  69. 		(*aft)=(*itr);
  70. 	itr=s.lower_bound(y);
  71. 	if(itr==s.begin())
  72. 		(*bef)=0;
  73. 	else{
  74. 		itr--;
  75. 		(*bef)=(*itr);
  76. 	}
  77. 	return ;
  78. }
  79. void bhencho(ll pr,ll y, ll z){
  80. 	ll ba,bp,bc=-1,mc=-1,ma,mp,cur,nxt;
  81. 	cal(&mc,&ma,&mp,in,y);
  82. 	cal(&bc,&ba,&bp,out,y);
  83. 	if(z<l){
  84. 		if(ba>ma)
  85. 			nxt=ba-ma;
  86. 		else
  87. 			nxt=0;
  88. 		cur=ba-y;
  89. 		if(pr>=l && pr<=r){
  90. 			lazyUpd(1,1,n,max(mp+1,bp+1),y,nxt-cur);
  91. 			in.erase(in.find(y));
  92. 		}else if(pr>r){
  93. 			if(mp>bp)
  94. 				lazyUpd(1,1,n,bp+1,mp,ba-y);
  95. 			lazyUpd(1,1,n,max(bp+1,mp+1),y,nxt);
  96. 			out.erase(out.find(y));
  97. 		}
  98. 	}else if(z>=l && z<=r){
  99. 		in.insert(y);
  100. 		if(ba>ma)
  101. 			cur=ba-ma;
  102. 		else
  103. 			cur=0;
  104. 		if(pr<l){
  105. 			lazyUpd(1,1,n,max(mp+1,bp+1),y,(ba-y)-cur);
  106. 		}else if(pr>r){
  107. 			lazyUpd(1,1,n,bp+1,y,ba-y);
  108. 			out.erase(out.find(y));
  109. 		}
  110. 	}else if(z>r){
  111. 		out.insert(y);
  112. 		// cur=ba-y;
  113. 		if(pr<l){
  114. 			if(ba>ma)
  115. 				cur=ba-ma;
  116. 			else
  117. 				cur=0;
  118. 			if(mp>bp)
  119. 				lazyUpd(1,1,n,bp+1,mp,y-ba);
  120. 			lazyUpd(1,1,n,max(bp+1,mp+1),y,-cur);
  121. 		}else if(pr>=l && pr<=r){
  122. 			cur=ba-y;
  123. 			lazyUpd(1,1,n,bp+1,y,-cur);
  124. 			in.erase(in.find(y));
  125. 		}
  126. 	}
  127. }
  128.  
  129. ll firse(ll pr,ll y, ll z){ // calculate using z...
  130. 	ll ba,bp,bc=-1,mc=-1,ma,mp,cur,nxt;
  131. 	cal(&mc,&ma,&mp,in,z);
  132. 	cal(&bc,&ba,&bp,out,z);
  133. 	if(pr>r){
  134. 		return lazyQuery(1,1,n,y,z);
  135. 	}else if(pr>=l && pr<=r){
  136. 		ll anss=0;
  137. 		if(bp>=y){
  138. 			anss+=lazyQuery(1,1,n,y,z);
  139. 			anss-=/*lazyQuery(1,1,n,bp+1,z)*/((z-bp)*(ba-z-1));
  140. 			return anss;
  141. 		}else{
  142. 			anss+=lazyQuery(1,1,n,y,z);
  143. 			anss-=((z-y+1)*(ba-z-1));
  144. 			return anss;
  145. 		}
  146. 	}else if(pr<l){
  147. 		ll anss=0;
  148. 		if(bp>=y){
  149. 			if(mp<bp)
  150. 				return lazyQuery(1,1,n,y,bp);
  151. 			anss=lazyQuery(1,1,n,y,mp)-((mp-bp)*(ba-z-1));
  152. 			return anss;
  153. 		}else{
  154. 			if(mp<y)
  155. 				return anss;
  156. 			anss+=lazyQuery(1,1,n,y,mp)-((mp-y+1)*(ba-z-1));
  157. 			return anss;
  158. 		}
  159. 	}
  160. }
  161.  
  162. int main()
  163. {
  164.     ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  165.     cin >> n >> q >> l >> r;
  166.     while(q--){
  167.     	int x;
  168.     	ll pr;
  169.     	cin >> x;
  170.     	if(x==1){
  171.     		ll y,z;
  172.     		cin >> y >> z;
  173.     		pr=a[y];
  174.     		a[y]=z;
  175.     		bhencho(pr,y,z);
  176.     	}else{
  177.     		ll y,z;
  178.     		cin >> y >> z;
  179.     		pr=a[z];
  180.     		cout << firse(pr,y,z) << endl;
  181.     	}
  182.     }
  183.     return 0;
  184. }
Success #stdin #stdout 0s 66048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yDX2FD
language:
C++ (gcc 8.3)
created:
6 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!