Description

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c 如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

Solution

这题是可以区间线段树套权值线段树来做的

但是我想练一下整体二分

顺便写一个树状数组的区间修改+区间查询

class BIT{    #define NM 50005    #define lb(x) (x&(-x))    private:        ll t1[NM],t2[NM],N;        BIT(){}    public:        BIT(int _n):N(_n){memset(t1,0,sizeof t1);memset(t2,0,sizeof t2);}        inline void CC(int p,int v){for(reg int x=p;x<=N;x+=lb(x))t1[x]+=v,t2[x]+=v*p*1ll;}        inline void C(int l,int r,int x){CC(l,x);CC(r+1,-x);}        inline ll GG(int p){ll r=0;for(reg int x=p;x;x-=lb(x))r+=(p+1)*t1[x]-t2[x];return r;}        inline ll G(int l,int r){return GG(r)-GG(l-1);}    #undef NM    #undef lb};

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define reg registerclass BIT{    #define NM 50005    #define lb(x) (x&(-x))    private:        ll t1[NM],t2[NM],N;        BIT(){}    public:        BIT(int _n):N(_n){memset(t1,0,sizeof t1);memset(t2,0,sizeof t2);}        inline void CC(int p,int v){for(reg int x=p;x<=N;x+=lb(x))t1[x]+=v,t2[x]+=v*p*1ll;}        inline void C(int l,int r,int x){CC(l,x);CC(r+1,-x);}        inline ll GG(int p){ll r=0;for(reg int x=p;x;x-=lb(x))r+=(p+1)*t1[x]-t2[x];return r;}        inline ll G(int l,int r){return GG(r)-GG(l-1);}    #undef NM    #undef lb};#define MN 50005struct ques{int l,r,id,opt;ll c;}q[MN],b1[MN],b2[MN];int n,m,tot,cnt,num[MN],Ans[MN];void solve(int l=1,int r=tot,int ql=1,int qr=m){    if(ql>qr) return;//  printf("%d %d %d %d\n",l,r,ql,qr);    static BIT T(n);register int i;    if(l==r)    {        for(i=ql;i<=qr;++i)if(q[i].opt==2)Ans[q[i].id]=num[l];        return;    }    register int mid=(l+r+1)>>1,tpb1=0,tpb2=0;register ll tmp;    for(i=ql;i<=qr;++i)    {        if(q[i].opt==1)        {            if(q[i].c>=num[mid]) T.C(q[i].l,q[i].r,1),b2[++tpb2]=q[i];            else b1[++tpb1]=q[i];        }        else        {            tmp=T.G(q[i].l,q[i].r);            if(tmp
     
      =num[mid]&&q[i].opt==1) T.C(q[i].l,q[i].r,-1);    bool has1=false,has2=false;    for(i=1;i<=tpb1;++i) q[i+ql-1]=b1[i];    for(i=1;i<=tpb2;++i) q[qr-tpb2+i]=b2[i];    solve(l,mid-1,ql,ql+tpb1-1);solve(mid,r,qr-tpb2+1,qr);}int main(){//  freopen("testdata.in","r",stdin);//  freopen("testdata.out","w",stdout);    n=read();m=read();    register int i;    for(i=1;i<=m;++i)    {        q[i].opt=read(),q[i].l=read(),q[i].r=read(),q[i].c=read();        if(q[i].opt==1) num[++tot]=q[i].c;        if(q[i].opt==2) q[i].id=++cnt;    }    std::sort(num+1,num+tot+1);    tot=std::unique(num+1,num+tot+1)-num-1;    solve();    for(i=1;i<=cnt;++i) printf("%d\n",Ans[i]);    return 0;}
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！