fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define mp make_pair
  6. #define Fast_IO ios::sync_with_stdio(false);
  7. #define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
  8. //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  9. #define fir first
  10. #define sec second
  11. #define mod 998244353
  12. #define int long long
  13. #define inf 0x3f3f3f3f
  14. #define INF 0x3f3f3f3f3f3f3f3f
  15. inline int read()
  16. {
  17. 	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
  18. 	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
  19. 	if(nega==-1) return -ans;
  20. 	return ans;
  21. }
  22. typedef pair<int,int> pii;
  23. void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%lld%c",x[i]," \n"[i==(int)x.size()-1]);}
  24. #define N 100005
  25. int a[N],n,Q;
  26. struct Node
  27. {
  28. 	int pos,pre,cnt;
  29. 	Node(int a=0,int b=0,int c=0) {pos=a,pre=b,cnt=c;}
  30. };
  31. struct SMT
  32. {
  33. 	#define ls (u<<1)
  34. 	#define rs (u<<1|1)
  35. 	#define mid ((l+r)/2)
  36. 	vector<Node> vl[N*4],vr[N*4];
  37. 	pair<vector<Node>,vector<Node>> merge(int l1,int r1,int l2,int r2,vector<Node> lpre,vector<Node> lsuf,vector<Node> rpre,vector<Node> rsuf)
  38. 	{
  39. 		vector<Node> pre,suf;
  40. 		pre=lpre,suf=rsuf;
  41. 		pre[(int)pre.size()-1].cnt=0;
  42. 		suf[(int)suf.size()-1].cnt=0;
  43. 		int lsum=pre.back().pre,rsum=suf.back().pre;
  44. 		if(lsum>=a[l2]) pre.pop_back();
  45. 		if(rsum>=a[r1]) suf.pop_back();
  46. 		for(auto [pos,_pre,cnt]:rpre)
  47. 		{
  48. 			if(pos==r2||(lsum+_pre<a[pos+1])) pre.eb(pos,_pre+lsum,0);
  49. 		}
  50. 		for(auto [pos,_pre,cnt]:lsuf)
  51. 		{
  52. 			if(pos==l1||(rsum+_pre<a[pos-1])) suf.eb(pos,_pre+rsum,0);
  53. 		}
  54. 		{ // get lsuf jumps
  55. 			vector<int> jmpr(lsuf.size()); int curpos=0;
  56. 			for(int i=0;i<(int)lsuf.size();i++)
  57. 			{
  58. 				auto [pos,pre,cnt]=lsuf[i];
  59. 				if(pre<a[r1+1]) {jmpr[i]=-1; continue;}
  60. 				while(curpos+1<(int)rpre.size())
  61. 				{
  62. 					if(pre+rpre[curpos].pre>=a[rpre[curpos].pos+1]) curpos++;
  63. 					else break;
  64. 				}
  65. 				jmpr[i]=curpos;
  66. 			}
  67. 			vector<int> tor(lsuf.size()),jmpl(lsuf.size());
  68. 			for(int i=(int)lsuf.size()-1;i>=0;i--)
  69. 			{
  70. 				auto [pos,pre,cnt]=lsuf[i];
  71. 				if(i==(int)lsuf.size()-1) tor[i]=jmpr[i],jmpl[i]=i;
  72. 				else
  73. 				{
  74. 					int v=pre;
  75. 					if(jmpr[i]!=-1) v+=rpre[jmpr[i]].pre;
  76. 					if(v>=a[pos-1]) tor[i]=tor[i+1],jmpl[i]=jmpl[i+1];
  77. 					else tor[i]=jmpr[i],jmpl[i]=i;
  78. 				}
  79. 			}
  80. 			curpos=(int)pre.size()-1;
  81. 			for(int i=(int)lsuf.size()-1;i>=0;i--)
  82. 			{
  83. 				if(jmpl[i]==(int)lsuf.size()-1)
  84. 				{
  85. 					int nedpos;
  86. 					if(tor[i]==-1) nedpos=r1;
  87. 					else nedpos=rpre[tor[i]].pos;
  88. 					while(pre[curpos].pos!=nedpos) curpos--;
  89. 					pre[curpos].cnt+=lsuf[i].cnt;
  90. 				}
  91. 			}
  92. 			curpos=(int)suf.size()-1;
  93. 			for(int i=(int)lsuf.size()-1;i>=0;i--)
  94. 			{
  95. 				if(tor[i]==(int)rpre.size()-1)
  96. 				{
  97. 					int nedpos=lsuf[jmpl[i]].pos;
  98. 					while(suf[curpos].pos!=nedpos) curpos--;
  99. 					suf[curpos].cnt+=lsuf[i].cnt;
  100. 				}
  101. 			}
  102. 			// if(l1==1&&r2==5)
  103. 			// {
  104. 				// printf("***\n");
  105. 				// print(tor),print(jmpl),print(jmpr);
  106. 				// for(auto [x,y,z]:suf) printf("%d %d %d\n",x,y,z);
  107. 			// }
  108. 		}
  109. 		{ // get rpre jumps
  110. 			vector<int> jmpl(rpre.size()); int curpos=0;
  111. 			for(int i=0;i<(int)rpre.size();i++)
  112. 			{
  113. 				auto [pos,pre,cnt]=rpre[i];
  114. 				if(pre<a[r1]) {jmpl[i]=-1; continue;}
  115. 				while(curpos+1<(int)lsuf.size())
  116. 				{
  117. 					if(pre+lsuf[curpos].pre>=a[lsuf[curpos].pos-1]) curpos++;
  118. 					else break;
  119. 				}
  120. 				jmpl[i]=curpos;
  121. 			}
  122. 			vector<int> tol(rpre.size()),jmpr(rpre.size());
  123. 			for(int i=(int)rpre.size()-1;i>=0;i--)
  124. 			{
  125. 				auto [pos,pre,cnt]=rpre[i];
  126. 				if(i==(int)rpre.size()-1) tol[i]=jmpl[i],jmpr[i]=i;
  127. 				else
  128. 				{
  129. 					int v=pre;
  130. 					if(jmpl[i]!=-1) v+=lsuf[jmpl[i]].pre;
  131. 					if(v>=a[pos+1]) tol[i]=tol[i+1],jmpr[i]=jmpr[i+1];
  132. 					else tol[i]=jmpl[i],jmpr[i]=i;
  133. 				}
  134. 			}
  135. 			curpos=(int)suf.size()-1;
  136. 			for(int i=(int)rpre.size()-1;i>=0;i--)
  137. 			{
  138. 				if(jmpr[i]==(int)rpre.size()-1)
  139. 				{
  140. 					int nedpos;
  141. 					if(tol[i]==-1) nedpos=l2;
  142. 					else nedpos=lsuf[tol[i]].pos;
  143. 					while(suf[curpos].pos!=nedpos) curpos--;
  144. 					suf[curpos].cnt+=rpre[i].cnt;
  145. 				}
  146. 			}
  147. 			curpos=(int)pre.size()-1;
  148. 			for(int i=(int)rpre.size()-1;i>=0;i--)
  149. 			{
  150. 				if(tol[i]==(int)lsuf.size()-1)
  151. 				{
  152. 					int nedpos=rpre[jmpr[i]].pos;
  153. 					while(pre[curpos].pos!=nedpos) curpos--;
  154. 					pre[curpos].cnt+=rpre[i].cnt;
  155. 				}
  156. 			}
  157. 		}
  158. 		return {pre,suf};
  159. 	}
  160. 	pair<vector<Node>,vector<Node>> getone(int pos)
  161. 	{
  162. 		vector<Node> v;
  163. 		v.eb(pos,a[pos],1);
  164. 		return {v,v};
  165. 	}
  166. 	void build(int u,int l,int r)
  167. 	{
  168. 		if(l==r)
  169. 		{
  170. 			tie(vl[u],vr[u])=getone(l);
  171. 			return ;
  172. 		}
  173. 		build(ls,l,mid),build(rs,mid+1,r);
  174. 		tie(vl[u],vr[u])=merge(l,mid,mid+1,r,vl[ls],vr[ls],vl[rs],vr[rs]);
  175. 		// printf("^ %d %d %d :\n",u,l,r);
  176. 		// for(auto [x,y,z]:vl[u]) printf("%d %d %d\n",x,y,z);
  177. 		// cout<<"\n";
  178. 		// for(auto [x,y,z]:vr[u]) printf("%d %d %d\n",x,y,z);
  179. 		// cout<<"\n";
  180. 	}
  181. 	void update(int u,int l,int r,int pos)
  182. 	{
  183. 		if(l==r)
  184. 		{
  185. 			tie(vl[u],vr[u])=getone(l);
  186. 			return ;
  187. 		}
  188. 		if(pos<=mid) update(ls,l,mid,pos);
  189. 		else update(rs,mid+1,r,pos);
  190. 		tie(vl[u],vr[u])=merge(l,mid,mid+1,r,vl[ls],vr[ls],vl[rs],vr[rs]);
  191. 	}
  192. 	pair<vector<Node>,vector<Node>> query(int u,int l,int r,int L,int R)
  193. 	{
  194. 		if(L==l&&r==R) return {vl[u],vr[u]};
  195. 		if(mid>=L&&mid<R)
  196. 		{
  197. 			auto [lpre,lsuf]=query(ls,l,mid,max(l,L),min(mid,R));
  198. 			auto [rpre,rsuf]=query(rs,mid+1,r,max(mid+1,L),min(r,R));
  199. 			return merge(L,mid,mid+1,R,lpre,lsuf,rpre,rsuf);
  200. 		}
  201. 		else if(mid>=L) return query(ls,l,mid,max(l,L),min(mid,R));
  202. 		else if(mid<R) return query(rs,mid+1,r,max(mid+1,L),min(r,R));
  203. 		else assert(0);
  204. 	}
  205. }smt;
  206. signed main()
  207. {
  208. 	cin>>n;
  209. 	for(int i=1;i<=n;i++) a[i]=read();
  210. 	smt.build(1,1,n);
  211. 	cin>>Q;
  212. 	while(Q--)
  213. 	{
  214. 		int op=read(),l=read(),r=read();
  215. 		if(op==1) a[l]=r,smt.update(1,1,n,l);
  216. 		else
  217. 		{
  218. 			auto [pre,suf]=smt.query(1,1,n,l,r);
  219. 			printf("%d\n",suf.back().cnt);
  220. 		}
  221. 	}
  222. 	return 0;
  223. }
  224.  
  225.  
Runtime error #stdin #stdout 0.65s 2095820KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/U3hIhf
language:
C++14 (gcc 8.3)
created:
2 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!