重庆国外网站推广,乐陵310seo,wordpress顶部颜色,网站工具查询ABC467。赛时糖完了 G 写了个带修莫队，然后因为没写奇偶化排序 T 飞了……加了个奇偶化排序就过了。
A
显然答案为 \(\left[\dfrac{10^4w}{h^2}\geq25\right]\)。赛时代码
//#includebits/stdc++.h
#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
using namespace std;
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int w,h;cinhw;if(10000.0*w/h/h=25){cout"Yes\n";}else{cout"No\n";}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}B
没找钱的就记录答案，答案为：
\[\sum_{i=1}^n[s_i=\texttt{keep}](b_i-a_i)
\]赛时代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
using namespace std;
constexpr const int N=100,V=100;
int n,a[N+1],b[N+1];
string s[N+1];
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;int ans=0;for(int i=1;i=n;i++){cina[i]b[i]s[i];switch(s[i][0]){case'k':ans+=b[i]-a[i];break;case 't':break;}}coutans'\n';cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}C
没想 \(m=2\) 的单独做法， 准备复制 E 的代码，先写了 D。
D
容易发现，圆心在 \(PQ,RS\) 的垂直平分线的交点上：
\[\begin{aligned}
y=-\dfrac1{\dfrac{y_p-y_q}{x_p-x_q}}\left(x-\dfrac{x_p+x_q}2\right)+\dfrac{y_p+y_q}2\\
y=-\dfrac1{\dfrac{y_r-y_s}{x_r-x_s}}\left(x-\dfrac{x_r+x_s}2\right)+\dfrac{y_r+y_s}2\\
\end{aligned}
\]无解的情况是这两条直线无交。即直线不重合且 \(\dfrac{y_p-y_q}{x_p-x_q}=\dfrac{y_r-y_s}{x_r-x_s}\)。
直线重合的时候是有圆心的，再判一下直线重合即可。
赛时代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
using namespace std;
typedef long long ll;
struct node{int x,y;
}p,q,r,s;
struct frac{int a,b;
};
frac k(node a,node b){return {a.y-b.y,a.x-b.x};
}
bool operator ==(frac x,frac y){return 1ll*x.a*y.b==1ll*y.a*x.b;
}
bool check(frac k1,frac k2){ll dx=q.x-p.x;ll dy=q.y-p.y;ll mx=p.x+q.x-r.x-s.x;ll my=p.y+q.y-r.y-s.y;return !(k1==k2)||(mx*dx+my*dy)==0;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cinT;while(T--){cinp.xp.yq.xq.yr.xr.ys.xs.y;frac k1=k(p,q);frac k2=k(r,s);if(!check(k1,k2)){cout"No\n";}else{cout"Yes\n";}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}E
设 \(a_i\) 操作了 \(x_i\) 次，则 \(a_i\) 会变为 \(a_i+x_i\)。
那么原要求等价于 \(a_i+a_{i+1}+x_i+x_{i+1}\equiv b_i\pmod m\)，即 \(x_i+x_{i+1}\equiv b_i-a_i-a_{i+1}\pmod m\)。令 \(c_i=b_i-a_i-a_{i+1}\)。
\(x_1\) 已知，之后就可以直接求出来 \(x_1,x_2,\cdots,x_n\)。
之后是一个分段函数，求最小值。
赛时代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
#includemap
using namespace std;
#define int long long
constexpr const int N=2e5,M=1e9;
int n,m,a[N+1],b[N+1],c[N+1],p[N+1];
main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnm;for(int i=1;i=n;i++){cina[i];}for(int i=1;in;i++){cinb[i];}for(int i=1;in;i++){c[i]=(b[i]-a[i]-a[i+1])%m;if(c[i]0){c[i]+=m;}}p[1]=0;for(int i=2;i=n;i++){p[i]=(c[i-1]-p[i-1])%m;if(p[i]0){p[i]+=m;}}int pre=0,k=0;for(int i=1;i=n;i++){a[i]=p[i];pre+=a[i];if(i1){k++;}else{k--;}}mapint,intd;for(int i=1;i=n;i++){if(i1){if(a[i]0){d[m-a[i]]-=m;}}else{if(a[i]m-1){d[a[i]+1]+=m;}}}vectorintv{m-1};for(auto [i,j]:d){v.push_back(i);}sort(v.begin(),v.end());v.resize(unique(v.begin(),v.end())-v.begin());int ans=pre,pl=pre;for(int i=0;iv.size();i++){int x=v[i];if(i==0){pl+=k*x;}else{pl+=k*(x-v[i-1]);}pl+=d[x];ans=min(ans,pl);}coutans'\n';cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}F
贪心，把 \((a_i,b_i)\) 按照 \(b_i\) 从大到小排序，答案即：
\[\max_{i=1}^n\left(\sum_{j\leq i}a_j+b_i\right)
\]但是 \(a_i,b_i\) 会做单点修改，考虑用数据结构维护。
用平衡树以 \(b_i\) 为关键字维护每个点的 \((a_i,b_i)\)，然后每个节点维护一下左子树里的 \(\sum a_j\) 即可。
赛时代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
#includerandom
using namespace std;
typedef long long ll;
constexpr const int N=1e5,Q=1e5;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
mt19937 Rand(time(0));
int n,a[N+1],b[N+1];
int root;
struct FHQTreap{int size;struct node{pairint,intvalue;int size,rand;int lChild,rChild;ll ans,sumA;}t[N+Q+1];FHQTreap(){size=root=0;t[0].ans=inf;t[0].sumA=0;}int create(pairint,int x){t[++size]={x,1,Rand(),0,0,x.first+x.second,x.second};return size;}void up(int p){t[p].size=t[t[p].lChild].size+t[t[p].rChild].size+1;t[p].ans=min({t[t[p].lChild].ans , t[t[p].lChild].sumA+t[p].value.first+t[p].value.second , t[t[p].lChild].sumA+t[p].value.second+t[t[p].rChild].ans});t[p].sumA=t[t[p].lChild].sumA+t[p].value.second+t[t[p].rChild].sumA;}void split(int p,pairint,int x,int l,int r,bool flag=true){if(!p){l=r=0;return;}if(t[p].valuex||t[p].value==xflag){l=p;split(t[p].rChild,x,t[p].rChild,r,flag);}else{r=p;split(t[p].lChild,x,l,t[r].lChild,flag);}up(p);}int merge(int l,int r){if(!l||!r){return l|r;}if(t[l].randt[r].rand){t[l].rChild=merge(t[l].rChild,r);up(l);return l;}else{t[r].lChild=merge(l,t[r].lChild);up(r);return r;}}void insert(pairint,int x){int l,r,p;split(root,x,l,r);root=merge(merge(l,create(x)),r);}void erase(pairint,int x){int l,r,p;split(root,x,l,r);split(l,x,l,p,false);p=merge(t[p].lChild,t[p].rChild);root=merge(merge(l,p),r);}ll query(){return -t[root].ans;}
}t;
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int q;cinnq;for(int i=1;i=n;i++){cina[i];}for(int i=1;i=n;i++){cinb[i];}for(int i=1;i=n;i++){t.insert({-b[i],-a[i]});}while(q--){int op,i,x;cinopix;t.erase({-b[i],-a[i]});switch(op){case 1:a[i]=x;break;case 2:b[i]=x;break;}t.insert({-b[i],-a[i]});coutt.query()'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}G
据说是主席树板子题，然而我并不会。
观察数据范围 \(10^5\)，可以考虑带修莫队。
但是 \(k\leq10^{15}\) 不太好做，因此还可以值域分块。
然后就是板子题，写个奇偶化排序就过了。
赛时没写奇偶化排序 T 飞了。
赛后代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
using namespace std;
typedef long long ll;
constexpr const int N=2e5,Q=2e5,V=5e5;
int n,m,sizeQ,sizeOp,init[N+1],a[N+1],real[N+1];
ll value[V+1];
int M,Bv,bc;
int bid[V+1],bl[N+1],br[N+1],cv[V+1],cb[N+1];
ll sv[V+1],sb[N+1];
ll tot;
void build(){Bv=sqrt(M)+1;bc=(M+Bv-1)/Bv;for(int b=1;b=bc;b++){bl[b]=(b-1)*Bv+1;br[b]=min(b*Bv,M);for(int v=bl[b];v=br[b];v++)bid[v]=b;}
}
struct question{int l,r;ll k;int t,id;
}q[Q+1];
struct operation{int pos,color,backup;
}op[Q+1];
int ans[Q+1];
int B,size,pos[N+1],edgeL[N+1],edgeR[N+1];
void pre(){B=pow(n,2/3.0);for(int i=1;edgeR[i-1]+1=n;i++){edgeL[i]=edgeR[i-1]+1;edgeR[i]=min(edgeL[i]+B-1,n);for(int j=edgeL[i];j=edgeR[i];j++)pos[j]=i;}sort(q+1,q+sizeQ+1,[](question a,question b){if(pos[a.l]!=pos[b.l]){return pos[a.l]pos[b.l]; }else if(pos[a.r]!=pos[b.r]){if(pos[a.l]1){return pos[a.r]pos[b.r];}else{return pos[a.r]pos[b.r];}}else{if(pos[a.r]1){return a.tb.t;}else{return a.tb.t;}}});
}
void addLeft(int l,int r,int t){l--;int v=a[l];cv[v]++;sv[v]+=value[v];tot+=value[v];int b=bid[v];cb[b]++;sb[b]+=value[v];
}
void addRight(int l,int r,int t){r++;int v=a[r];cv[v]++;sv[v]+=value[v];tot+=value[v];int b=bid[v];cb[b]++;sb[b]+=value[v];
}
void delLeft(int l,int r,int t){int v=a[l];cv[v]--;sv[v]-=value[v];tot-=value[v];int b=bid[v];cb[b]--;sb[b]-=value[v];l++;
}
void delRight(int l,int r,int t){int v=a[r];cv[v]--;sv[v]-=value[v];tot-=value[v];int b=bid[v];cb[b]--;sb[b]-=value[v];r--;
}
void moveUp(int l,int r,int t){t++;int p=op[t].pos;if(l=pp=r){int old=a[p];cv[old]--;sv[old]-=value[old];tot-=value[old];int b=bid[old];cb[b]--;sb[b]-=value[old];}a[p]=op[t].color;if(l=pp=r){int nw=a[p];cv[nw]++;sv[nw]+=value[nw];tot+=value[nw];int b=bid[nw];cb[b]++;sb[b]+=value[nw];}
}
void moveDown(int l,int r,int t){int p=op[t].pos;if(l=pp=r){int nw=a[p];cv[nw]--;sv[nw]-=value[nw];tot-=value[nw];int b=bid[nw];cb[b]--;sb[b]-=value[nw];}a[p]=op[t].backup;if(l=pp=r){int old=a[p];cv[old]++;sv[old]+=value[old];tot+=value[old];int b=bid[old];cb[b]++;sb[b]+=value[old];}t--;
}
int calc(ll k){if(totk)return -1;ll rem=k;int ans=0;for(int b=bc;b=1;b--){if(rem=0)break;if(sb[b]==0)continue;if(sb[b]=rem){for(int v=br[b];v=bl[b];v--){if(rem=0)break;if(cv[v]==0)continue;ll s=sv[v];if(s=rem){ans+=(rem+value[v]-1)/value[v];rem=0;break;}else{rem-=s;ans+=cv[v];}}break;}else{rem-=sb[b];ans+=cb[b];}}return ans;
}
void discist(){static int tmp[V+1];M=0;for(int i=1;i=n;i++){tmp[++M]=init[i];}for(int i=1;i=sizeOp;i++){tmp[++M]=op[i].color;tmp[++M]=op[i].backup;}sort(tmp+1,tmp+M+1);M=unique(tmp+1,tmp+M+1)-tmp-1;for(int i=1;i=M;i++){value[i]=tmp[i];}for(int i=1;i=n;i++){a[i]=lower_bound(tmp+1,tmp+M+1,init[i])-tmp;}for(int i=1;i=sizeOp;i++){op[i].color=lower_bound(tmp+1,tmp+M+1,op[i].color)-tmp;op[i].backup=lower_bound(tmp+1,tmp+M+1,op[i].backup)-tmp;}
}
main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnm;for(int i=1;i=n;i++){cininit[i];real[i]=init[i];}sizeQ=sizeOp=0;for(int i=1;i=m;i++){int c,x,l,r;ll k;cincxlrk;op[++sizeOp]={c,x,real[c]};real[c]=x;sizeQ++;q[sizeQ]={l,r,k,sizeOp,sizeQ};}discist();build();pre();int l=1,r=0,t=0;tot=0;for(int i=1;i=sizeQ;i++){while(lq[i].l){addLeft(l,r,t);} while(rq[i].r){addRight(l,r,t);} while(lq[i].l){delLeft(l,r,t);} while(rq[i].r){delRight(l,r,t);} while(tq[i].t){moveUp(l,r,t);} while(tq[i].t){moveDown(l,r,t);} ans[q[i].id]=calc(q[i].k);}for(int i=1;i=sizeQ;i++){coutans[i]'\n';}cout.flush(); /*fclose(stdin);fclose(stdout);*/return 0;
} 重庆国外网站推广乐陵310seo
重庆国外网站推广,乐陵310seo,wordpress顶部颜色,网站工具查询ABC467。赛时糖完了 G 写了个带修莫队，然后因为没写奇偶化排序 T 飞了……加了个奇偶化排序就过了。
A
显然答案为 \(\left[\dfrac{10^4w}{h^2}\geq25\right]\)。赛时代码
//#includebits/stdc++.h
#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
using namespace std;
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int w,h;cinhw;if(10000.0*w/h/h=25){cout"Yes\n";}else{cout"No\n";}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}B
没找钱的就记录答案，答案为：
\[\sum_{i=1}^n[s_i=\texttt{keep}](b_i-a_i)
\]赛时代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
using namespace std;
constexpr const int N=100,V=100;
int n,a[N+1],b[N+1];
string s[N+1];
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;int ans=0;for(int i=1;i=n;i++){cina[i]b[i]s[i];switch(s[i][0]){case'k':ans+=b[i]-a[i];break;case 't':break;}}coutans'\n';cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}C
没想 \(m=2\) 的单独做法， 准备复制 E 的代码，先写了 D。
D
容易发现，圆心在 \(PQ,RS\) 的垂直平分线的交点上：
\[\begin{aligned}
y=-\dfrac1{\dfrac{y_p-y_q}{x_p-x_q}}\left(x-\dfrac{x_p+x_q}2\right)+\dfrac{y_p+y_q}2\\
y=-\dfrac1{\dfrac{y_r-y_s}{x_r-x_s}}\left(x-\dfrac{x_r+x_s}2\right)+\dfrac{y_r+y_s}2\\
\end{aligned}
\]无解的情况是这两条直线无交。即直线不重合且 \(\dfrac{y_p-y_q}{x_p-x_q}=\dfrac{y_r-y_s}{x_r-x_s}\)。
直线重合的时候是有圆心的，再判一下直线重合即可。
赛时代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
using namespace std;
typedef long long ll;
struct node{int x,y;
}p,q,r,s;
struct frac{int a,b;
};
frac k(node a,node b){return {a.y-b.y,a.x-b.x};
}
bool operator ==(frac x,frac y){return 1ll*x.a*y.b==1ll*y.a*x.b;
}
bool check(frac k1,frac k2){ll dx=q.x-p.x;ll dy=q.y-p.y;ll mx=p.x+q.x-r.x-s.x;ll my=p.y+q.y-r.y-s.y;return !(k1==k2)||(mx*dx+my*dy)==0;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cinT;while(T--){cinp.xp.yq.xq.yr.xr.ys.xs.y;frac k1=k(p,q);frac k2=k(r,s);if(!check(k1,k2)){cout"No\n";}else{cout"Yes\n";}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}E
设 \(a_i\) 操作了 \(x_i\) 次，则 \(a_i\) 会变为 \(a_i+x_i\)。
那么原要求等价于 \(a_i+a_{i+1}+x_i+x_{i+1}\equiv b_i\pmod m\)，即 \(x_i+x_{i+1}\equiv b_i-a_i-a_{i+1}\pmod m\)。令 \(c_i=b_i-a_i-a_{i+1}\)。
\(x_1\) 已知，之后就可以直接求出来 \(x_1,x_2,\cdots,x_n\)。
之后是一个分段函数，求最小值。
赛时代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
#includemap
using namespace std;
#define int long long
constexpr const int N=2e5,M=1e9;
int n,m,a[N+1],b[N+1],c[N+1],p[N+1];
main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnm;for(int i=1;i=n;i++){cina[i];}for(int i=1;in;i++){cinb[i];}for(int i=1;in;i++){c[i]=(b[i]-a[i]-a[i+1])%m;if(c[i]0){c[i]+=m;}}p[1]=0;for(int i=2;i=n;i++){p[i]=(c[i-1]-p[i-1])%m;if(p[i]0){p[i]+=m;}}int pre=0,k=0;for(int i=1;i=n;i++){a[i]=p[i];pre+=a[i];if(i1){k++;}else{k--;}}mapint,intd;for(int i=1;i=n;i++){if(i1){if(a[i]0){d[m-a[i]]-=m;}}else{if(a[i]m-1){d[a[i]+1]+=m;}}}vectorintv{m-1};for(auto [i,j]:d){v.push_back(i);}sort(v.begin(),v.end());v.resize(unique(v.begin(),v.end())-v.begin());int ans=pre,pl=pre;for(int i=0;iv.size();i++){int x=v[i];if(i==0){pl+=k*x;}else{pl+=k*(x-v[i-1]);}pl+=d[x];ans=min(ans,pl);}coutans'\n';cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}F
贪心，把 \((a_i,b_i)\) 按照 \(b_i\) 从大到小排序，答案即：
\[\max_{i=1}^n\left(\sum_{j\leq i}a_j+b_i\right)
\]但是 \(a_i,b_i\) 会做单点修改，考虑用数据结构维护。
用平衡树以 \(b_i\) 为关键字维护每个点的 \((a_i,b_i)\)，然后每个节点维护一下左子树里的 \(\sum a_j\) 即可。
赛时代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
#includerandom
using namespace std;
typedef long long ll;
constexpr const int N=1e5,Q=1e5;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
mt19937 Rand(time(0));
int n,a[N+1],b[N+1];
int root;
struct FHQTreap{int size;struct node{pairint,intvalue;int size,rand;int lChild,rChild;ll ans,sumA;}t[N+Q+1];FHQTreap(){size=root=0;t[0].ans=inf;t[0].sumA=0;}int create(pairint,int x){t[++size]={x,1,Rand(),0,0,x.first+x.second,x.second};return size;}void up(int p){t[p].size=t[t[p].lChild].size+t[t[p].rChild].size+1;t[p].ans=min({t[t[p].lChild].ans , t[t[p].lChild].sumA+t[p].value.first+t[p].value.second , t[t[p].lChild].sumA+t[p].value.second+t[t[p].rChild].ans});t[p].sumA=t[t[p].lChild].sumA+t[p].value.second+t[t[p].rChild].sumA;}void split(int p,pairint,int x,int l,int r,bool flag=true){if(!p){l=r=0;return;}if(t[p].valuex||t[p].value==xflag){l=p;split(t[p].rChild,x,t[p].rChild,r,flag);}else{r=p;split(t[p].lChild,x,l,t[r].lChild,flag);}up(p);}int merge(int l,int r){if(!l||!r){return l|r;}if(t[l].randt[r].rand){t[l].rChild=merge(t[l].rChild,r);up(l);return l;}else{t[r].lChild=merge(l,t[r].lChild);up(r);return r;}}void insert(pairint,int x){int l,r,p;split(root,x,l,r);root=merge(merge(l,create(x)),r);}void erase(pairint,int x){int l,r,p;split(root,x,l,r);split(l,x,l,p,false);p=merge(t[p].lChild,t[p].rChild);root=merge(merge(l,p),r);}ll query(){return -t[root].ans;}
}t;
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int q;cinnq;for(int i=1;i=n;i++){cina[i];}for(int i=1;i=n;i++){cinb[i];}for(int i=1;i=n;i++){t.insert({-b[i],-a[i]});}while(q--){int op,i,x;cinopix;t.erase({-b[i],-a[i]});switch(op){case 1:a[i]=x;break;case 2:b[i]=x;break;}t.insert({-b[i],-a[i]});coutt.query()'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}G
据说是主席树板子题，然而我并不会。
观察数据范围 \(10^5\)，可以考虑带修莫队。
但是 \(k\leq10^{15}\) 不太好做，因此还可以值域分块。
然后就是板子题，写个奇偶化排序就过了。
赛时没写奇偶化排序 T 飞了。
赛后代码
//#includebits/stdc++.h
#includealgorithm
#includeiostream
#includecstring
#includeiomanip
#includecstdio
#includestring
#includevector
#includecmath
#includectime
#includedeque
#includequeue
#includestack
#includelist
using namespace std;
typedef long long ll;
constexpr const int N=2e5,Q=2e5,V=5e5;
int n,m,sizeQ,sizeOp,init[N+1],a[N+1],real[N+1];
ll value[V+1];
int M,Bv,bc;
int bid[V+1],bl[N+1],br[N+1],cv[V+1],cb[N+1];
ll sv[V+1],sb[N+1];
ll tot;
void build(){Bv=sqrt(M)+1;bc=(M+Bv-1)/Bv;for(int b=1;b=bc;b++){bl[b]=(b-1)*Bv+1;br[b]=min(b*Bv,M);for(int v=bl[b];v=br[b];v++)bid[v]=b;}
}
struct question{int l,r;ll k;int t,id;
}q[Q+1];
struct operation{int pos,color,backup;
}op[Q+1];
int ans[Q+1];
int B,size,pos[N+1],edgeL[N+1],edgeR[N+1];
void pre(){B=pow(n,2/3.0);for(int i=1;edgeR[i-1]+1=n;i++){edgeL[i]=edgeR[i-1]+1;edgeR[i]=min(edgeL[i]+B-1,n);for(int j=edgeL[i];j=edgeR[i];j++)pos[j]=i;}sort(q+1,q+sizeQ+1,[](question a,question b){if(pos[a.l]!=pos[b.l]){return pos[a.l]pos[b.l]; }else if(pos[a.r]!=pos[b.r]){if(pos[a.l]1){return pos[a.r]pos[b.r];}else{return pos[a.r]pos[b.r];}}else{if(pos[a.r]1){return a.tb.t;}else{return a.tb.t;}}});
}
void addLeft(int l,int r,int t){l--;int v=a[l];cv[v]++;sv[v]+=value[v];tot+=value[v];int b=bid[v];cb[b]++;sb[b]+=value[v];
}
void addRight(int l,int r,int t){r++;int v=a[r];cv[v]++;sv[v]+=value[v];tot+=value[v];int b=bid[v];cb[b]++;sb[b]+=value[v];
}
void delLeft(int l,int r,int t){int v=a[l];cv[v]--;sv[v]-=value[v];tot-=value[v];int b=bid[v];cb[b]--;sb[b]-=value[v];l++;
}
void delRight(int l,int r,int t){int v=a[r];cv[v]--;sv[v]-=value[v];tot-=value[v];int b=bid[v];cb[b]--;sb[b]-=value[v];r--;
}
void moveUp(int l,int r,int t){t++;int p=op[t].pos;if(l=pp=r){int old=a[p];cv[old]--;sv[old]-=value[old];tot-=value[old];int b=bid[old];cb[b]--;sb[b]-=value[old];}a[p]=op[t].color;if(l=pp=r){int nw=a[p];cv[nw]++;sv[nw]+=value[nw];tot+=value[nw];int b=bid[nw];cb[b]++;sb[b]+=value[nw];}
}
void moveDown(int l,int r,int t){int p=op[t].pos;if(l=pp=r){int nw=a[p];cv[nw]--;sv[nw]-=value[nw];tot-=value[nw];int b=bid[nw];cb[b]--;sb[b]-=value[nw];}a[p]=op[t].backup;if(l=pp=r){int old=a[p];cv[old]++;sv[old]+=value[old];tot+=value[old];int b=bid[old];cb[b]++;sb[b]+=value[old];}t--;
}
int calc(ll k){if(totk)return -1;ll rem=k;int ans=0;for(int b=bc;b=1;b--){if(rem=0)break;if(sb[b]==0)continue;if(sb[b]=rem){for(int v=br[b];v=bl[b];v--){if(rem=0)break;if(cv[v]==0)continue;ll s=sv[v];if(s=rem){ans+=(rem+value[v]-1)/value[v];rem=0;break;}else{rem-=s;ans+=cv[v];}}break;}else{rem-=sb[b];ans+=cb[b];}}return ans;
}
void discist(){static int tmp[V+1];M=0;for(int i=1;i=n;i++){tmp[++M]=init[i];}for(int i=1;i=sizeOp;i++){tmp[++M]=op[i].color;tmp[++M]=op[i].backup;}sort(tmp+1,tmp+M+1);M=unique(tmp+1,tmp+M+1)-tmp-1;for(int i=1;i=M;i++){value[i]=tmp[i];}for(int i=1;i=n;i++){a[i]=lower_bound(tmp+1,tmp+M+1,init[i])-tmp;}for(int i=1;i=sizeOp;i++){op[i].color=lower_bound(tmp+1,tmp+M+1,op[i].color)-tmp;op[i].backup=lower_bound(tmp+1,tmp+M+1,op[i].backup)-tmp;}
}
main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnm;for(int i=1;i=n;i++){cininit[i];real[i]=init[i];}sizeQ=sizeOp=0;for(int i=1;i=m;i++){int c,x,l,r;ll k;cincxlrk;op[++sizeOp]={c,x,real[c]};real[c]=x;sizeQ++;q[sizeQ]={l,r,k,sizeOp,sizeQ};}discist();build();pre();int l=1,r=0,t=0;tot=0;for(int i=1;i=sizeQ;i++){while(lq[i].l){addLeft(l,r,t);} while(rq[i].r){addRight(l,r,t);} while(lq[i].l){delLeft(l,r,t);} while(rq[i].r){delRight(l,r,t);} while(tq[i].t){moveUp(l,r,t);} while(tq[i].t){moveDown(l,r,t);} ans[q[i].id]=calc(q[i].k);}for(int i=1;i=sizeQ;i++){coutans[i]'\n';}cout.flush(); /*fclose(stdin);fclose(stdout);*/return 0;
}