题解 CF1679C Rooks Defenders

· · 题解

树状数组裸题。

在 CF 这种拼手速的场合谁会打线段树啦

题意

给定一个 n × n 的正方形棋盘，支持如下操作：

  1. 在 (x,y) 格放入一个棋子“车”。

  2. 移除 (x,y) 格的“车”。

  3. 给定一个子矩形，其左上角格为 (x_1,y_1)，右下角格为 (x_2,y_2)，查询该子矩形是否被棋盘上所有“车”的攻击范围覆盖。

保证操作合法。

思路

单点修改 + 区间查询 + CF 特有的手速要求（码量要小）= 树状数组。

维护两个树状数组，分别对应行和列。

查询时只需要查询子矩形对应的行区间和列区间有多少行 / 列被覆盖即可。

只要行和列中至少有一个区间被完全覆盖，那么就是满足要求的，反之一定不满足。

插入的时候不能想当然，要判断当前行 / 列是否已经有棋子，如果有的话就不能插入。因为一行 / 列上的多个棋子只能覆盖一行 / 列。

删除同理，要判断移除当前棋子后本行 / 列是否无棋子，如果当前棋子是本行 / 列的最后一个，那么就需要删除，反之不需要。

这个判断只要额外开两个数组就可以了。

时间复杂度 O(nlogn) ，空间复杂度 O(n) 。

代码

#include<bits/stdc++.h>
#define ll long long
#define db double
#define R read()
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
using namespace std;
inline ll read() {
    ll s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f*=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
inline void write(ll x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10),x%=10;
    putchar('0'+x);
}//Don't use it for CF.
inline void wk(ll x){write(x);putchar(' ');}
inline void we(ll x){write(x);putchar('\n');}
const ll maxn=1e5+5;
ll t1[maxn],t2[maxn];
ll n,m;
ll lb(ll x){
    return x&-x;
}//lowbit
void add_1(ll p,ll x){
    while(p<=n){
        t1[p]+=x;
        p+=lb(p); 
    }
}
void add_2(ll p,ll x){
    while(p<=n){
        t2[p]+=x;
        p+=lb(p); 
    }
}//两个插入/删除函数
ll sum_1(ll x){
    ll res=0;
    while(x>0){
        res+=t1[x];
        x-=lb(x);
    }
    return res;
}
ll sum_2(ll x){
    ll res=0;
    while(x>0){
        res+=t2[x];
        x-=lb(x);
    }
    return res;
}//两个查询
ll cnt_1[maxn],cnt_2[maxn];//两个记录数组，用来记录当前行/列棋子数
signed main(){
    n=R,m=R;
    for(ll i=1;i<=m;i++){
        ll opt=R;
        if(opt==1){
            ll x=R,y=R;
            if(!cnt_1[x])add_1(x,1);
            if(!cnt_2[y])add_2(y,1);//坑点：只有当本行/列之前不存在棋子时才需要插入
            cnt_1[x]++,cnt_2[y]++;
        }
        if(opt==2){
            ll x=R,y=R;
            if(cnt_1[x]==1)add_1(x,-1);
            if(cnt_2[y]==1)add_2(y,-1);//同上
            cnt_1[x]--,cnt_2[y]--;
        }
        if(opt==3){
            ll ans=0,flag=0,fl=0;
            ll x=R,y=R,l=R,r=R;
            ans=sum_1(l)-sum_1(x-1);//查询行
            if(ans<l-x+1)flag=1;
            ans=sum_2(r)-sum_2(y-1);//查询列
            if(ans<r-y+1)fl=1;
            if(flag==1&&fl==1)cout<<"NO"<<endl;//只有行列都没能完全覆盖时才不满足要求
            else cout<<"YES"<<endl;//反之满足要求
        }
    }
    return 0;
}