题解：AT_abc467_g [ABC467G] Many Sweets Problem
题目大意
需要你维护单点修改的操作以及求一段区间内至少选多少点才能满足
显然你要求出最小的点数的话，一定是贪心选最大的，只要你很喜欢主席树并且了解，打过带修的树状数组套权值线段树的话，你应该能发现可以把这个操作放到权值线段树上面。
这道题实际上就是板子题了，在这里推荐两道很相似的题目：
- 带修改的区间第 8 大。
- 带修改的区间第 k 小。
首先普通的主席树是使用数组维护的，这样修改的话肯定会时间超限，于是我们考虑树套树，原本的主席树内部其实就是一堆权值线段树而已，于是我们在权值线段树外面再套上一层树状数组，它就变的可以支持单点修改了，这种题目还是挺多的，推荐先看一下上面两道题。
假设你已经会了带修主席树，应该不能这么说，它应该就叫树套树。之后你考虑维护每颗权值线段树的每个子树内的点的个数以及代表的点的权职和。考虑每次向下的时候，记录
最后就是细节问题，记得离散化一下就行。虽然看起来有点长，可能是我的码风问题吧，其实打久了就无感了。
CODE
这道板子题还是很好改的，打了这么久也是终于加过一次分了……
赛时还真没想到还能出个板子题让我水一下的。也可以看出有多水和板子了……
#include<bits/stdc++.h>
#define wk(x) write(x)，putchar(' ')
#define wh(x) write(x)，putchar('\n')
#define int long long
#define N 200005
#define L T[p].l
#define R T[p].r
#define MID ((l+r)>>1)
using namespace std;char st;
int n，m，k，jk，ans，sum，num，cnt，tot，p1，p2;
int RT[N]，dis[N]，vis[N]，X[N]，Y[N]，wis[N*10];
map<int，int> kis;
void read(int &x){
x=0;int ff=1;char ty;ty=getchar();
while(!(ty>='0'&&ty<='9')){if(ty=='-') ff=-1;ty=getchar();}
while(ty>='0'&&ty<='9') x=(x<<3)+(x<<1)+ty-'0'，ty=getchar();x*=ff;return;
}
void write(int x){
if(x==0){putchar('0');return;}if(x<0){x=-x;putchar('-');}
char asd[201];int ip=0;while(x) asd[++ip]=x%10+'0'，x/=10;
for(int i=ip;i>=1;i--) putchar(asd[i]);return;
}
struct T{int l，r，ans，sum;}T[N*100];
struct G{
void insert(int &p，int l，int r，int x，int z){
if(num==0&&!p) T[++cnt]=T[p]，p=cnt;
else if(!p) T[wis[num]]=T[p]，p=wis[num]，num--;
if(l==r) {T[p].ans+=kis[l]*z;T[p].sum+=z;return;}//离散化过了，要记得是取 kis[l] 的值来更新
if(MID>=x) insert(T[p].l，l，MID，x，z);
else insert(T[p].r，MID+1，r，x，z);
T[p].ans=T[L].ans+T[R].ans;
T[p].sum=T[L].sum+T[R].sum;
if(T[L].ans==0&&L) wis[++num]=L，L=0;
if(T[R].ans==0&&R) wis[++num]=R，R=0;
return;
}
int qry(int l，int r，int x，int z){
if(l==r){
int G=0，GG=0;//记得这个点本身也是有值的
for(int i=1;i<=p2;i++) G+=T[Y[i]].ans;
for(int i=1;i<=p1;i++) G-=T[X[i]].ans;
for(int i=1;i<=p2;i++) GG+=T[Y[i]].sum;
for(int i=1;i<=p1;i++) GG-=T[X[i]].sum;
//这里是离散化过后的区间，所以不应该是 l 而是 kis[l]，赛时调了一会
return x>G?-1:(z+(x+kis[l]-1)/kis[l]);
}
int G=0，GG=0;
for(int i=1;i<=p2;i++) G+=T[T[Y[i]].r].ans;
for(int i=1;i<=p1;i++) G-=T[T[X[i]].r].ans;
for(int i=1;i<=p2;i++) GG+=T[T[Y[i]].r].sum;
for(int i=1;i<=p1;i++) GG-=T[T[X[i]].r].sum;
if(G>=x){
for(int i=1;i<=p1;i++) X[i]=T[X[i]].r;
for(int i=1;i<=p2;i++) Y[i]=T[Y[i]].r;
return qry(MID+1，r，x，z);
}
else{
for(int i=1;i<=p1;i++) X[i]=T[X[i]].l;
for(int i=1;i<=p2;i++) Y[i]=T[Y[i]].l;
return qry(l，MID，x-G，z+GG);//取上贡献
}
}
int lowbit(int x){return x&-x;}
void Get(int l，int r){//在树状数组上求出当前查询区间
p1=p2=0;l--;
while(r) Y[++p2]=RT[r]，r-=lowbit(r);
while(l) X[++p1]=RT[l]，l-=lowbit(l);
return;
}
void Get1(int r，int G，int x){//更新
while(r<=n) insert(RT[r]，1，sum，G，x)，r+=lowbit(r);
return;
}
}GT;
struct GY{
int c，x，l，r，z;
}Q[N];
signed main(){
read(n)，read(m);
for(int i=1;i<=n;i++) read(dis[i])，vis[++tot]=dis[i];
for(int i=1，l，r，x;i<=m;i++){
read(Q[i].c)，read(Q[i].x)，read(Q[i].l)，read(Q[i].r)，read(Q[i].z);
vis[++tot]=Q[i].x;
}//离散化其实似乎打的有点繁琐了？
sort(1+vis，1+vis+tot);
sum=unique(1+vis，1+vis+tot)-vis-1;
for(int i=1;i<=n;i++) kis[lower_bound(1+vis，1+vis+sum，dis[i])-vis]=dis[i];
for(int i=1;i<=m;i++) kis[lower_bound(1+vis，1+vis+sum，Q[i].x)-vis]=Q[i].x;
for(int i=1;i<=n;i++) GT.Get1(i，lower_bound(1+vis，1+vis+sum，dis[i])-vis，1);
for(int i=1;i<=m;i++){
int G=lower_bound(1+vis，1+vis+sum，Q[i].x)-vis;
GT.Get1(Q[i].c，lower_bound(1+vis，1+vis+sum，dis[Q[i].c])-vis，-1);//修改操作
dis[Q[i].c]=Q[i].x;GT.Get1(Q[i].c，G，1);GT.Get(Q[i].l，Q[i].r);//查询
wh(GT.qry(1，sum，Q[i].z，0));
}
return 0;
}赛时代码，码风有可能不符个人习惯，仅供参考。