专栏文章

P14449 [ICPC 2025 Xi'an R] Catch the Monster

zziyistudy
P14449题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mina44h9
此快照首次捕获于
2025/12/01 23:03
3 个月前
此快照最后确认于
2025/12/01 23:03
3 个月前
查看原文
此篇为 dmy 比赛复盘。
对于这种连续区间查询的题，容易想到双指针维护对于每个 ii，能到达最远的不违反条件的 jj，这样就能 O(1)O(1) 查询了。
这道题推一推不难发现满足条件的树是一棵毛毛虫树，即对于每个点，不存在其有大于等于三个度数大于等于 22 的点。
我们考虑每次加入点怎么快速维护。枚举每条包含该点的边， (u,v)(u,v) 是不难维护的，唯一的问题是，当加入这条边后，uu 的度数增加，可能会导致与 uu 相邻的一个点受到影响，直接枚举时间是无法承受的。但发现只有当 duu=1du_u=1 的那个点加入时，当 uu 又连一条边时他不会收到更新，而其他的由于本来 duu≥2du_u\ge 2，就会计入答案。所以不妨维护 lasilas_i，每次加边时 lasulas_u 加上 vv 等，虽然当 duu≥2du_u\ge2 后这个 laslas 无意义，但由于我们只需要当 duu=2du_u=2 时多更新，此时这个值是确定值，维护完毕。删除点同理。
CPP
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=998244353;
// head
const int N=1e6+5;
vector<vector<int>> G(N);
int ans[N];
int du[N],cnt[N],las[N],sum;
void upd(int x,int k)
{
    sum-=(cnt[x]>=3);
    cnt[x]+=k;
    sum+=(cnt[x]>=3);
}
signed main() 
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        G[u].pb(v);
        G[v].pb(u);
    }
    for(int i=n,j=n;i>=1;i--){
        for(auto it:G[i]){
            if(it<i||it>j) continue;
            du[it]++,du[i]++;
            if(du[it]==2) upd(las[it],1);
            if(du[i]==2) upd(las[i],1);
            if(du[it]>=2) upd(i,1);
            if(du[i]>=2) upd(it,1);
            las[it]+=i,las[i]+=it;
        }
        while(sum)
        {
            for(auto it:G[j]){
                if(it<i||it>j) continue;
                if(du[j]>=2) upd(it,-1);
                las[it]-=j;
                du[it]--;
                if(du[it]==1) upd(las[it],-1);
            }
            sum-=(cnt[j]>=3);
            j--;
        }
        ans[i]=j;
    }
    while(q--)
    {
        int l,r;cin>>l>>r;
        if(ans[l]>=r) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...