题解归档 - cf2187C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2187C
• 本地来源：problems/cf2187C/idea.md
• 题目链接：https://codeforces.com/contest/2187/problem/C
• 原始标题：cf2187C Jerry and Tom

思路

cf2187C Jerry and Tom

Pattern: non-crossing forward edges give a dominator tree.

Build:

• Let p[u]=max(u+1, all extra endpoints from u) for u<n.
• Make a rooted tree with parent p[u], root n; dep[n]=0, dep[u]=dep[p[u]]+1.
• This p[u] is exactly the brute-force nxt[u].

Why p[u] is the first common mandatory point:

• If p[u]=u+1, there is only the base first step.
• If there is an edge (u,p[u]), then any edge starting strictly inside (u,p[u])
  cannot end after p[u]; otherwise it crosses (u,p[u]).
• Therefore every path from u+1 is trapped inside the interval until it reaches
  p[u], while the direct edge u->p[u] skips every intermediate vertex.
• So every u -> n path must pass through p[u], and no vertex between them can
  be mandatory.

Claim:

• For every u<n, Jerry's worst first move is to p[u]=max(out[u]).
• p[u] is the immediate dominator of u: every path from u to n must pass through p[u], and the edge u->p[u] exists.
• Therefore the adversarial Jerry path is the parent chain in this tree rooted at n.
• For pair (x,y), the minimax value is
  f(x,y)=dep[y]-dep[lca(x,y)].
  when dep[y]<=dep[x]; otherwise Tom cannot force a positive catch before Jerry
  escapes to n, so it contributes 0.
• Positive contribution condition:
  dep[y]<=dep[x] and y is not an ancestor of x.
  If y is an ancestor of x (including y=n), Tom can just wait, so the
  required Tom moves are 0.

Game interpretation:

• Tom only needs to climb from y toward the first common ancestor of x and
  y; the number of Tom moves is the number of tree-parent jumps from y to
  lca(x,y).
• Jerry chooses the direct mandatory jump x->p[x] whenever it delays this catch
  the most. Detours inside the same interval only give Tom no harder instance,
  because they cannot leave before the same mandatory boundary.

Sum:

• Need sum over ordered pairs with dep[y]<=dep[x] of dep[y]-dep[lca(x,y)].
• Process vertices by decreasing depth. Active set contains all x with dep[x]>=current depth.
• For a query vertex y, contribution is dep[y]*active_count - sum_x dep[lca(x,y)].
• Maintain sum_x dep[lca(x,y)] by path-add from root to each active x
  (excluding root) and path-sum from root to y with HLD:
  every common non-root ancestor contributes 1, and the number of common
  non-root ancestors is exactly dep(lca(x,y)).

Non-crossing / bracket view:

• Extra edges are laminar or disjoint intervals (shared endpoints allowed).
• Edge (u,p[u]) is the closing bracket/boundary of u's current interval.
• No internal interval can jump outside this boundary, hence the dominator tree is
  the interval nesting skeleton. Disjoint blocks simply meet later on the base
  chain.

Verification:

• Sample.
• Random non-crossing graphs for n<=8 against full minimax brute-force recursion.

代码

来源：problems/cf2187C/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll fa[maxn+5],dep[maxn+5],siz[maxn+5],son[maxn+5],top[maxn+5],dfn[maxn+5],rk[maxn+5],lazy[maxn*4+5],sum[maxn*4+5],cur;
vector<ll>ss[maxn+5],vv[maxn+5];
void pushdown(ll rt,ll l,ll r){
    ll mid;
    if(!lazy[rt]) return;
    mid=(l+r)/2;
    lazy[rt*2]+=lazy[rt];
    lazy[rt*2+1]+=lazy[rt];
    sum[rt*2]+=lazy[rt]*(mid-l+1);
    sum[rt*2+1]+=lazy[rt]*(r-mid);
    lazy[rt]=0;
}
void update(ll rt,ll l,ll r,ll x,ll y,ll v){
    ll mid;
    if(x>y) return;
    if(x<=l and r<=y){
        lazy[rt]+=v;
        sum[rt]+=v*(r-l+1);
        return;
    }
    pushdown(rt,l,r);
    mid=(l+r)/2;
    if(x<=mid) update(rt*2,l,mid,x,y,v);
    if(y>mid) update(rt*2+1,mid+1,r,x,y,v);
    sum[rt]=sum[rt*2]+sum[rt*2+1];
}
ll query(ll rt,ll l,ll r,ll x,ll y){
    ll mid,ans;
    if(x>y) return 0;
    if(x<=l and r<=y) return sum[rt];
    pushdown(rt,l,r);
    mid=(l+r)/2;
    ans=0;
    if(x<=mid) ans+=query(rt*2,l,mid,x,y);
    if(y>mid) ans+=query(rt*2+1,mid+1,r,x,y);
    return ans;
}
void addpath(ll x,ll n){
    while(top[x]!=n){
        update(1,1,n,dfn[top[x]],dfn[x],1);
        x=fa[top[x]];
    }
    if(x!=n) update(1,1,n,dfn[n]+1,dfn[x],1);
}
ll qpath(ll x,ll n){
    ll ans;
    ans=0;
    while(top[x]!=n){
        ans+=query(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(x!=n) ans+=query(1,1,n,dfn[n]+1,dfn[x]);
    return ans;
}
int main(){
    ll t,n,m,i,j,k,zc,pd,dq,cnt,ans,mx,rt,x,y;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        vv[0].clear();
        for(i=1;i<=n;i++){
            ss[i].clear();
            vv[i].clear();
            fa[i]=dep[i]=siz[i]=son[i]=top[i]=dfn[i]=rk[i]=0;
        }
        for(i=1;i<n;i++) fa[i]=i+1;
        for(i=1;i<=m;i++){
            scanf("%lld%lld",&x,&y);
            fa[x]=max(fa[x],y);
        }
        for(i=1;i<n;i++) ss[fa[i]].push_back(i);
        mx=0;
        for(i=n-1;i>=1;i--){
            dep[i]=dep[fa[i]]+1;
            mx=max(mx,dep[i]);
        }
        for(i=1;i<=n;i++) siz[i]=1;
        for(i=1;i<n;i++){
            siz[fa[i]]+=siz[i];
            if(siz[i]>siz[son[fa[i]]]) son[fa[i]]=i;
        }
        cur=0;
        stack<pair<ll,ll> >st;
        st.push({n,n});
        while(!st.empty()){
            x=st.top().first;
            y=st.top().second;
            st.pop();
            while(x){
                top[x]=y;
                dfn[x]=++cur;
                rk[cur]=x;
                for(auto j:ss[x]) if(j!=son[x]) st.push({j,j});
                x=son[x];
            }
        }
        for(i=1;i<=n;i++) vv[dep[i]].push_back(i);
        for(i=1;i<=4*n;i++) lazy[i]=sum[i]=0;
        ans=0;
        cnt=0;
        for(i=mx;i>=0;i--){
            for(auto j:vv[i]){
                addpath(j,n);
                cnt++;
            }
            for(auto j:vv[i]) ans+=dep[j]*cnt-qpath(j,n);
        }
        printf("%lld\n",ans);
    }
    return 0;
}