萌新求助

用的是权值线段树qaq

(i,j)位置维护的以(1,1)为左上角和以(i,j)为右下角的矩阵中的所有权值，每次加入(i,j)的权值，然后合并(i-1,j)和(i,j-1)的线段树，再减去(i-1,j-1)的线段树。 查询是就是(x2,y2)(x2,y1-1)(x1-1,y2)(x1-1,y1-1)做容斥。

目前样例都过不了，好像是合并的问题，但不知道哪里错了

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;

const int M=505;

int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') y=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*y;
}

int n,q,cnt=0,a[M][M],lsh[M*M],Num[M][M];
int num=0,rt[M*M],size[M*M*250],ch[M*M*250][2];
void pushup(int u){
    return (void)(size[u]=size[ch[u][0]]+size[ch[u][1]]);
}

void Insert(int &u,int l,int r,int x){
    if(!u) u=++num;size[u]=1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) Insert(ch[u][0],l,mid,x),ch[u][1]=0;
    else Insert(ch[u][1],mid+1,r,x),ch[u][0]=0;
    return (void)(pushup(u));
}

int Merge(int x,int y,int l,int r){
    if(!x||!y) return x+y;
    if(l==r){
        size[x]+=size[y];
        return x;
    }
    int mid=(l+r)>>1;
    ch[x][0]=Merge(ch[x][0],ch[y][0],l,mid);
    ch[x][1]=Merge(ch[x][1],ch[y][1],mid+1,r);
    pushup(x);
    return x;
}

int Del(int x,int y,int l,int r){
    if(!x||!y) return x+y;
    if(size[x]==size[y]){
        size[x]=0;
        ch[x][0]=ch[x][1]=0;
        return x;
    }
    if(l==r){
        size[x]-=size[y];
        return x;
    }
    int mid=(l+r)>>1;
    ch[x][0]=Del(ch[x][0],ch[y][0],l,mid);
    ch[x][1]=Del(ch[x][1],ch[y][1],mid+1,r);
    pushup(x);
    return x;
}

int Query(int A,int B,int C,int D,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)>>1,p=size[ch[A][0]]-size[ch[B][0]]-size[ch[C][0]]+size[ch[D][0]];
    if(p>k) return Query(ch[A][0],ch[B][0],ch[C][0],ch[D][0],l,mid,k);
    else return Query(ch[A][1],ch[B][1],ch[C][1],ch[D][1],mid+1,r,k-p);
}

void Check(int u,int l,int r){
    printf("Check %d %d %d %d\n",u,l,r,size[u]);
    if(l==r) return ;
    int mid=(l+r)>>1;
    Check(ch[u][0],l,mid),Check(ch[u][1],mid+1,r);
}

void solve(){
    n=read(),q=read();cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=read(),
            lsh[++cnt]=a[i][j],
            Num[i][j]=cnt;
    sort(lsh+1,lsh+cnt+1);int len=unique(lsh+1,lsh+cnt+1)-lsh-1;cnt=len;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=lower_bound(lsh+1,lsh+cnt+1,a[i][j])-lsh;
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=n;j++){
//          printf("%d ",a[i][j]);
//      }
//      printf("\n");
//  }
//  for(int i=1;i<=cnt;i++) printf("%d ",lsh[i]);printf("\n");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            Insert(rt[Num[i][j]],1,cnt,a[i][j]);
            if(Num[i-1][j]) rt[Num[i][j]]=Merge(rt[Num[i][j]],rt[Num[i-1][j]],1,cnt);
            if(Num[i][j-1]) rt[Num[i][j]]=Merge(rt[Num[i][j]],rt[Num[i][j-1]],1,cnt);
            if(Num[i-1][j-1]) rt[Num[i][j]]=Del(rt[Num[i][j]],rt[Num[i-1][j-1]],1,cnt);
//          printf("\nCheck %d %d:\n",i,j);
//          Check(Num[i][j],1,cnt);
        }
    }
    while(q--){
        int X1=read(),Y1=read(),X2=read(),Y2=read(),K=read();
        printf("%d\n",lsh[Query(rt[Num[X2][Y2]],rt[Num[X1-1][Y2]],rt[Num[X2][Y1-1]],rt[Num[X1-1][Y1-1]],1,cnt,K)]);
    }
}

int main(){
//  freopen("shuju.in","r",stdin);
    solve();
}