整体二分+洛谷P1527 [国家集训队]矩阵乘法

ゝ一纸荒年。 2023-06-08 10:53 7阅读 0赞

我靠，tm的，把1写成2，debug了一晚上，debug到心态炸裂。

不过，这整体二分，也没有想象中的那么快，可能不好写，但是代码少。

代码少，还是很舒服~

#include<bits/stdc++.h>
    using namespace std;
    const int M=500*505;
    struct Node{int x,y,v;}d[M];
    bool cmp(Node a,Node b){return a.v<b.v;}
    
    struct ques{int x1,x2,y1,y2,k,id;}q[M],p[M];
    
    int n,m,cnt,res[M],t[505][504];
    void inser(int x,int y,int w){
        for(int i=x;i<=n;i+=(i&-i))
            for(int j=y;j<=n;j+=(j&-j))
                t[i][j]+=w;
    }
    int pre(int x,int y){
        int ans = 0;
        for(int i=x;i>0;i-=(i&-i))
            for(int j=y;j>0;j-=(j&-j))
                ans+=t[i][j];
        return ans;
    }
    int sum(int x1,int y1,int x2,int y2){
        return pre(x2,y2)+pre(x1-1,y1-1)-pre(x1-1,y2)-pre(x2,y1-1);
    }
    
    void ef(int l,int r,int ql,int qr){
        if(qr<ql)return ;
        if(l==r){
            for(int i=ql;i<=qr;i++) res[ q[i].id ]=d[l].v;
            return ;
        }
        int mid=(l+r)>>1,pl=ql,pr=qr;
        for(int i=l;i<=mid;i++)inser(d[i].x,d[i].y,1);
        for(int num,i=ql;i<=qr;i++){
            num=sum(q[i].x1,q[i].y1,q[i].x2,q[i].y2);
            if(q[i].k<=num)p[pl++]=q[i];
            else q[i].k-=num,p[pr--]=q[i];
        }
        for(int i=l;i<=mid;i++)inser(d[i].x,d[i].y,-1);
        for(int i=ql;i<pl;i++)q[i]=p[i];
        for(int i=pl;i<=qr;i++)q[i]=p[i];
        ef(l,mid,ql,pl-1);
        ef(mid+1,r,pl,qr);
    }
    
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&d[++cnt].v),d[cnt].x=i,d[cnt].y=j;
    
        sort(d+1,d+cnt+1,cmp);
    
        for(int i=1;i<=m;i++)
            scanf("%d%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2,&q[i].k),q[i].id=i;
        ef(1,cnt,1,m);
        for(int i=1;i<=m;i++)printf("%d\n",res[i]);
        return 0;
    }