Luogu-1527 [国家集训队]矩阵乘法

题面

Luogu-1527

题解

昨天学CDQ分治时做了一些题，但是因为题(wo)太(tai)水(lan)了(le)并没有整理

学了一晚上的整体二分，拿这道模板题练练手qaq

整体二分的思想：对答案进行分治

每次处理一段答案区间时，二分一个mid答案

以mid为依据把询问分成两部分（在这道题中就是“小于等于mid的数的数量”大于等于k和小于k这两部分）

然后再继续递归处理这两部分，写起来和CDQ分治特别像...

第一次写二维BIT+第一次因为二维BIT的sb错误调30min XD

没刻意卡常还在luogu跑了rk1，开心qwq

代码

#include<map>

#include<queue>

#include<cmath>

#include<ctime>

#include<stack>

#include<bitset>

#include<vector>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

inline char gc(){

    static char buf[100000],*p1,*p2;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

    return getchar();

}

inline int read(){

    int ans=0,fh=1;

    char ch=gc();

    while(ch<'0'||ch>'9'){if(ch=='-') fh=-1; ch=gc();}

    while(ch>='0'&&ch<='9')	ans=(ans<<1)+(ans<<3)+ch-'0',ch=gc();

    return ans*fh;

}

const int maxl=600,maxn=6e4+100,inf=0x7fffffff;

struct BIT{

    int n;

    int s[maxl][maxl];

    inline int lowbit(int x){return x&(-x);}

    inline void revise(int x,int y,int z){

        for(int i=x;i<=n;i+=lowbit(i))

            for(int j=y;j<=n;j+=lowbit(j))

                s[i][j]+=z;

    }

    inline int query(int x,int y){

        int ans=0;

        for(int i=x;i;i-=lowbit(i))

            for(int j=y;j;j-=lowbit(j))

                ans+=s[i][j];

        return ans;

    }

    inline int query(int sx,int sy,int tx,int ty){

        int ans=query(tx,ty);

        ans-=query(sx-1,ty)+query(tx,sy-1);

        return ans+query(sx-1,sy-1);

    }

}bt;

struct node{

    int x,y,poi;

}mt[maxl*maxl];

int n,m,sx[maxn],sy[maxn],tx[maxn],ty[maxn],k[maxn],p[maxn];

int b[maxl*maxl],tot,ans[maxn],now,tmp1[maxn],tmp2[maxn];

inline bool cmp(node x,node y){return x.poi<y.poi;}

inline bool check(int x){return bt.query(sx[x],sy[x],tx[x],ty[x])>=k[x];}

void cdq(int l,int r,int L,int R){

    if(L>R) return;

    if(l==r){for(int i=L;i<=R;i++) ans[p[i]]=b[l];return;}

    int mid=l+r>>1;

    while(mt[now+1].poi<=b[mid]) now++,bt.revise(mt[now].x,mt[now].y,1);

    while(mt[now].poi>b[mid]) bt.revise(mt[now].x,mt[now].y,-1),now--;

    int lc=0,rc=0,cnt=L-1;

    for(int i=L;i<=R;i++)

        if(check(p[i])) tmp1[++lc]=p[i];

        else tmp2[++rc]=p[i];

    for(int i=1;i<=lc;i++) p[++cnt]=tmp1[i];

    for(int i=1;i<=rc;i++) p[++cnt]=tmp2[i];

    cdq(l,mid,L,L+lc-1),cdq(mid+1,r,L+lc,R);

}

int main(){

//	freopen("1527.in","r",stdin);

//	freopen("1527.out","w",stdout);

    n=bt.n=read(),m=read();

    int cnt=0;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            mt[++cnt]=(node){i,j,read()};

    sort(mt+1,mt+cnt+1,cmp);

    mt[0].poi=-1;mt[cnt+1].poi=inf;

    for(int i=1;i<=cnt;i++)

        if(mt[i].poi!=mt[i-1].poi)

            b[++tot]=mt[i].poi;

    for(int i=1;i<=m;i++){

        sx[i]=read(),sy[i]=read();

        tx[i]=read(),ty[i]=read();

        k[i]=read();p[i]=i;

    }

    now=0,cdq(1,tot,1,m);

    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);

    return 0;

}