题解 P1527 【[国家集训队]矩阵乘法】
C3H5ClO
2020-09-14 11:23:44
发一个$\Theta(n^2\log^2n)$做法。（假设$m$与$n^2$同阶）
首先，这道题空间没法搞树状数组套线段树之类的，只能整体二分。
在整体二分中的某一次分治时，假设值域为$[l,r]$，值域中点为$mid$，则要统计值域在此范围的询问的子矩形中满足$x\in[l,r]$的$x$的个数。由于$cnt(x1,y1,x2,y2)=cnt(0,0,x2,y2)-cnt(0,0,x2,y1-1)-cnt(0,0,x1-1,y2)+cnt(0,0,x1-1,y1-1)$，将一个询问拆成四个询问，这是一个二维偏序问题，并不需要二维树状数组。可以将所有$x\in[l,r]$的$x$看成修改，和询问一起离线下来，按横坐标排序，纵坐标用普通的树状数组解决。这样做，假设这次分治值域区间长度为$l$，询问个数为$q$，则本次分治时间复杂度为$\Theta((l+q)(\log l+\log q))$，算法整体复杂度为$\Theta((n^2+m)(\log n^2+\log m)\log n^2)=\Theta(n^2\log^2n)$。
上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=505,M=60005;
int n,q,a[N][N],ans[M],x,y,xx,yy,z;
int aa[N*N],lenaa,dx[M],o2p[M],o2p1[M],o2p2[M];
struct node{int v,x,y;}o[N*N];
bool operator <(node a,node b){return a.v<b.v;}
struct node2{int x1,y1,x2,y2,k,id;}o2[M];
struct node3{int x,y,id;}o3[N*N*2];
bool operator <(node3 a,node3 b){return a.x!=b.x?a.x<b.x:!a.id&&b.id;}
int sz[N*N];
void ddxg(int x,int y){for(;x<=lenaa;x+=x&-x)sz[x]+=y;}
int qjcx(int x){int y=0; for(;x;x-=x&-x)y+=sz[x]; return y;}
void getans(int l,int r,int o2l,int o2r)
{
if(l==r){for(int i=o2l;i<=o2r;i++)ans[o2[o2p[i]].id]=aa[o[l].v]; return;}
int mid=l+r>>1,len1=0,len2=0,len3=0;
for(int i=l;i<=mid;i++)o3[++len3]={o[i].x,o[i].y,0};
for(int i=o2l;i<=o2r;i++)
{
x=o2[o2p[i]].x1; y=o2[o2p[i]].y1; xx=o2[o2p[i]].x2; yy=o2[o2p[i]].y2;
o3[++len3]={xx,yy,i}; o3[++len3]={x-1,y-1,i};
o3[++len3]={xx,y-1,-i}; o3[++len3]={x-1,yy,-i};
}
sort(o3+1,o3+len3+1);
for(int i=1;i<=len3;i++)
if(!o3[i].id)ddxg(o3[i].y,1);
else if(o3[i].id>0)dx[o3[i].id]+=qjcx(o3[i].y);
else dx[-o3[i].id]-=qjcx(o3[i].y);
for(int i=o2l;i<=o2r;i++)
if(o2[o2p[i]].k<=dx[i])o2p1[++len1]=o2p[i];
else o2[o2p[i]].k-=dx[i],o2p2[++len2]=o2p[i];
for(int i=1;i<=len1;i++)o2p[o2l+i-1]=o2p1[i];
for(int i=1;i<=len2;i++)o2p[o2l+len1+i-1]=o2p2[i];
fill(dx+o2l,dx+o2r+1,0);
for(int i=l;i<=mid;i++)ddxg(o[i].y,-1);
if(len1)getans(l,mid,o2l,o2l+len1-1);
if(len2)getans(mid+1,r,o2l+len1,o2r);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",a[i]+j),aa[++lenaa]=a[i][j];
sort(aa+1,aa+lenaa+1);
lenaa=unique(aa+1,aa+lenaa+1)-aa-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=lower_bound(aa+1,aa+lenaa+1,a[i][j])-aa,o[i*n-n+j]={a[i][j],i,j};
sort(o+1,o+n*n+1);
for(int i=1;i<=q;i++)scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&z),o2[i]={x,y,xx,yy,z,i},o2p[i]=i;
getans(1,n*n,1,q);
for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}
```