P8078 [WC2022] 秃子酋长

· · 题解

\mathcal{Question}

P8078 [WC2022] 秃子酋长

题目意思比较清晰，这里就不解释了。

\mathcal{Solution}

我们考虑莫队。

首先 \Theta (n\sqrt{n}\ log\ n) 的莫队是挺好想的。

我们可以用一个数据结构来维护每次我们两个指针枚举到的序列，答案暴力修改即可。

如果是平衡树之类的，那么插入的时间复杂度为 \Theta(log\ n)，如果是 vector，那么插入的时间复杂度为 \Theta(\text{玄学})，二分查找的时间复杂度为 \Theta(log\ n)。

无论怎么样，这个时间复杂度是不能通过此题的。

由于加入的时候时间复杂度总是 \Theta(log\ n)。（也许是我太菜了想不出来）

所以我们可以考虑只删不加回滚莫队。

对于每个数的删除，我们可以考虑用链表。

但是 C++ 自带的链表无法快速的找到一个数的位置。（也许又是我逊了）

我们就考虑双向链表。

双向链表就是将链表用数组的形式储存下来。

我们定义两个数组 L 和 R。

$R_i$ 表示 $i$ 节点右边的节点编号。 我们可以以权值作为关键字来建立双向链表。 意思就是 $L_{a_i}$ 表示 $i$ 节点左边的节点的权值，$R_{a_i}$ 表示 $i$ 节点右边的节点的权值。 于是我们就可以快速的找到一个数的位置。（也就是它左右两边的数） 双向链表的插入和删除也都是 $\Theta(1)$ 的。 在 $a$ 和 $b$ 节点之间插入 $x$ 节点。 ```cpp L[x] = a; R[x] = b; R[a] = x; L[b] = x; ``` 把 $a$ 和 $b$ 节点之间的 $x$ 节点删除。 ```cpp L[a] = b; R[b] = a; ``` 然后我们暴力更新答案即可。 时间复杂度 $\Theta(n\sqrt{n})$。 但是这道题的第 $17$ 个测试点并不是很友好。 我们加上快读，并且将块长设成 $1000$ 就能卡过去了。 ## $\mathcal{Code}

十年 OI 一场空，不开 long long 见祖宗。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
static char buf[100010], *p1 = buf, *p2 = buf;
#define gc p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100010, stdin), p1 == p2)? EOF: *p1++
inline int read() {
    int res = 0, w = 0;
    char c = gc;
    while (!isdigit(c))
        w ^= c == '-', c = gc;
    while (isdigit(c))
        res = (res << 1) + (res << 3) + (c ^ 48), c = gc;
    return (w? -res: res);
}
inline void write(LL x) {
    static int sta[50], top = 0;
    if (x < 0) putchar('-'), x = -x;
    do {
        sta[ top++ ] = x % 10;
        x /= 10;
    } while (x);
    while (top) putchar(sta[ --top ] + 48);
    putchar('\n');
}
const int MAXN = 5e5 + 10;
int n, m, a[MAXN], siz, bnum, belong[MAXN];
LL ans[MAXN];
struct query {
    int l, r, id;
}q[MAXN];
int L[MAXN], R[MAXN], cnt[MAXN];
inline bool cmp(query a, query b) {
    if (belong[ a.l ] ^ belong[ b.l ]) return belong[ a.l ] < belong[ b.l ];
    return a.r > b.r;
}
inline int doit(int Qnum, int x) {
    memset(L, 0, sizeof(L));
    memset(R, 0, sizeof(R));
    memset(cnt, 0, sizeof(cnt));
    int left = (x - 1) * siz + 1;
    int l = left, r = q[Qnum].r, i = Qnum, last = 0;
    LL now = 0;
    for (int i = l; i <= r; i++)
        cnt[ a[i] ] = i;
    for (int i = 1; i <= n; i++)
        if (cnt[i]) {
            if (last) now += 1ll * abs(cnt[i] - cnt[last]);
            R[last] = i;
            L[i] = last;
            last = i;
        }
    for (; belong[ q[i].l ] == x; i++) {
        while (r > q[i].r) {
            int Left = L[ a[r] ], Right = R[ a[r] ];
            if (Left) now -= 1ll * abs(cnt[ a[r] ] - cnt[Left]);
            if (Right) now -= 1ll * abs(cnt[Right] - cnt[ a[r] ]);
            if (Left && Right) now += 1ll * abs(cnt[Right] - cnt[Left]);
            R[Left] = Right;
            L[Right] = Left;
            cnt[ a[r] ] = 0;
            r--;
        }
        LL temp = now;
        while (l < q[i].l) {
            int Left = L[ a[l] ], Right = R[ a[l] ];
            if (Left) now -= 1ll * abs(cnt[ a[l] ] - cnt[Left]);
            if (Right) now -= 1ll * abs(cnt[Right] - cnt[ a[l] ]);
            if (Left && Right) now += 1ll * abs(cnt[Right] - cnt[Left]);
            R[Left] = Right;
            L[Right] = Left;
            cnt[ a[l] ] = 0;
            l++;
        }
        ans[ q[i].id ] = now;
        now = temp;
        for (int j = left; j < l; j++) {
            int Left = L[ a[j] ], Right = R[ a[j] ];
            R[Left] = a[j];
            L[Right] = a[j];
            cnt[ a[j] ] = j;
        }
        l = left;
    }
    return i;
}
int main() {
    n = read(); m = read(); siz = 1000; bnum = (n - 1) / siz + 1;
    for (int i = 1; i <= bnum; i++)
        for (int j = (i - 1) * siz + 1; j <= min(n, i * siz); j++)
            belong[j] = i;
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= m; i++) {
        q[i].l = read(); q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int Qnum = 1;
    for (int i = 1; i <= bnum; i++) {
        Qnum = doit(Qnum, i);
    }
    for (int i = 1; i <= m; i++)
        write(ans[i]);
    return 0;
}

完结撒花 ^_の