题解 P3776 【[APIO2017]斑斓之地】

· · 题解

对于每两块相邻的可用土地（不被蛇占据的土地，下称白点，反之为黑点）之间连一条边，形成图 G，显然题意就是求 G 在横坐标 [a_r,b_r]，纵坐标 [a_c,b_c] 范围内的连通块个数。

显然 G 是一个平面图。根据平面图的欧拉公式，对于连通平面图 G，有 |V|-|E|+|F|=1，其中 |V|,|E|,|F| 分别表示 G 的点数、边数、划分平面数。进而推知：对于任意平面图 G，|V|-|E|+|F|=G 的连通块数。考虑快速计算 |V|,|E|,|F| 的值。

显然 |V|,|E| 都很好计算：以 |V| 为例，相当于计算 [a_r,b_r][a_c,b_c] 内的白点个数，而白点个数较大，反面考虑，转化为计算该区域内黑点个数——由于黑点总数为 O(m) 的，转化为简单二维数点问题，主席树即可解决。|E| 包含两部分边：横边和竖边，分开考虑，每部分也是一个二维数点问题，亦可同上解决。

对于 |F|，原图的平面可能由两部分组成：一是若干 1\times 1 的小正方形，这一部分相当于求四个点都是白点的数量，套用二维数点即可；另外要特别注意，如果矩形范围将蛇的范围完全包住并留有外隙，则 |F| 额外加 1——令黑点的 r,c 最大最小值为 maxr,minr,maxc,minc，则上述条件等价于 a_r<minr 且 b_r>maxr 且 a_c<minc 且 b_c>minc。具体原理留给读者思考。

综上，我们得到了一个时间、空间复杂度均为 O((r+c+m)\log c) 的做法，可以通过此题。特别提醒：特判 m=0，即 S 为空的情况。

代码：

#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

int r=0,c=0,m=0,Q=0;

struct point
{
    int x,y;point(int xx=0,int yy=0):x(xx),y(yy){}
};bool operator<(point a,point b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}
bool operator==(point a,point b){return a.x==b.x&&a.y==b.y;}

vector<point> q[4];
void add_point(int x,int y)
{
    for(int i=0;i<4;i++)q[i].push_back(point(x,y));
    if(x<r){q[1].push_back(point(x+1,y)),q[3].push_back(point(x+1,y));}
    if(y<c){q[2].push_back(point(x,y+1)),q[3].push_back(point(x,y+1));}
    if(x<r&&y<c){q[3].push_back(point(x+1,y+1));}
}

struct PresidentTree
{
    struct nd
    {
        int lc,rc,sum;
    }t[7000000];int used;
    void build(int l,int r,int &k)
    {
        if(!k)k=++used;t[k].sum=0;if(l==r)return;
        int mid=(l+r)>>1;build(l,mid,t[k].lc),build(mid+1,r,t[k].rc);
    }
    int add(int pos,int val,int l,int r,int k)
    {
        int p=++used;t[p]=t[k];
        if(l==r){t[p].sum+=val;return p;}
        int mid=(l+r)>>1;if(pos<=mid){t[p].lc=add(pos,val,l,mid,t[k].lc);}else t[p].rc=add(pos,val,mid+1,r,t[k].rc);
        t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;return p;
    }
    int sum(int x,int y,int l,int r,int k)
    {
        if(l>y||r<x)return 0;
        if(x<=l&&r<=y)return t[k].sum;
        int mid=(l+r)>>1;return sum(x,y,l,mid,t[k].lc)+sum(x,y,mid+1,r,t[k].rc);
    }
}T[4];int rt[4][500000];

char S[500000];

int sum(int i,int ar,int ac,int br,int bc)
{
    if(ar>br||ac>bc)return 0;
    return T[i].sum(ac,bc,1,c,rt[i][br])-T[i].sum(ac,bc,1,c,rt[i][ar-1]);
}

int main()
{
    scanf("%d%d%d%d",&r,&c,&m,&Q);
    int sr=0,sc=0;scanf("%d%d",&sr,&sc);add_point(sr,sc);
    if(m)scanf("%s",S+1);
    int minr=sr,maxr=sr,minc=sc,maxc=sc;
    for(int i=1;i<=m;i++)
    {
        if(S[i]=='N')sr--;if(S[i]=='S')sr++;if(S[i]=='W')sc--;if(S[i]=='E')sc++;
        minr=min(minr,sr),maxr=max(maxr,sr),minc=min(minc,sc),maxc=max(maxc,sc);
        add_point(sr,sc);
    }
    //puts("");
    for(int i=0;i<4;i++)
    {
        sort(q[i].begin(),q[i].end());

        vector<point>::iterator new_end=unique(q[i].begin(),q[i].end());
        q[i].erase(new_end,q[i].end());
        //for(int j=0;j<q[i].size();j++)printf("%d %d\n",q[i][j].x,q[i][j].y);
        T[i].build(1,c,rt[i][0]);
        for(int j=1,p=-1;j<=r;j++)
        {
            rt[i][j]=rt[i][j-1];
            while(p+1<q[i].size()&&q[i][p+1].x==j)
            {
                p++;
                rt[i][j]=T[i].add(q[i][p].y,1,1,c,rt[i][j]);
            }
        }
        //puts("");
    }

    while(Q--)
    {
        int ar=0,ac=0,br=0,bc=0;scanf("%d%d%d%d",&ar,&ac,&br,&bc);long long R=br-ar+1,C=bc-ac+1;
        long long ans1=R*C-sum(0,ar,ac,br,bc);
        long long ans2=(R-1)*C-sum(1,ar+1,ac,br,bc);
        long long ans3=R*(C-1)-sum(2,ar,ac+1,br,bc);
        long long ans4=(R-1)*(C-1)-sum(3,ar+1,ac+1,br,bc);
        if(ar<minr&&br>maxr&&ac<minc&&bc>maxc)ans4++;
        //printf("%lld %lld %lld %lld\n",ans1,ans2,ans3,ans4);
        printf("%lld\n",ans1-ans2-ans3+ans4);
    }
    return 0;
}