fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define int long long
  5. #define int long long
  6. struct SegmentTree{
  7. private:
  8. int sz=1,skip=0;
  9. vector<int>seg,lazy;
  10. void propegate(int l,int r,int node)
  11. {
  12. if(lazy[node]==0)return;
  13. if(l!=r)
  14. {
  15. lazy[2*node+1]+=lazy[node];
  16. lazy[2*node+2]+=lazy[node];
  17. }
  18. int len=r-l+1;
  19. seg[node]+=len*lazy[node];
  20. lazy[node]=0;
  21. }
  22. void update(int l,int r,int node,int lx,int rx,int val)
  23. {
  24. propegate(l,r,node);
  25. if(l>rx||r<lx)
  26. {
  27. return;
  28. }
  29. if(l>=lx&&r<=rx)
  30. {
  31. lazy[node]+=val;
  32. propegate(l,r,node);
  33. return;
  34. }
  35. int mid=l+r>>1;
  36. update(l,mid,2*node+1,lx,rx,val);
  37. update(mid+1,r,2*node+2,lx,rx,val);
  38. seg[node]=seg[2*node+1]+seg[2*node+2];
  39. }
  40. int query(int l,int r,int node,int lx,int rx)
  41. {
  42. propegate(l,r,node);
  43. if(l>=lx&&r<=rx)
  44. {
  45. return seg[node];
  46. }
  47. if(l>rx||r<lx)
  48. {
  49. return skip;
  50. }
  51. int mid=l+r>>1;
  52. return query(l,mid,2*node+1,lx,rx)+query(mid+1,r,2*node+2,lx,rx);
  53. }
  54. public:
  55. void update(int l,int r,int val)
  56. {
  57. update(0,sz-1,0,l,r,val);
  58. }
  59. int query(int l,int r)
  60. {
  61. return query(0,sz-1,0,l,r);
  62. }
  63. SegmentTree(int n){
  64. while(sz<=n)sz*=2;
  65. seg=vector<int>(sz*2,0);
  66. lazy=vector<int>(sz*2,0);
  67. }
  68. };
  69. struct SegmentTreeBeats{
  70. private:
  71. #define L 2*node+1
  72. #define R 2*node+2
  73. #define mid (l+r>>1)
  74. #define inf 1e15+5
  75. struct Node{
  76. int sum,mx,secMx,mxCnt,mn,mnCnt,secMn,lazyAdd,lazySet;
  77. Node(int summ,int mxx,int secMxx,int mxCntt,int mnn,int secMnn,int mnCntt,int add=0,int set=-1)
  78. :sum(summ),mx(mxx),secMx(secMxx),mxCnt(mxCntt),
  79. mn(mnn),secMn(secMnn),mnCnt(mnCntt),
  80. lazyAdd(add),lazySet(set){}
  81. };
  82. int sz;vector<Node>seg;
  83. Node merge(Node&a,Node&b)
  84. {
  85. Node ret(0,-inf,-inf,0,inf,inf,0,0,-1);
  86. ret.sum=a.sum+b.sum;
  87. ret.mx=max(a.mx,b.mx);// max
  88. ret.secMx=max(a.secMx,b.secMx);
  89. if(ret.mx==a.mx) ret.mxCnt+=a.mxCnt;
  90. else ret.secMx=max(ret.secMx,a.mx);
  91. if(ret.mx==b.mx) ret.mxCnt+=b.mxCnt;
  92. else ret.secMx=max(ret.secMx,b.mx);
  93. ret.mn=min(a.mn,b.mn);// min
  94. ret.secMn=min(a.secMn,b.secMn);
  95. if(ret.mn==a.mn) ret.mnCnt+=a.mnCnt;
  96. else ret.secMn=min(ret.secMn,a.mn);
  97. if(ret.mn==b.mn) ret.mnCnt+=b.mnCnt;
  98. else ret.secMn=min(ret.secMn,b.mn);
  99. return ret;
  100. }
  101. void pushSet(int l,int r,int node,int val)
  102. {
  103. seg[node]=Node(val*(r-l+1),val,-inf,r-l+1,val,inf,r-l+1,0,val);
  104. }
  105. void pushMin(int l,int r,int node,int mn)
  106. {
  107. if(seg[node].mn>=mn)
  108. {
  109. pushSet(l,r,node,mn);
  110. return;
  111. }
  112. if(seg[node].mx>mn)
  113. {
  114. if(seg[node].secMn==seg[node].mx) seg[node].secMn=mn;
  115. int val=seg[node].mx-mn;
  116. seg[node].sum-=val*seg[node].mxCnt;
  117. seg[node].mx=mn;
  118. }
  119. }
  120. void pushMax(int l,int r,int node,int mx)
  121. {
  122. if(seg[node].mx<=mx)
  123. {
  124. pushSet(l,r,node,mx);
  125. return;
  126. }
  127. if(seg[node].mn<mx)
  128. {
  129. if(seg[node].secMx==seg[node].mn) seg[node].secMx=mx;
  130. int val=mx-seg[node].mn;
  131. seg[node].sum+=val*seg[node].mnCnt;
  132. seg[node].mn=mx;
  133. }
  134. }
  135. void pushAdd(int l,int r,int node,int val)
  136. {
  137. if(seg[node].mx==seg[node].mn)
  138. {
  139. pushSet(l,r,node,seg[node].mn+val);
  140. return;
  141. }
  142. seg[node].mx+=val;
  143. if(seg[node].secMx!=-inf) seg[node].secMx+=val;
  144. seg[node].mn+=val;
  145. if(seg[node].secMn!=inf) seg[node].secMn+=val;
  146. seg[node].sum+=(r-l+1)*val;
  147. seg[node].lazyAdd+=val;
  148. }
  149. void propegate(int l,int r,int node)
  150. {
  151. if(l==r) return;
  152. if(seg[node].lazySet!=-1)
  153. {
  154. pushSet(l,mid,L,seg[node].lazySet);
  155. pushSet(mid+1,r,R,seg[node].lazySet);
  156. seg[node].lazySet=-1;
  157. }
  158. else
  159. {
  160. pushAdd(l,mid,L,seg[node].lazyAdd);
  161. pushAdd(mid+1,r,R,seg[node].lazyAdd);
  162. seg[node].lazyAdd=0;
  163. pushMin(l,mid,L,seg[node].mx);
  164. pushMin(mid+1,r,R,seg[node].mx);
  165. pushMax(l,mid,L,seg[node].mn);
  166. pushMax(mid+1,r,R,seg[node].mn);
  167. }
  168. }
  169. void build(int l,int r,int node,vector<int>&v)
  170. {
  171. if(l==r)
  172. {
  173. if(l<v.size())
  174. {
  175. seg[node]=Node(v[l],v[l],-inf,1,v[l],inf,1);
  176. }
  177. return;
  178. }
  179. build(l,mid,L,v);
  180. build(mid+1,r,R,v);
  181. seg[node]= merge(seg[L],seg[R]);
  182. }
  183. void updateAdd(int l,int r,int node,int lx,int rx,int val)
  184. {
  185. if(l>rx||r<lx)return;
  186. if(l>=lx&&r<=rx)
  187. {
  188. pushAdd(l,r,node,val);
  189. return;
  190. }
  191. propegate(l,r,node);
  192. updateAdd(l,mid,L,lx,rx,val);
  193. updateAdd(mid+1,r,R,lx,rx,val);
  194. seg[node]=merge(seg[L],seg[R]);
  195. }
  196. void updateSet(int l,int r,int node,int lx,int rx,int val)
  197. {
  198. if(l>rx||r<lx)return;
  199. if(l>=lx&&r<=rx)
  200. {
  201. pushSet(l,r,node,val);
  202. return;
  203. }
  204. propegate(l,r,node);
  205. updateSet(l,mid,L,lx,rx,val);
  206. updateSet(mid+1,r,R,lx,rx,val);
  207. seg[node]=merge(seg[L],seg[R]);
  208. }
  209. void updateMin(int l,int r,int node,int lx,int rx,int mn)
  210. {
  211. if(r<lx||l>rx||seg[node].mx<=mn) return;
  212. if(l>=lx&&r<=rx&&mn>seg[node].secMx)
  213. {
  214. pushMin(l,r,node,mn);
  215. return;
  216. }
  217. propegate(l,r,node);
  218. updateMin(l,mid,L,lx,rx,mn);
  219. updateMin(mid+1,r,R,lx,rx,mn);
  220. seg[node]=merge(seg[L],seg[R]);
  221. }
  222. void updateMax(int l,int r,int node,int lx,int rx,int mx)
  223. {
  224. if(l>rx||r<lx||mx<=seg[node].mn) return;
  225. if(l>=lx&&r<=rx&&mx<seg[node].secMn)
  226. {
  227. pushMax(l,r,node,mx);
  228. return;
  229. }
  230. propegate(l,r,node);
  231. updateMax(l,mid,L,lx,rx,mx);
  232. updateMax(mid+1,r,R,lx,rx,mx);
  233. seg[node]=merge(seg[L],seg[R]);
  234. }
  235. int querySum(int l,int r,int node,int lx,int rx)
  236. {
  237. if(l>rx||r<lx)return 0;
  238. if(l>=lx&&r<=rx)return seg[node].sum;
  239. propegate(l,r,node);
  240. return querySum(l,mid,L,lx,rx)+querySum(mid+1,r,R,lx,rx);
  241. }
  242. int queryMin(int l,int r,int node,int lx,int rx)
  243. {
  244. if(l>rx||r<lx)return inf;
  245. if(l>=lx&&r<=rx)return seg[node].mn;
  246. propegate(l,r,node);
  247. return min(queryMin(l,mid,L,lx,rx),queryMin(mid+1,r,R,lx,rx));
  248. }
  249. int queryMax(int l,int r,int node,int lx,int rx)
  250. {
  251. if(l>rx||r<lx)return -inf;
  252. if(l>=lx&&r<=rx)return seg[node].mx;
  253. propegate(l,r,node);
  254. return max(queryMax(l,mid,L,lx,rx),queryMax(mid+1,r,R,lx,rx));
  255. }
  256. #undef L
  257. #undef R
  258. #undef mid
  259. public:
  260. SegmentTreeBeats(vector<int>&v)
  261. {
  262. int n=v.size()+5;
  263. sz=1;
  264. while(sz<=n)sz<<=1;
  265. seg=vector<Node>(sz<<1,Node(0,-inf,-inf,0,inf,inf,0,0,-1));
  266. build(0,sz-1,0,v);
  267. }
  268. void updateAdd(int l,int r,int val)
  269. {
  270. updateAdd(0,sz-1,0,l,r,val);
  271. }
  272. void updateSet(int l,int r,int val)
  273. {
  274. updateSet(0,sz-1,0,l,r,val);
  275. }
  276. void updateMin(int l,int r,int mn)
  277. {
  278. updateMin(0,sz-1,0,l,r,mn);
  279. }
  280. void updateMax(int l,int r,int mx)
  281. {
  282. updateMax(0,sz-1,0,l,r,mx);
  283. }
  284. int queryMax(int l,int r)
  285. {
  286. return queryMax(0,sz-1,0,l,r);
  287. }
  288. int queryMin(int l,int r)
  289. {
  290. return queryMin(0,sz-1,0,l,r);
  291. }
  292. int querySum(int l,int r)
  293. {
  294. return querySum(0,sz-1,0,l,r);
  295. }
  296. #undef inf
  297. };
  298. signed main()
  299. {
  300. ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  301. int n,q;cin>>n>>q;
  302. vector<int>s(n+1);
  303. SegmentTree tree(n+5);
  304. for(int i=1;i<=n;i++)
  305. {
  306. cin>>s[i];
  307. tree.update(i,i,s[i]);
  308. }
  309. vector<int>v(n+1);
  310. SegmentTreeBeats beats(v);
  311. while(q--)
  312. {
  313. int op;cin>>op;
  314. if(op==1)
  315. {
  316. int l,r,x;cin>>l>>r>>x;
  317. tree.update(l,r,x);
  318. beats.updateAdd(l,r,-x);
  319. beats.updateMax(l,r,0);
  320. }
  321. else
  322. {
  323. int l,r;cin>>l>>r;
  324. cout<<tree.query(l,r)+beats.querySum(l,r)<<'\n';
  325. }
  326. }
  327. return 0;
  328. }
Success #stdin #stdout 0.01s 5516KB
stdin
1 5
1
1 1 1 99
1 1 1 -99
2 1 1
1 1 1 100
2 1 1
stdout
100
101