fork(1) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define X first
  6. #define Y second
  7. #define INPUT freopen("draft.inp","r",stdin)
  8. #define OUTPUT freopen("draft.out","w",stdout)
  9. #define FOR(i,l,r) for(auto i=l;i<=r;i++)
  10. #define REP(i,l,r) for(auto i=l;i<r;i++)
  11. #define FORD(i,l,r) for(auto i=l;i>=r;i--)
  12. #define REPD(i,l,r) for(auto i=l;i>r;i--)
  13. #define ENDL printf("\n")
  14. #define debug 1
  15.  
  16. typedef long long ll;
  17. typedef pair<int,int> ii;
  18.  
  19. const int inf=1e9;
  20. const int MOD=1e9+7;
  21. const double PI=3.14159265359;
  22. const int N=1e5+10;
  23.  
  24.  
  25. template <class T> bool minimize(T &x,T y){
  26. if (x>y) x=y;else return 0;
  27. return 1;
  28. }
  29. template <class T> bool maximize(T &x,T y){
  30. if (x<y) x=y;else return 0;
  31. return 1;
  32. }
  33.  
  34. ll S[N<<2],sum[N<<2][2];
  35. int laz[N<<2][2],c[N<<2];
  36. ii h[N<<2][2],ma[N<<2][2],mi[N<<2][2];
  37.  
  38. int n,m,a[N][2],gold[2],q[N][4];
  39. void lazyupdate(int node,int L,int R){
  40. if (!c[node]) return;
  41. FOR(type,0,1) if (h[node][type].Y){
  42. ma[node][type].X=mi[node][type].X=h[node][type].X;
  43. sum[node][type]=1LL*h[node][type].X*c[node];
  44. S[node]=1LL*h[node][type].X*sum[node][type^1];
  45. if (L<R){
  46. h[node*2][type]=h[node*2+1][type]=h[node][type];
  47. laz[node*2][type]=laz[node*2+1][type]=0;
  48. }
  49. h[node][type]=ii(0,0);
  50. }
  51. S[node]+=sum[node][1]*laz[node][0]+sum[node][0]*laz[node][1]+1LL*laz[node][0]*laz[node][1]*c[node];
  52. FOR(i,0,1) if (laz[node][i]){
  53. sum[node][i]+=1LL*laz[node][i]*c[node];
  54. ma[node][i].X+=laz[node][i];
  55. mi[node][i].X+=laz[node][i];
  56. if (L<R){
  57. laz[node*2][i]+=laz[node][i];
  58. laz[node*2+1][i]+=laz[node][i];
  59. }
  60. laz[node][i]=0;
  61. }
  62. }
  63. void getinfo(int node){
  64. FOR(type,0,1){
  65. mi[node][type]=(mi[node<<1][type].X<mi[node*2+1][type].X)?mi[node*2][type]:mi[node*2+1][type];
  66. ma[node][type]=(ma[node<<1][type].X>ma[node*2+1][type].X)?ma[node*2][type]:ma[node*2+1][type];
  67. sum[node][type]=(sum[node<<1][type]+sum[node*2+1][type]);
  68. }
  69. c[node]=c[node*2]+c[node*2+1];
  70. S[node]=S[node*2]+S[node*2+1];
  71. }
  72. void update(int type,int node,int L,int R,int l,int r,int v){
  73. lazyupdate(node,L,R);
  74. if (L>r||R<l) return;
  75. if (l<=L&&R<=r){
  76. if (type>2) laz[node][type-3]+=v;
  77. else h[node][type-1]=ii(v,1);
  78. lazyupdate(node,L,R);
  79. return;
  80. }
  81. update(type,node*2,L,(L+R)/2,l,r,v);
  82. update(type,node*2+1,(L+R)/2+1,R,l,r,v);
  83. getinfo(node);
  84. }
  85. ll query(int type,int node,int L,int R,int l,int r){
  86. lazyupdate(node,L,R);
  87. if (L>r||R<l) return 0;
  88. if (l<=L&&R<=r) return (type?c[node]:S[node]);
  89. return query(type,node*2,L,(L+R)/2,l,r)+query(type,node*2+1,(L+R)/2+1,R,l,r);
  90. }
  91. void clearnode(int node){
  92. FOR(i,0,1){
  93. mi[node][i].X=inf;
  94. ma[node][i].X=-inf;
  95. h[node][i]=ii(0,0);
  96. laz[node][i]=0;
  97. sum[node][i]=0;
  98. }
  99. c[node]=S[node]=0;
  100. }
  101. void erase(int node,int L,int R,int x){
  102. lazyupdate(node,L,R);
  103. if (L>x||R<x) return;
  104. if (L==R){
  105. clearnode(node);
  106. return;
  107. }
  108. erase(node*2,L,(L+R)/2,x);
  109. erase(node*2+1,(L+R)/2+1,R,x);
  110. getinfo(node);
  111. }
  112. void build(int node,int L,int R){
  113. if (L==R){
  114. bool ok=!(a[L][0]>gold[0]||a[L][1]>gold[1]||a[L][0]<=0||a[L][1]<=0);
  115. FOR(i,0,1){
  116. mi[node][i]=ii(ok?a[L][i]:inf,L);
  117. ma[node][i]=ii(ok?a[L][i]:-inf,L);
  118. sum[node][i]=ok?a[L][i]:0;
  119. }
  120. c[node]=ok;
  121. S[node]=ok?1LL*a[L][0]*a[L][1]:0;
  122. return;
  123. }
  124. build(node*2,L,(L+R)/2);
  125. build(node*2+1,(L+R)/2+1,R);
  126. getinfo(node);
  127. }
  128. void detect(){
  129. FOR(type,0,1){
  130. while (ma[1][type].X>gold[type]){
  131. int x=ma[1][type].Y;
  132. erase(1,1,n,x);
  133. }
  134. while (mi[1][type].X<=0){
  135. int x=mi[1][type].Y;
  136. erase(1,1,n,x);
  137. }
  138. }
  139. }
  140. void check(int node,int L,int R){
  141. printf("%d %d %d\n",node,L,R);
  142. // printf("Max a:%d %d\n",ma[node][0].X,ma[node][0].Y);
  143. // printf("Min a:%d %d\n",mi[node][0].X,mi[node][0].Y);
  144. // printf("Max b:%d %d\n",ma[node][1].X,ma[node][1].Y);
  145. // printf("Min b:%d %d\n",mi[node][1].X,mi[node][1].Y);
  146. printf("%d %d\n",laz[node][0],laz[node][1]);
  147. cout<<sum[node][0]<<" "<<sum[node][1]<<'\n'<<S[node]<<'\n';
  148. if (L==R) return;
  149. check(node*2,L,(L+R)/2);
  150. check(node*2+1,(L+R)/2+1,R);
  151. }
  152. int main(){
  153. freopen("vmellip.inp", "r", stdin);
  154. freopen("vmellip.out", "w", stdout);
  155. // INPUT;OUTPUT;
  156. scanf("%d%d",&n,&m);
  157. FOR(i,1,n)
  158. FOR(j,0,1) scanf("%d",a[i]+j);
  159. FOR(i,1,m) {
  160. FOR(j,0,2) scanf("%d",q[i]+j);
  161. if (q[i][0]<=4) scanf("%d",q[i]+3);
  162. }
  163. scanf("%d%d",gold,gold+1);
  164. build(1,1,n);
  165. // check(1,1,n);
  166. FOR(i,1,m){
  167. // printf("%d...\n",i);
  168. if (q[i][0]<=4) update(q[i][0],1,1,n,q[i][1],q[i][2],q[i][3]);
  169. else {
  170. detect();
  171. printf("%lld\n",query(q[i][0]-5,1,1,n,q[i][1],q[i][2]));
  172. }
  173. // check(1,1,n);
  174. }
  175. }
Runtime error #stdin #stdout 0s 46696KB
stdin
Standard input is empty
stdout
Standard output is empty