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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| #include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define mp make_pair
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }
char IO;
template <class T=int> T rd(){
T s=0; int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=4e5+10;
const ll U=1e12;
int n,m;
int rt,c[N],ls[N],rs[N],key[N],ma[N],mi[N];
ll s[N],val[N];
int cmp(int x,int y){ return val[x]!=val[y]?val[x]<val[y]:x>y; }
void Up(int p) {
s[p]=s[ls[p]]+s[rs[p]]+val[p];
c[p]=c[ls[p]]+c[rs[p]]+1;
ma[p]=mi[p]=p;
if(ma[ls[p]] && cmp(ma[p],ma[ls[p]])) ma[p]=ma[ls[p]];
if(ma[rs[p]] && cmp(ma[p],ma[rs[p]])) ma[p]=ma[rs[p]];
if(mi[ls[p]] && cmp(mi[ls[p]],mi[p])) mi[p]=mi[ls[p]];
if(mi[ls[p]] && cmp(mi[ls[p]],mi[p])) mi[p]=mi[rs[p]];
}
void Show(int x) {
if(ls[x]) Show(ls[x]);
printf("(%d,%lld,%lld) ",x,val[x],s[x]);
if(rs[x]) Show(rs[x]);
}
int Union(int x,int y) {
if(!x || !y) return x|y;
if(key[x]<key[y]) return rs[x]=Union(rs[x],y),Up(x),x;
return ls[y]=Union(x,ls[y]),Up(y),y;
}
Pii Split(int x,int k) {
if(c[x]<=k) return mp(x,0);
if(!x || !k) return mp(0,x);
if(c[ls[x]]+1<=k) {
Pii y=Split(rs[x],k-c[ls[x]]-1);
return rs[x]=y.first,Up(x),mp(x,y.second);
} else {
Pii y=Split(ls[x],k);
return ls[x]=y.second,Up(x),mp(y.first,x);
}
}
Pii Split2(int x,int k) {
if(!x) return mp(0,0);
if(cmp(ma[x],k)) return mp(x,0);
if(cmp(k,mi[x])) return mp(0,x);
if(cmp(x,k)) {
Pii y=Split2(rs[x],k);
return rs[x]=y.first,Up(x),mp(x,y.second);
} else {
Pii y=Split2(ls[x],k);
return ls[x]=y.second,Up(x),mp(y.first,x);
}
}
Pii Split3(int x,ll k) {
if(!x) return mp(0,0);
if(s[x]<=k) return mp(0,x);
if(s[rs[x]]>=k) {
Pii y=Split3(rs[x],k);
return rs[x]=y.first,Up(x),mp(x,y.second);
} else {
Pii y=Split3(ls[x],k-s[rs[x]]-val[x]);
return ls[x]=y.second,Up(x),mp(y.first,x);
}
}
void Insert(){
val[++n]=rd<ll>(),s[n]=val[n],ma[n]=mi[n]=n,c[n]=1,key[n]=rand();
Pii t=Split2(rt,n);
rt=Union(Union(t.first,n),t.second);
}
void Erase() {
Pii x=Split2(rt,0);
Pii y=Split(x.second,1);
rt=Union(x.first,y.second);
}
int T[N],cnt;
int main(){
rep(i,1,rd()) Insert();
rep(kase,1,rd()) {
int opt=rd();
if(opt==2) Insert();
else if(opt==3) val[0]=rd<ll>()-1,Erase();
else {
ll now=rd<ll>(),des=rd<ll>(),ans=cnt=0;
while(now<des) {
val[n+1]=now;
Pii x=Split2(rt,n+1);
ll nxt=x.second?val[mi[x.second]]+1:1e18;
cmin(nxt,des);
ll d=nxt-now;
Pii y=Split3(x.first,d);
now+=s[y.second],ans+=c[y.second];
rt=Union(y.first,x.second);
T[++cnt]=y.second;
if(now<nxt) break;
}
drep(i,cnt,1) {
Pii x=Split2(rt,T[i]);
rt=Union(Union(x.first,T[i]),x.second);
}
if(now>=des) printf("%lld\n",ans);
else puts("-1");
}
}
}
|
