1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 #include using namespace std; struct Node { int cnt,bc; long long sum,bs; } c[1200200]; int n,m,num,i,nxt,res,q,qt[100100]; long long qai,bnxt,a[300300],b[400400],qa[100100],qb[100100]; void modify(long long x, int v) { int i=1,L=1,R=num; while (true) { c[i].cnt+=v; c[i].bc=c[i].cnt; c[i].sum+=x*v; c[i].bs=c[i].sum; if (L==R) break; int h=(L+R)/2; i*=2; if (x>b[h]) { L=h+1; ++i; } else R=h; } } int findnext(int i, int L, int R, long long x) { if (L==R) return (b[R]>=x && c[i].cnt>0)?R:0; int h=(L+R)/2,res=0; if (x<=b[h]) res=findnext(i*2,L,h,x); if (res==0) return findnext(i*2+1,h+1,R,x); return res; } void collect(int i, int L, int R, long long x) { if (b[R]=x) return; long long z=min(1LL*c[i].cnt,(bnxt-qai)/b[R]+1); long long zs=z*b[R]; res+=z; c[i].cnt-=z; qai+=zs; c[i].sum-=zs; return; } int h=(L+R)/2; if (qai<=bnxt && b[h+1]qa[i]; ) { qai=qa[i]; bnxt=qb[i]-1; nxt=findnext(1,1,num,qai); if (nxt!=0 && b[nxt]qa[i])?-1:res); recover(1,1,num); } else modify(qa[i],(qt[i]==3)?-1:1); return 0; }