洛谷：K大数查询，整体二分写法

柔光的暖阳◎ 2023-06-01 06:23 7阅读 0赞

## 题目描述 P3332 ##

有N个位置，M个操作。操作有两种，每次操作如果是：

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

## 输入格式 ##

第一行N，M接下来M行，每行形如1 a b c或2 a b c

## 输出格式 ##

输出每个询问的结果

## 输入输出样例 ##

**输入 \#1**复制

2 5
    1 1 2 1
    1 1 2 2
    2 1 1 2
    2 1 1 1
    2 1 2 3

**输出 \#1**复制

1
    2
    1

## 说明/提示 ##

【样例说明】

第一个操作后位置 1 的数只有 1 ， 位置 2 的数也只有 1 。  
第二个操作 后位置 1 的数有 1 、 2 ，位置 2 的数也有 1 、 2 。  
第三次询问 位置 1 到位置 1 第 2 大的数是1 。  
第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。

N,M<=50000,N,M<=50000  
a<=b<=N  
1操作中abs(c)<=N  
2操作中c<=long long

仍然记得当时写了一天的二分，wa了一天，可能那天精神不好把，，

因为是查询和修改是交叉进行的，所以二分解决它就很容易，二分答案，将对当前答案有影响的加在线段树中，然后查询是否符合条件，符合符合就左边，不符合就右边

二分真的是快到飞起；

AC码

#include<bits/stdc++.h>
    using namespace std;
    const int M=5e4+5;
    #define ll long long
    struct Node{int l,r;ll num,tag,rec;}t[M<<2];
    struct node{int op,l,r,id;ll v;}q[M],p1[M],p2[M];
    int n,m,ans[M],Q;
    inline void build(int k,int l,int r){
        t[k].l=l;t[k].r=r;
        t[k].num=t[k].tag=t[k].rec=0;
        if(l==r)return ;
        int mid=(l+r)>>1;
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
    }
    inline void down(int k){
        if(t[k].rec){
            t[k*2].tag=t[k*2].num=t[k*2+1].tag=t[k*2+1].num=0;
            t[k*2].rec=t[k*2+1].rec=1;
            t[k].rec=0;
        }
        if(t[k].tag){
            t[k*2].tag+=t[k].tag;
            t[k*2].num+=((ll)(t[k*2].r-t[k*2].l+1))*t[k].tag;
            t[k*2+1].tag+=t[k].tag;
            t[k*2+1].num+=((ll)(t[k*2+1].r-t[k*2+1].l+1))*t[k].tag;
            t[k].tag=0;
        }
    }
    inline void add(int k,int l,int r){
        if(l<=t[k].l&&t[k].r<=r){
            t[k].tag++;
            t[k].num+=((ll)(t[k].r-t[k].l+1));
            return ;
        }
        down(k);
        int mid=(t[k].l+t[k].r)>>1;
        if(l<=mid)add(k*2,l,r);
        if(mid<r)add(k*2+1,l,r);
        t[k].num=t[k*2].num+t[k*2+1].num;
    }
    inline ll ask(int k,int l,int r){
        if(l<=t[k].l&&t[k].r<=r)return t[k].num;
        down(k);
        int mid=(t[k].l+t[k].r)>>1;
        ll res=0;
        if(l<=mid)res+=ask(k*2,l,r);
        if(mid<r)res+=ask(k*2+1,l,r);
        return res;
    }
    inline void ef(int s,int e,int l,int r){
        if(l==r){
            for(int i=s;i<=e;i++)if(q[i].op==2) ans[q[i].id]=l;
            return ;
        }
        t[1].rec=1;t[1].num=t[1].tag=0;
        int s1=0,e1=0,mid=(l+r)>>1;
        ll val;
        for(int i=s;i<=e;i++){
            if(q[i].op==1){
                if(q[i].v>mid){
                    add(1,q[i].l,q[i].r);
                    p2[++e1]=q[i];
                }else p1[++s1]=q[i];
            }else{
                val=ask(1,q[i].l,q[i].r);
                if(val<q[i].v){
                    q[i].v-=val;
                    p1[++s1]=q[i];
                }else p2[++e1]=q[i];
            }
        }
        for(int i=1;i<=s1;i++) q[s+i-1]=p1[i];
        for(int i=1;i<=e1;i++) q[s+s1+i-1]=p2[i];
        if(s1)ef(s,s+s1-1,l,mid);
        if(e1)ef(s+s1,e,mid+1,r);
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)scanf("%d%d%d%lld",&q[i].op,&q[i].l,&q[i].r,&q[i].v),q[i].op==2?q[i].id=++Q:q[i].id=0;
        build(1,1,n);
        ef(1,m,-n,n);
        for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
        return 0;
    }