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
",ans[i]);
return 0;
}