Rooks Defenders

题意

一个二维图，每次可以选择1:坐标放置车，2:移除车，3:问一个矩阵图当前是不是被攻击。

被攻击的条件：每一行都有车，或者每一列都有车。

思路

方法一

用一个线段树或者树状数组进行单点修改和区间求和操作即可，用两个数组记录该行/列是不是需要修改即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
 
LL n,q;
int t,a,b,c,d;
int hang[200010],lie[200010];
int hh[200010],hl[200010];
int lowbit(int x){
    return x&-x;
}
void add(int x,int cc,int *tr){
    for(int i=x;i<=n;i+= lowbit(i)) tr[i]+=cc;
}
int sum(int x,int *tr){
    int res=0;
    for(int i=x;i;i-= lowbit(i)) res+=tr[i];
    return res;
}
 
 
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=q;i++){
        scanf("%d",&t);
        if(t==1){
            scanf("%d%d",&a,&b);
            hang[a]++;
            lie[b]++;
            if(sum(a,hh)-sum(a-1,hh)==0) add(a,1,hh);
            if(sum(b,hl)-sum(b-1,hl)==0) add(b,1,hl);
        }else if(t==2){
            scanf("%d%d",&a,&b);
            hang[a]--;
            lie[b]--;
            if(hang[a]==0) add(a,-1,hh);
            if(lie[b]==0) add(b,-1,hl);
        }else{
            scanf("%d%d%d%d",&a,&b,&c,&d);
//            cout<<sum(c,hang)- sum(a-1,hang)<<" "<<sum(d,lie)- sum(b-1,lie)<<endl;
            if((sum(c,hh)- sum(a-1,hh))==(c-a+1) || (sum(d,hl)- sum(b-1,hl))==(d-b+1)){
                puts("Yes");
            }else{
                puts("No");
            }
        }
    }
    return 0;
}

D:（二分+拓扑排序+最长路）

题意

求一个有向图中长度为k-1的路径，上面的点权的 $MAX(a_u)$ 的最小值，长度为0的路径相当于就选择了一个点。

思路

二分：

我们很难判断最大值到底是什么，所以可以通过二分来先确定值。再来找有没有满足这种情况的路径。

对每次二分，都需只能访问小于该值的点。

拓扑排序：

我们将满足条件的边用来建图，拓扑排序中有两种情况满足长度：

①一条长度为k-1的链

②一个环

第一种情况是拓扑排序的一个重要运用

对于第二种情况。我们可以记录这个图有多少个边，我们每次拓扑进行的删边操作都是可以记录的，那么如果存在一些边无法被删除的情况，说明这些边是形成了环的，同时这些边在我们二分的条件下都是合法边。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
LL n,m,k;
LL a[200010],mx;
LL v,u;
vector<int> mp[200010];
LL dp[200010];

bool ck(LL x){
    vector<int> mpp[200010];
    queue<int> qu;
    memset(dp,0,sizeof dp);
    int tot=0;

    for(int i=1;i<=n;i++){   //建立新图
        if(a[i]>x) continue;
        for(int nx:mp[i]){
            if(a[nx]>x) continue;
            mpp[i].push_back(nx);
            dp[nx]++;  //入度
            tot++; //一共有多少边
        }
    }

    for(int i=1;i<=n;i++){
        if(dp[i]==0&&a[i]<=x) qu.push(i);
    }

    LL len=0;

    while(qu.size()){
        int sz=qu.size();
        while(sz--){
            int ft=qu.front();
            qu.pop();
            for(int nx:mpp[ft]){
                dp[nx]--;
                tot--;
                if(dp[nx]==0){
                    qu.push(nx);
                }
            }
        }
        len++;
        if(len>=k) return true;
    }
    if(tot>0)return true;
    return false;
}

int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),mx=max(mx,a[i]);
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&u,&v);
        mp[u].push_back(v);
    }

    LL l=0,r=mx,mid;
    while(l<r){
        mid = (l+r)>>1;
        if(ck(mid)){
            r=mid;
        }else{
            l=mid+1;
        }
    }

    if(l==mx&&!ck(mx)){
        printf("-1\n");
    }else{
        printf("%lld\n",l);
    }
    return 0;
}

总结

拓扑排序判断是第几个层次，常用代码。这个方法也可以用来求有向无环图的最长路。（无向图可用两次搜索详见：大臣的旅费）

LL len=0;

while(qu.size()){
    int sz=qu.size();
    while(sz--){
        int ft=qu.front();
        qu.pop();
        for(int nx:mpp[ft]){
            dp[nx]--;
            tot--;
            if(dp[nx]==0){
                qu.push(nx);
            }
        }
    }
    len++;
    if(len>=k) return true;
}