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

ziyistudy · 2025-11-11 18:51:16 · 题解

此篇为 dmy 比赛复盘。

对于这种连续区间查询的题，容易想到双指针维护对于每个 i，能到达最远的不违反条件的 j，这样就能 O(1) 查询了。

这道题推一推不难发现满足条件的树是一棵毛毛虫树，即对于每个点，不存在其有大于等于三个度数大于等于 2 的点。

我们考虑每次加入点怎么快速维护。枚举每条包含该点的边， (u,v) 是不难维护的，唯一的问题是，当加入这条边后，u 的度数增加，可能会导致与 u 相邻的一个点受到影响，直接枚举时间是无法承受的。但发现只有当 du_u=1 的那个点加入时，当 u 又连一条边时他不会收到更新，而其他的由于本来 du_u\ge 2，就会计入答案。所以不妨维护 las_i，每次加边时 las_u 加上 v 等，虽然当 du_u\ge2 后这个 las 无意义，但由于我们只需要当 du_u=2 时多更新，此时这个值是确定值，维护完毕。删除点同理。

#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";
    }
}