题解 P1527 【[国家集训队]矩阵乘法】

发一个\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)。

上代码：

#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]);
}