luogu P3332 [ZJOI2013]K大数查询

题目链接
题目大意:
有N个位置，M个操作。操作有两种，每次操作如果是：

1 a b c：表示在第a个位置到第b个位置，每个位置加上一个数c
2 a b c：表示询问从第a个位置到第b个位置，第C大的数是多少。

整体二分练习题
每次二分答案 把所有操作分成左右两个部分

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 5e5 + 3;
const LL mod = 1e9 + 7;
struct uzi{
    int o,l,r;
    LL i;
    int pos;
}p[N],q1[N],q2[N];
int n,m,a[N],cnt;
LL ans[N];
LL t[N<<2],laz[N<<2];
int T[N];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
void pd(int o,int l,int r){
    laz[ls]+=laz[o];
    laz[rs]+=laz[o];
    t[ls]+=laz[o]*(mid-l+1);
    t[rs]+=laz[o]*(r-mid);
    laz[o]=0;
}
int cal[N<<2];
void gg(int o,int l,int r){
    t[ls]=laz[ls]=0;
    t[rs]=laz[rs]=0;
    cal[ls]=cal[rs]=1;
    cal[o]=0;
}
void up(int o,int l,int r,int x,int y,int d){
    if(x<=l&&y>=r){
        t[o]+=1ll*(r-l+1)*d;
        laz[o]+=d;
        return ;
    }
    if(cal[o])gg(o,l,r);
    if(laz[o])pd(o,l,r);
    if(x<=mid)up(ls,l,mid,x,y,d);
    if(y>mid)up(rs,mid+1,r,x,y,d);
    t[o]=t[ls]+t[rs];
}
LL get(int o,int l,int r,int x,int y){
    if(x<=l&&y>=r)return t[o];
    if(cal[o])gg(o,l,r);
    if(laz[o])pd(o,l,r);
    LL ans=0;
    if(x<=mid)ans+=get(ls,l,mid,x,y);
    if(y>mid)ans+=get(rs,mid+1,r,x,y);
    return ans;
}
void solve(LL  l,LL r,int x,int y){
    if(l>r||x>y)return ;
    if(l==r){
        for(int i=x;i<=y;i++)if(p[i].o==2)ans[p[i].pos]=n-l+1;
        return ;
    }
    int c=0,d=0;
    t[1]=laz[1]=0;
    cal[1]=1;
    for(int i=x;i<=y;i++){
        if(p[i].o==1){
            if(p[i].i<=mid)up(1,1,n,p[i].l,p[i].r,1),q1[++c]=p[i];
            else q2[++d]=p[i];
        }else{
            LL x=get(1,1,n,p[i].l,p[i].r);
            if(x>=p[i].i)q1[++c]=p[i];
            else p[i].i-=x,q2[++d]=p[i];
        }
    }
    for(int i=x;i<=x+c-1;i++)p[i]=q1[i-x+1];
    for(int i=x+c;i<=y;i++)p[i]=q2[i-x-c+1];
    solve(l,mid,x,x+c-1);
    solve(mid+1,r,x+c,y);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int o,l,r;
        LL c;
        cin>>o>>l>>r>>c;T[i]=o;
        if(o==1)p[i]={o,l,r,n-c+1,i};
        else p[i]={o,l,r,c,i};
    }
    solve(1,n,1,m);
    for(int i=1;i<=m;i++)if(T[i]==2)cout<<ans[i]<<endl;
    return 0;
}