[模板]区间第k大整体二分

https://blog.csdn.net/wu_tongtong/article/details/78825245

https://www.cnblogs.com/sagitta/p/5982251.html

https://blog.csdn.net/wu_tongtong/article/details/78826023

https://blog.csdn.net/wu_tongtong/article/details/79790268

不带修 POJ2104:

#include<iostream>
#include<cstdio>
#include<cstring>
#define lbt(x) (x&-x)
#define INF 2000000000
using namespace std;
const int maxn=100009;
int n,m,tot;
struct qq{
    int x,y,k,id,type;//0 add,1 query
}q[maxn*2],q1[maxn*2],q2[maxn*2];
int ans[maxn*2];
int t[maxn];
void add(int x,int k){
    while(x<=n){
        t[x]+=k;
        x+=lbt(x);
    }
}
int ask(int x){
    int ans=0;
    while(x){
        ans+=t[x];
        x-=lbt(x);
    }
    return ans;
}
void solve(int l,int r,int L,int R){//值域和询问序列 
    if(l>r || L>R)return;
    if(l==r){
        for(int i=L;i<=R;i++)if(q[i].type)ans[q[i].id]=l;
        return;
    }
    int mid=l+r>>1,cnt1=0,cnt2=0;
    for(int i=L;i<=R;i++)
    if(q[i].type){
        int tmp=ask(q[i].y)-ask(q[i].x-1);
        if(tmp>=q[i].k)q1[++cnt1]=q[i];
        else q[i].k-=tmp,q2[++cnt2]=q[i];
    }
    else{
        if(q[i].x<=mid)add(q[i].id,1),q1[++cnt1]=q[i];
        else q2[++cnt2]=q[i];
    }
    for(int i=1;i<=cnt1;i++)if(!q1[i].type)add(q1[i].id,-1);//清空树状数组 
    for(int i=1;i<=cnt1;i++)q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++)q[L+cnt1+i-1]=q2[i];
    solve(l,mid,L,L+cnt1-1);solve(mid+1,r,L+cnt1,R);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        q[++tot].x=x;q[tot].id=i;
    }
    for(int i=1;i<=m;i++){
        tot++;
        scanf("%d%d%d",&q[tot].x,&q[tot].y,&q[tot].k);
        q[tot].type=1;q[tot].id=i;
    }
    solve(-INF,INF,1,tot);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}

 目前不对：HDU5412

#include<iostream>
#include<cstdio>
#include<cstring>
#define lbt(x) (x&-x)
#define INF 1000000000
using namespace std;
const int maxn=100009;
int n,m,tot,totq,ans[maxn],raw[maxn];
struct node{
    int type,x,y,k,id;//0 add 1 query
}q[maxn*2],q1[maxn*2],q2[maxn*2];
int t[maxn];
void add(int x,int k){
    while(x<=n){
        t[x]+=k;
        x+=lbt(x);
    }
}
int ask(int x){
    int ans=0;
    while(x){
        ans+=t[x];
        x-=lbt(x);
    }
}
void solve(int l,int r,int L,int R){
    if(l>r || L>R)return;
    if(l==r){
        for(int i=L;i<=R;i++)if(q[i].type)ans[q[i].id]=l;
        return;
    }
    int mid=l+r>>1,cnt1=0,cnt2=0;
    for(int i=L;i<=R;i++)
    if(q[i].type){
        int tmp=ask(q[i].y)-ask(q[i].x-1);
        if(tmp>=q[i].k)q1[++cnt1]=q[i];
        else q[i].k-=tmp,q2[++cnt2]=q[i];
    }
    else{
        if(q[i].x<=mid)add(q[i].id,q[i].y),q1[++cnt1]=q[i];
        else q2[++cnt2]=q[i];
    }
    for(int i=1;i<=cnt1;i++)if(!q1[i].type)add(q1[i].id,-q1[i].y);
    for(int i=1;i<=cnt1;i++)q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++)q[L+cnt1+i-1]=q2[i];
    solve(l,mid,L,L+cnt1-1);solve(mid+1,r,L+cnt1,R);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(ans,0,sizeof(ans));
        memset(t,0,sizeof(t));
        tot=0;totq=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&raw[i]);
            q[++tot].x=raw[i];q[tot].y=1;q[tot].id=i;
        }
        scanf("%d",&m);int op;
        for(int i=1,x,y,k;i<=m;i++){
            scanf("%d",&op);
            if(op==1){
                scanf("%d%d",&x,&y);
                q[++tot].x=raw[x];q[tot].y=-1;q[tot].id=x;
                raw[x]=y;//用raw数组记录序列状态 
                q[++tot].x=raw[x];q[tot].y=1;q[tot].id=x;
            }
            else{
                scanf("%d%d%d",&x,&y,&k);
                q[++tot].x=x;q[tot].y=y;q[tot].k=k;q[tot].id=++totq;q[tot].type=1;
            }
        }
        solve(1,INF,1,tot);
        for(int i=1;i<=totq;i++)
        printf("%d\n",ans[i]);
    }
}

 

luogu_P1527矩阵乘法：

树状数组换为二维，把每个点塞入一维数组排序，其他没什么大的区别

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lbt(x) (x&-x)
#define INF 1e9
using namespace std;
const int maxn=509;
const int maxm=60009;
int n,m,ans[maxm];
int t[maxn][maxn];
void add(int x,int y,int k){
    for(;x<=n;x+=lbt(x))
    for(int z=y;z<=n;z+=lbt(z))
    t[x][z]+=k;
}
int ask(int x,int y){
    int ans=0;
    for(;x;x-=lbt(x))
    for(int z=y;z;z-=lbt(z))
    ans+=t[x][z];
    return ans;
}
struct node{
    int xa,ya,xb,yb,k,id;
}q[maxm*2],q1[maxm*2],q2[maxm*2];
int tota,tot;
struct aa{
    int x,y,w;
    bool operator <(const aa&xx)const{
        return w<xx.w;
    }
}a[maxn*maxn];
inline int calc(int xa,int ya,int xb,int yb){
    return ask(xb,yb)-ask(xa-1,yb)-ask(xb,ya-1)+ask(xa-1,ya-1);
}
void solve(int l,int r,int L,int R){
    if(L>R || l>r)return;
    if(l==r){
        for(int i=L;i<=R;i++)ans[q[i].id]=a[l].w;
        return;
    }
    int mid=l+r>>1,cnt1=0,cnt2=0;
    for(int i=l;i<=mid;i++)
    add(a[i].x,a[i].y,1);
    for(int i=L;i<=R;i++){
        int tmp=calc(q[i].xa,q[i].ya,q[i].xb,q[i].yb);
        if(tmp>=q[i].k)q1[++cnt1]=q[i];
        else q[i].k-=tmp,q2[++cnt2]=q[i];
    }
    for(int i=l;i<=mid;i++)
    add(a[i].x,a[i].y,-1);
    for(int i=1;i<=cnt1;i++)q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++)q[L+cnt1+i-1]=q2[i];
    solve(l,mid,L,L+cnt1-1);solve(mid+1,r,L+cnt1,R);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++)
    for(int j=1;j<=n;j++){
        scanf("%d",&x);
        a[++tota].x=i;a[tota].y=j;a[tota].w=x;
    }
    sort(a+1,a+tota+1);
    for(int i=1;i<=m;i++){
        tot++;
        scanf("%d%d%d%d%d",&q[tot].xa,&q[tot].ya,&q[tot].xb,&q[tot].yb,&q[tot].k);
        q[tot].id=i;
    }
    solve(1,tota,1,tot);
    for(int i=1;i<=tot;i++)printf("%d\n",ans[i]);
}