2020 CCPC Wannafly Winter Camp Day1I K小数查询(分块)

观察到询问的个数还能接受，我们考虑使用分块办法来维护答案

对于每次更新，边界块暴力，中间块维护整块信息，我们对每个块维护一个mi，表示对整块取min的值

更新的时候，整块只用维护min值，边界块需要更新并且重新排序，因为并不是所有的点都被改变。

询问的时候采取二分check，check的方法也是如此，分块维护即可，因为每个块只有根号n，因此时间复杂度得到保证

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
int belong[N],block;
int n,m;
int l[N],r[N];
vector<int> num[N];
int mi[N];
int a[N];
int sz;
void build(){
    block=sqrt(n);
    sz=n/block;
    if(n%block)
        sz++;
    int i,j;
    for(i=1;i<=sz;i++){
        l[i]=(i-1)*block+1,r[i]=i*block;
    }
    r[sz]=n;
    for(i=1;i<=n;i++){
        belong[i]=(i-1)/block+1;
    }
    for(i=1;i<=sz;i++){
        mi[i]=inf;
        for(j=l[i];j<=r[i];j++){
            num[i].push_back(a[j]);
        }
        sort(num[i].begin(),num[i].end());
    }
}
void check(int pos){
    num[pos].clear();
    int i;
    for(i=l[pos];i<=r[pos];i++){
        a[i]=min(a[i],mi[pos]);
        num[pos].push_back(a[i]);
    }
    sort(num[pos].begin(),num[pos].end());
}
void modify(int ll,int rr,int x){
    int tmp1=belong[ll];
    int tmp2=belong[rr];
    int i,j;
    if(tmp1==tmp2){
        for(i=ll;i<=rr;i++){
            a[i]=min(a[i],x);
        }
        check(tmp1);
        return ;
    }
    for(i=ll;i<=r[tmp1];i++){
        a[i]=min(a[i],x);
    }
    check(tmp1);
    for(i=l[tmp2];i<=rr;i++){
        a[i]=min(a[i],x);
    }
    check(tmp2);
    for(i=tmp1+1;i<=tmp2-1;i++){
        mi[i]=min(mi[i],x);
    }
}
int query(int ll,int rr,int k){
    int tmp1=belong[ll];
    int tmp2=belong[rr];
    int i,j;
    int cnt=0;
    if(tmp1==tmp2){
        for(i=ll;i<=rr;i++){
            if(a[i]<=k||mi[tmp1]<=k)
                cnt++;
        }
        return cnt;
    }
    for(i=ll;i<=r[tmp1];i++){
        if(a[i]<=k||mi[tmp1]<=k)
            cnt++;
    }
    for(i=l[tmp2];i<=rr;i++){
        if(a[i]<=k||mi[tmp2]<=k)
            cnt++;
    }
    for(i=tmp1+1;i<=tmp2-1;i++){
        if(mi[i]<=k)
            cnt+=r[i]-l[i]+1;
        else{
            cnt+=upper_bound(num[i].begin(),num[i].end(),k)-num[i].begin();
        }
    }
    return cnt;
}
int ask(int L,int R,int k){
    int l=-1e9,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(query(L,R,mid)>=k){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return l;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int i;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    build();
    while(m--){
        int opt;
        cin>>opt;
        if(opt==1){
            int l,r,x;
            cin>>l>>r>>x;
            modify(l,r,x);
        }
        else{
            int l,r,k;
            cin>>l>>r>>k;
            cout<<ask(l,r,k)<<endl;
        }
    }
    return 0;
}