P6138 IOI2012 骑马比武竞赛

· · 题解

20240225

今日随机：P6138 IOI2012 骑马比武竞赛

今天不是数数题。

首先给出一个经典的区间合并思路：把元素视为点，区间合并就是给区间内所有点新建一个父节点。

对于本题，骑士视为叶节点点，然后根据操作建树。

对于任何时候，我们需要一种快速的方法找出排名为 x 的个节点。

可以维护一个 tag E，令 E 根据节点位置单调。

使用 BIT 维护 E。

初始时把叶子节点的 E 设为他们的位置。

合并一个区间 [s,e]，可以新建一个节点 x，使 E_x 等于区间最左端点的 E 即可。

每个点最多向父亲连一次边，加上查找的时间消耗：O((n + c)\log^2{n})。

然后是求解。

我们可以枚举每一个位置 i，显然 i 被打败的区间包括在 i 左或右边第一个大于 i 的位置。

求 LCA，胜利轮数即为 \operatorname{dep}(i) - \operatorname{dep}(LCA) - 1。

特殊的，判断 i 是否存在 i 左或右边第一个大于 i 的位置。

瓶颈在于求 LCA，是 O(\log{n}) 的。

总时间复杂度：O((n + c)\log^2{n} + n\log{n})。

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,c,r,tsz;
struct tree
{
    vector<int> to[200005];
    int dp[200005],f[200005][25];
    void dfs(int x = tsz,int fa=0)
    {
        dp[x] = dp[fa] + 1;
        f[x][0] = fa;
        for(int i=1;i<=20;i++)f[x][i] = f[f[x][i-1]][i-1];
        for(auto ed : to[x])dfs(ed,x);
    }
    int getlca(int x,int y)
    {
        if(dp[x] < dp[y])swap(x,y);
        if(dp[x] != dp[y])for(int i=20;i>=0;i--)
        {
            if(dp[f[x][i]] >= dp[y])x = f[x][i];
        }
        if(x == y)return x;
        for(int i=20;i>=0;i--)
        {
            if(f[x][i] != f[y][i])
            {
                x = f[x][i];
                y = f[y][i];
            }
        }
        return f[x][0];
    }
}t;
struct buildtree{
    int sz;
    int bit[100005],Etag[100005];
    set<pii> s;
    int lowbit(int x){return x & -x;}
    void add(int pos,int v){for(;pos<=n;pos+=lowbit(pos))bit[pos]+=v;}
    int que(int pos){int r=0;for(;pos>=1;pos-=lowbit(pos))r+=bit[pos];return r;}
    void insert(int id,int E)
    {
        add(E,1);
        s.insert(pii(E,id));
        Etag[E] = id;
        sz++;
    }
    void erase(int id,int E)
    {
        add(E,-1);
        s.erase(pii(E,id));
        Etag[E] = 0;
        sz--;
    }
    int getrkxE(int x)
    {
        int l=1,r=n;
        while(l < r)
        {
            int E = (l + r) >> 1;
            if(que(E) >= x)r = E;
            else l = E + 1;
        }
        return l;
    }
}b;
int k[100005],pre[100005],sub[100005];
int sol(int pos)
{
    int d = 0;
    if(pre[pos] != 0)
    {
        d = max(d,t.dp[t.getlca(pos,pre[pos])]);
    }
    if(sub[pos] != n+1)
    {
        d = max(d,t.dp[t.getlca(pos,sub[pos])]);
    }
    return t.dp[pos] - d - 1;
}
signed main()
{
    cin>>n>>c>>r;
    for(int i=1,tp;i<=n-1;i++)
    {
        cin>>tp;
        if(tp > r)k[i] = 1;
    }
    for(int i=1,tp=0;i<=n;i++)
    {
        pre[i] = tp;
        if(k[i])tp = i;
    }
    for(int i=n,tp=n+1;i>=1;i--)
    {
        sub[i] = tp;
        if(k[i-1])tp = i;
    }
    for(int i=1;i<=n;i++)
    {
        tsz++;
        b.insert(i,i);
    }
    for(int i=1,s,e;i<=c;i++)
    {
        cin>>s>>e;
        s++;
        e++;
        tsz++;
        int E = b.getrkxE(s);
        t.to[tsz].push_back(b.Etag[E]);
        b.erase(b.Etag[E],E);
        for(int j=s+1;j<=e;j++)
        {
            int _E = b.getrkxE(s);
            t.to[tsz].push_back(b.Etag[_E]);
            b.erase(b.Etag[_E],_E);
        }
        b.insert(tsz,E);
    }
    t.dfs();
    int pos = 1,ans = sol(1);
    for(int i=2;i<=n;i++)
    {
        int tp = sol(i);
        if(tp > ans)
        {
            ans = tp;
            pos = i;
        }
    }
    cout<<pos-1;
    return 0;
}