题解：P3776 [APIO2017] 斑斓之地

· · 题解

称黑点为蛇经过的点。

连通块问题可以选择找代表元，但是我们发现这个给出的阻碍会将矩形全部切成没有任何规律的情况，只能放弃这个方法。

但是我们发现，对于网格图来说，我们数点的数量是非常简单的，于是我们考虑欧拉公式 |V|-|E|+|F|=G，即不考虑外面情况的连通块数量。

那么点的个数就是矩形大小减去黑点个数。边的话我们考虑分成横向边和竖向边，则我们可以将左边和上面的点分别代表这两个边是否被黑点破坏。

对于面的情况就是统计有多少个 2\times 2 的无黑点小矩形，即一个黑点会破坏 4 个这样的矩形，那么我们还是将这个黑点破坏的矩形记到它的一个角（比如左上）即可。

但是如果说这个矩形将整条蛇包裹起来，那么这个蛇的空间也变成了一个面，答案需要加一。

剩下的就是主席树板子题了。 :::info[代码]

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
struct Tree{
    struct node{
    int x,l,r;
    #define lc(u) t[u].l
    #define rc(u) t[u].r
    }t[MAXN*40];
    int tot,rt[MAXN];
    void modify(int &u,int l,int r,int p,int v){
        t[++tot]=t[u];
        u=tot;
        t[u].x+=v;
        if(l==r){
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid){
            modify(lc(u),l,mid,p,v);
        }else{
            modify(rc(u),mid+1,r,p,v);
        }
    }
    int query(int u,int v,int l,int r,int ql,int qr){
        if(ql>qr){
            return 0;
        }
        if(ql<=l&&r<=qr){
            return t[v].x-t[u].x;
        }
        int mid=(l+r)>>1,ans=0;
        if(ql<=mid){
            ans+=query(lc(u),lc(v),l,mid,ql,qr);
        }
        if(mid+1<=qr){
            ans+=query(rc(u),rc(v),mid+1,r,ql,qr);
        }
        return ans;
    }
}t[4];
vector<pair<int,int>>vec[4];//点，竖边，横边，四方格左上角
int mix,mxx,miy,mxy,sx,sy;
void add(int x,int y){
    rep(i,0,3){
        vec[i].push_back({x,y});
    }
    mix=min(mix,x);
    mxx=max(mxx,x);
    miy=min(miy,y);
    mxy=max(mxy,y);
    vec[1].push_back({x-1,y});
    vec[2].push_back({x,y-1});
    vec[3].push_back({x-1,y-1});
    vec[3].push_back({x-1,y});
    vec[3].push_back({x,y-1});
}
int r,c,m,Q;
vector<int>gy[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>r>>c>>m>>Q;
    cin>>sx>>sy;
    mix=mxx=sx;
    miy=mxy=sy;
    add(sx,sy);
    rep(i,1,m){
        char c;
        cin>>c;
        if(c=='N'){
            sx--;
        }else if(c=='S'){
            sx++;
        }else if(c=='W'){
            sy--;
        }else{
            sy++;
        }
        add(sx,sy);
    }
    rep(i,0,3){
        sort(vec[i].begin(),vec[i].end());
        vec[i].erase(unique(vec[i].begin(),vec[i].end()),vec[i].end());
        rep(i,1,r){
            gy[i].clear();
        }
        for(auto nd:vec[i]){
            int x=nd.first,y=nd.second;
            if(x<1||x>r||y<1||y>c){
                continue;
            }
            gy[x].push_back(y);
        }
        rep(x,1,r){
            t[i].rt[x]=t[i].rt[x-1];
            for(auto y:gy[x]){
                t[i].modify(t[i].rt[x],1,c,y,1);
            }
        }
    }
    while(Q--){
        int ax,ay,bx,by;
        cin>>ax>>ay>>bx>>by;
        ll V=t[0].query(t[0].rt[ax-1],t[0].rt[bx],1,c,ay,by);
        // cout<<V<<"\n";
        V=1ll*(bx-ax+1)*(by-ay+1)-V;
        ll ES=t[1].query(t[1].rt[ax-1],t[1].rt[bx-1],1,c,ay,by);
        ES=1ll*(bx-ax)*(by-ay+1)-ES;
        ll EH=t[2].query(t[2].rt[ax-1],t[2].rt[bx],1,c,ay,by-1);
        EH=1ll*(bx-ax+1)*(by-ay)-EH;
        ll E=ES+EH;
        ll F=t[3].query(t[3].rt[ax-1],t[3].rt[bx-1],1,c,ay,by-1);
        F=1ll*(bx-ax)*(by-ay)-F;
        if(ax<mix&&mxx<bx&&ay<miy&&mxy<by){
            F++;
        }
        cout<<V-E+F<<"\n";
    }
    return 0;
}

:::