CF1379F2 题解

· · 题解

居然想出了 2800 /cy

其实这道题就是一个简单的思维和数据结构题，感觉评不上 2800。

思路

首先，对于一个 2 \times 2 的块里，一定会放且仅放一个国王，因为首先每个块最多放一个（否则会攻击），而因为一共只有 n 个块，所以每个格子必须放。

现在考虑禁止一个块放国王会产生什么贡献。

如果禁止放的这个在块的右下角，则这个块的左上角一定放国王。此时这个块上面的块的右下角、左上角的块的右下角、左面的块的右下角都不能放了，而这些块就只能放左上角了。一直进行这样的操作，最终会使当前这个块左上角的那个矩形内的块都只能放左上角。

如上图，圆表示黑色格子，粗的线段画出了 2 \times 2 的块。此时在 (4,4) 处禁止放国王，则上面都确定了。

同理，如果禁止放的这个在块的左上角，则这个块右下的所有块都只能放右下角。

对于没有撤销操作，则只需对每个放的操作检查它覆盖的位置之前是否有不一样的覆盖。比如当前禁止了某个块的右下角，则它上面的位置如果有之前已经禁止了某个块的左上角，则产生冲突。

对于撤销操作，减去现在冲突的个数即可。

也就是说我们需要解决以下的问题：有若干个四元组 (op_i,t_i,x_i,y_i)，对于每个三元组求出来：

这显然是三维偏序，直接 cdq 分治即可。

参考代码

代码中的 op 与上文中的恰好相反。

#include<bits/stdc++.h>
using namespace std;

int n,m,q;

int cnt=0;
struct CDQ
{
    int op,t,x,y,f;
} c[1000010];
bool cmp1(CDQ x,CDQ y)
{
    return x.t<y.t;
}
bool cmp2(CDQ x,CDQ y)
{
    return x.x==y.x?x.y<y.y:x.x<y.x;
}

int ans[1000010];

int tot=0,cl[10000010];

int tree[1000010];

void upd(int wz,int x)
{
    while(wz<=1e6+5)
    {
        cl[++tot]=wz;
        tree[wz]+=x;
        wz+=wz&-wz;
    }
}

int get_sum(int wz)
{
    int sum=0;
    while(wz)
    {
        sum+=tree[wz];
        wz-=wz&-wz;
    }
    return sum;
}

void clear()
{
    for(int i=1; i<=tot; ++i) tree[cl[i]]=0;
    tot=0;
}

void cdq(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    sort(c+l,c+mid+1,cmp2),sort(c+mid+1,c+r+1,cmp2);
    int now=l;
    clear();
    for(int i=mid+1; i<=r; ++i)
    {
        while(now<=mid && c[now].x<=c[i].x)
        {
            if(c[now].op==1) upd(c[now].y,c[now].f);
            ++now;
        }
        if(c[i].op==2)
        {
            ans[c[i].t]+=c[i].f*get_sum(c[i].y);
        }
    }
    clear();
    now=mid;
    for(int i=r; i>mid; --i)
    {
        while(now>=l && c[now].x>=c[i].x)
        {
            if(c[now].op==2) upd(c[now].y,c[now].f);
            --now;
        }
        if(c[i].op==1)
        {
            ans[c[i].t]+=c[i].f*(get_sum(1e6)-get_sum(c[i].y-1));
        }
    }
}

map<int,map<int,int> > vis;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,q,x,y;
    cin>>n>>m>>q;
    for(int i=1; i<=q; ++i)
    {
        cin>>x>>y;
        int op=(x%2==1?1:2);
        if(!vis[x][y])
        {
            c[i]={op,i,x,y,1};
            vis[x][y]=1;
        }
        else
        {
            c[i]={op,i,x,y,-1};
            vis[x][y]=0;
        }
    }
    sort(c+1,c+q+1,cmp1);
    cdq(1,q);
    int sum=0;
    for(int i=1; i<=q; ++i)
    {
        sum+=ans[i];
        puts(sum?"NO":"YES");
    }
    return 0;
}