2018-ACetic_ACid/AugTrain-01/B

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 2100
int n,m,T,Q;
int a[N][N],f[N][N];
int l[N],r[N],sta[N],top;
int main()
{
    scanf("%d%d%d%d",&n,&m,&T,&Q);
    for(int i=1,x,_x,y,_y;i<=T;i++)
    {
        scanf("%d%d%d%d",&x,&_x,&y,&_y);
        for(int j=x+1;j<=_x;j++)
            for(int k=y+1;k<=_y;k++)
                a[j][k]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
            if(a[i][j]==1) a[i][j]=0;
            else a[i][j]=a[i][j+1]+1;
    int tmpL,tmpR;
    for(int j=1;j<=m;j++)
    {
        top=0;
        sta[top]=0;
        for(int i=1;i<=n;i++)
        {
            while(top>0 && a[sta[top]][j]>a[i][j]) top--;
            l[i]=sta[top];
            sta[++top]=i;
        }
        top=0;
        sta[top]=n+1;
        for(int i=n;i>=1;i--)
        {
            while(top>0 && a[sta[top]][j]>=a[i][j]) top--;
            r[i]=sta[top];
            sta[++top]=i;
        }
        for(int i=1;i<=n;i++)
        {
            tmpL=i-l[i]; tmpR=r[i]-i;
            f[1][a[i][j]]++;
            f[min(tmpL,tmpR)+1][a[i][j]]--;
            f[max(tmpL,tmpR)+1][a[i][j]]--;
            f[tmpL+tmpR+1][a[i][j]]++;
        }
    }
    for(int j=1;j<=m;j++)
        for(int i=1;i<n;i++)
            f[i+1][j]+=f[i][j];
    for(int j=1;j<=m;j++)
        for(int i=1;i<n;i++)
            f[i+1][j]+=f[i][j];
    for(int i=1;i<=n;i++)
        for(int j=m;j>1;j--)
            f[i][j-1]+=f[i][j];
    for(int i=1,x,y;i<=Q;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",f[x][y]);
    }
    return 0;
}
}}}

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 2100
int n,m,T,Q;
int a[N][N],f[N][N];
int l[N],r[N],sta[N],top;
int main()
{
    scanf("%d%d%d%d",&n,&m,&T,&Q);
    for(int i=1,x,_x,y,_y;i<=T;i++)
    {
        scanf("%d%d%d%d",&x,&_x,&y,&_y);
        for(int j=x+1;j<=_x;j++)
            for(int k=y+1;k<=_y;k++)
                a[j][k]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
            if(a[i][j]==1) a[i][j]=0;
            else a[i][j]=a[i][j+1]+1;
    int tmpL,tmpR;
    for(int j=1;j<=m;j++)
    {
        top=0;
        sta[top]=0;
        for(int i=1;i<=n;i++)
        {
            while(top>0 && a[sta[top]][j]>a[i][j]) top--;
            l[i]=sta[top];
            sta[++top]=i;
        }
        top=0;
        sta[top]=n+1;
        for(int i=n;i>=1;i--)
        {
            while(top>0 && a[sta[top]][j]>=a[i][j]) top--;
            r[i]=sta[top];
            sta[++top]=i;
        }
        for(int i=1;i<=n;i++)
        {
            tmpL=i-l[i]; tmpR=r[i]-i;
            f[1][a[i][j]]++;
            f[min(tmpL,tmpR)+1][a[i][j]]--;
            f[max(tmpL,tmpR)+1][a[i][j]]--;
            f[tmpL+tmpR+1][a[i][j]]++;
        }
    }
    for(int j=1;j<=m;j++)
        for(int i=1;i<n;i++)
            f[i+1][j]+=f[i][j];
    for(int j=1;j<=m;j++)
        for(int i=1;i<n;i++)
            f[i+1][j]+=f[i][j];
    for(int i=1;i<=n;i++)
        for(int j=m;j>1;j--)
            f[i][j-1]+=f[i][j];
    for(int i=1,x,y;i<=Q;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",f[x][y]);
    }
    return 0;
}