题目连接

题面：

题意：
给定一个 n ∗ n n*n n∗n 的矩阵，每个点都有一个权值 ( n 2 ) a i , j (n^2)^{a_{i,j}} (n2)ai,j​，左上角为 ( 1 , 1 ) (1,1) (1,1) ，右下角为 ( n , n ) (n,n) (n,n)。
从 ( 1 , 1 ) (1,1) (1,1) 出发，每次只能往右或者往下走。

有 q q q 次查询，每次查询给出一个子矩阵 ( x l , x r , y l , y r ) (xl,xr,yl,yr) (xl,xr,yl,yr)，问如果子矩阵中的点不能走，从 ( 1 , 1 ) (1,1) (1,1) 到 ( n , n ) (n,n) (n,n) 获得的最大权值。

题解：

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=410;
const int maxm=160100;
const int maxp=100100;
const int up=1100;

struct node
{
    int lc,rc;
    ll ans,val;
    llu ha;
}t[maxm<<6];

llu pp[maxm];
ll pn[maxm];
int pre[maxn][maxn],suf[maxn][maxn];
int a[maxn][maxn],rtf[maxn][maxn],rtg1[maxn][maxn],rtg2[maxn][maxn];
int cnt=0,n,q,cm;

int change(int now,int pos,int l,int r)
{
    int p=++cnt;
    t[p]=t[now];
    t[p].ans=(t[p].ans+pn[pos])%mod;
    t[p].val=t[p].val+1;
    t[p].ha=t[p].ha+pp[pos];
    if(l==r) return p;
    int mid=(l+r)>>1,nowpos=cm-pos+1;
    if(nowpos<=mid) t[p].lc=change(t[now].lc,pos,l,mid);
    else t[p].rc=change(t[now].rc,pos,mid+1,r);
    return p;
}

bool askmax(int p,int q,int l,int r)
{
    if(l==r)
        return t[p].val>t[q].val;
    int mid=(l+r)>>1;
    if(t[t[p].lc].ha!=t[t[q].lc].ha) return askmax(t[p].lc,t[q].lc,l,mid);
    else return askmax(t[p].rc,t[q].rc,mid+1,r);
}

bool askmax(int p1,int p2,int q1,int q2,int l,int r)
{
    if(l==r)
        return t[p1].val+t[p2].val>t[q1].val+t[q2].val;
    int mid=(l+r)>>1;
    if(t[t[p1].lc].ha+t[t[p2].lc].ha!=t[t[q1].lc].ha+t[t[q2].lc].ha) return askmax(t[p1].lc,t[p2].lc,t[q1].lc,t[q2].lc,l,mid);
    else return askmax(t[p1].rc,t[p2].rc,t[q1].rc,t[q2].rc,mid+1,r);
}

void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            rtf[i][j]=rtg1[i][j]=rtg2[i][j]=0;
    }
    cnt=0;
}


int main(void)
{
    pp[0]=1;
    for(int i=1;i<maxm;i++)
        pp[i]=pp[i-1]*hp;

    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&q);

        cm=n*n;
        pn[0]=1;
        for(int i=1;i<=cm;i++)
            pn[i]=pn[i-1]*cm%mod;

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                rtf[i][j]=askmax(rtf[i-1][j],rtf[i][j-1],1,cm)?rtf[i-1][j]:rtf[i][j-1];
                rtf[i][j]=change(rtf[i][j],a[i][j],1,cm);
            }
        }

        for(int i=n;i>=1;i--)
        {
            for(int j=n;j>=1;j--)
            {
                rtg1[i][j]=askmax(rtg2[i][j+1],rtg2[i+1][j],1,cm)?rtg2[i][j+1]:rtg2[i+1][j];
                rtg2[i][j]=change(rtg1[i][j],a[i][j],1,cm);
            }
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                pre[i][j]=askmax(rtf[i][pre[i][j-1]],rtg1[i][pre[i][j-1]],rtf[i][j],rtg1[i][j],1,cm)?pre[i][j-1]:j;
            }
        }

        for(int i=n;i>=1;i--)
        {
            for(int j=n;j>=1;j--)
            {
                suf[i][j]=askmax(rtf[i][suf[i][j+1]],rtg1[i][suf[i][j+1]],rtf[i][j],rtg1[i][j],1,cm)?suf[i][j+1]:j;
            }
        }

        int xl,xr,yl,yr;
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d%d",&xl,&xr,&yl,&yr);
            if(askmax(rtf[xr+1][pre[xr+1][yl-1]],rtg1[xr+1][pre[xr+1][yl-1]],rtf[xl-1][suf[xl-1][yr+1]],rtg1[xl-1][suf[xl-1][yr+1]],1,cm))
            {
                printf("%lld\n",(t[rtf[xr+1][pre[xr+1][yl-1]]].ans+t[rtg1[xr+1][pre[xr+1][yl-1]]].ans)%mod);
            }
            else
            {
                printf("%lld\n",(t[rtf[xl-1][suf[xl-1][yr+1]]].ans+t[rtg1[xl-1][suf[xl-1][yr+1]]].ans)%mod);
            }
        }

        init(n);
    }
    return 0;
}