[USACO23JAN] Tractor Paths P 题解

· · 题解

题意：

先将所有区间按左端点（或右端点）从小到大排序。

对于第一问，一个显然的贪心是每次选取与当前区间相交的最靠右的区间，这启发我们建出一棵树：树上的 i 号结点表示第 i 个区间，i 号结点的父亲是与第 i 个区间相交的最靠右的区间所对应的结点，记之为 p_i。

我们的贪心对应的树上操作就是从 a 号结点开始，每次跳向父亲结点，直到当前结点编号不比 b 小为止。记最终所在的结点编号为 t，则第一问的答案即为 a 到 t 的距离，利用倍增即可快速求出 t。注意：实际上最后一步需要恰好跳到 b 号结点，但是为了叙述方便，我们这里记录的 t 是 a 的一个祖先结点。

对于第二问，我们首先需要明确每次从某个结点能跳到哪些结点。不难发现，对于一个结点 i，其能跳到的结点编号构成的集合为 (i,p_i]，那么它们具体在树的哪些位置呢？

考虑建树的过程，我们每次按编号从小到大加入结点，可以发现当加入一个结点时，其所有儿子的结点编号必然是当前所有暂无父亲的结点编号中最小的若干个（可以为零个）。由此我们可以证明，对于所有深度相同的结点编号，以及一个结点所有儿子的结点编号，它们都必然构成一段连续的区间，而这也使这棵树拥有了极好的性质。

接下来我们以下图这棵树为例（当然实际情况中树的形态可以千奇百怪，这里为了美观画了一棵对称的树）：

形象化地，若 i 号结点与 j 号结点同深度且 i<j，则我们称 i 号结点在 j 号结点左边，j 号结点在 i 号结点右边。可以发现，(i,p_i] 这段区间对应了 i 右边的所有结点以及 p_i 及其左边的所有结点。依旧形象化地，我们将跳到 i 右边的某结点的一次操作称为 “ 向右跳 ”，将跳到 p_i 及其左边的某结点的一次操作称为 “ 向左上跳 ”。

回到原问题，我们分两种情况讨论。

1. b=t 或 b 在 t 左边。

由于每次操作只能使当前结点的深度减少 0（向右跳）或 1（向左上跳），而 b 又与 t 同深度，故我们每次只能向左上跳以保证操作次数最少。

以 a=10,b=30,t=32 为例，则下图中的绿色结点即为可经过的所有结点：

不难发现，绿色结点的编号在 [i,p_i] 内且 DFS 序也在一段区间内，这是经典的二维数点问题，离线下来用树状数组维护即可。

2. b 在 t 的某个子结点右边。

同样地，通过分析深度变化可知，我们需恰好进行一次向右跳的操作，其余操作均为向左上跳。

以 a=3,b=32,t=34 为例，则下图中的蓝色结点即为可经过的所有结点：

不难发现，蓝色结点的编号在 [i,p_i] 内且 DFS 序在两段区间内，也是个二维数点问题。

至此，我们便用 O(n\log n+q\log n) 的时间复杂度解决了本题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,x,y,L,tmp,timer,l[200009],r[200009],dfn[200009],dis[200009],ans[200009],bit[200009],anc[200009][20];
char d[400009],s[200009];
struct st{ll x,w,id;};
vector <ll> to[200009];
vector <st> qr[200009];
inline ll read(){
    ll s = 0,w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    return s * w;
}
void upd(ll x,ll y){for (;x <= n;x += x & (-x)) bit[x] += y;}
ll query(ll x){ll res = 0; for (;x;x -= x & (-x)) res += bit[x]; return res;}
void build(){
    ll cl = 0,cr = 0,pos = 1;
    for (ll i = 1;i <= 2 * n;i += 1){
        if (d[i] == 'L') l[++ cl] = i;
        else r[++ cr] = i;
    }
    for (ll i = 2;i <= n;i += 1){
        while (pos < i && (i == n || l[i + 1] > r[pos])){
            anc[pos][0] = i;
            to[i].emplace_back(pos ++);
        }
    }
}
void dfs(ll u){
    dfn[u] = ++ timer;
    for (ll i = 1;i <= L;i += 1) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (ll i = 0;i < to[u].size();i += 1) dfs(to[u][i]);
}
void add(ll l,ll r,ll L,ll R,ll id){
    qr[r].emplace_back((st){R,1,id});
    qr[r].emplace_back((st){L - 1,-1,id});
    qr[l - 1].emplace_back((st){R,-1,id});
    qr[l - 1].emplace_back((st){L - 1,1,id});
}
void work(){
    for (ll i = 1;i <= n;i += 1){
        if (s[i] == '1') upd(dfn[i],1);
        for (ll j = 0;j < qr[i].size();j += 1){
            ans[qr[i][j].id] += query(qr[i][j].x) * qr[i][j].w;
        }
    }
}
int main(){
    n = read(),q = read(),L = log2(n),scanf("%s",d + 1),scanf("%s",s + 1);
    build(),dfs(n);
    for (ll i = 1;i <= q;i += 1){
        x = read(),y = read(),dis[i] = 1;
        ll tmp = x;
        for (ll j = L;j >= 0;j -= 1){
            if (!anc[x][j] || anc[x][j] >= y) continue;
            dis[i] += 1 << j,x = anc[x][j];
        }
        if (dfn[tmp] < dfn[y]) add(tmp,y,1,dfn[tmp],i),add(tmp,y,dfn[y],n,i);
        else add(tmp,y,dfn[y],dfn[tmp],i);
    }
    work();
    for (ll i = 1;i <= q;i += 1) printf("%lld %lld\n",dis[i],ans[i]);
    return 0;
}