P9995 [Ynoi2000] rspcn 题解

· · 题解

祭最优解：2025/4/1。

不是愚人玩笑！

较为经典的题目。

考虑用 odt 维护有序的段，总段数 n+m。需要维护值域的合并分裂，容易想到线段树分裂。

具体地，每个段维护一棵权值线段树，其叶子结点上维护 cnt,cfi，分别表示该段中，值 v 的数量以及是否首次出现。其余结点就是两儿子信息的和。

查询前缀答案，找到 x 所在的段，这个段的贡献容易计算；而对于其前面的段的贡献，需要再用一棵树状数组辅助计算。维护 ans_i 表示当前第 i 个位置所在段之前的贡献（不包含所在段），只需区间加，单点查。

线段树分裂需要写分裂大权值和分裂小权值两个版本，个人不喜欢强行写成一个函数。拆成两个函数写更加清晰，且常数更小。此外叶子结点需要特判。

实现上，我将每个段的信息记录在 rt_l 上，便于查询更新。

总时间复杂度 \mathcal O((n+m)\log n)。代码比较长，但是并无太多细节，不难调。

AC record

#define ls(x) t[x].lp
#define rs(x) t[x].rp
int n, q, tot, lstans, rt[MAXN], vis[MAXN];

struct setr {
    struct node {
        int lp, rp, cnt, cfi;
    } t[MAXN << 5];
    int st[MAXN << 5], len;

    il void pushup(int x) {
        t[x].cnt = t[ls(x)].cnt + t[rs(x)].cnt;
        t[x].cfi = t[ls(x)].cfi + t[rs(x)].cfi;
    }

    il int newnode() {
        int o = len ? st[len--] : ++tot;
        t[o].lp = t[o].rp = t[o].cnt = t[o].cfi = 0;
        return o;
    }

    il int merge(int x, int y) {
        if (!x || !y) return x | y;
        st[++len] = y; t[x].cnt += t[y].cnt; t[x].cfi += t[y].cfi;
        t[x].lp = merge(ls(x), ls(y)); t[x].rp = merge(rs(x), rs(y));
        return x;
    }

    il void _split(int x, int &y, int k, int tp) {
        tp ? split(x, y, k) : split2(x, y, k);
    }

    il void split(int x, int &y, int k, const int l = 1, const int r = n) {
        if (!x) return;
        y = newnode();
        if (l == r) {
            t[y].cnt = t[x].cnt - k; t[x].cnt = k;
            return;
        } int lcnt = t[ls(x)].cnt, mid = l + r >> 1;
        if (lcnt < k) split(t[x].rp, t[y].rp, k - lcnt, mid + 1, r);
        else t[y].rp = t[x].rp, t[x].rp = 0;
        if (lcnt > k) split(t[x].lp, t[y].lp, k, l, mid);
        pushup(x); pushup(y);
        if (!t[x].cnt) st[++len] = x;
        if (!t[y].cnt) st[++len] = y;
    }

    il void split2(int x, int &y, int k, const int l = 1, const int r = n) {
        if (!x) return;
        y = newnode();
        if (l == r) {
            t[y].cnt = t[x].cnt - k; t[x].cnt = k;
            return;
        } int rcnt = t[rs(x)].cnt, mid = l + r >> 1;
        if (rcnt < k) split2(t[x].lp, t[y].lp, k - rcnt, l, mid);
        else t[y].lp = t[x].lp, t[x].lp = 0;
        if (rcnt > k) split2(t[x].rp, t[y].rp, k, mid + 1, r);
        pushup(x); pushup(y);
        if (!t[x].cnt) st[++len] = x;
        if (!t[y].cnt) st[++len] = y;
    }

    il void upd(int &x, int l, int r, int k, int c) {
        if (!x) x = newnode();
        if (l == r) return ++t[x].cnt, t[x].cfi = c, void();
        int mid = l + r >> 1;
        k <= mid ? upd(ls(x), l, mid, k, c) : upd(rs(x), mid + 1, r, k, c);
        pushup(x);
    }

    il int kthq1(int x, int l, int r, int k) {
        if (l == r) return t[x].cfi;
        int lcnt = t[ls(x)].cnt, mid = l + r >> 1;
        return lcnt >= k ? kthq1(ls(x), l, mid, k) : kthq1(rs(x), mid + 1, r, k - lcnt) + t[ls(x)].cfi;
    }

    il int kthq2(int x, int l, int r, int k) {
        if (l == r) return t[x].cfi;
        int rcnt = t[rs(x)].cnt, mid = l + r >> 1;
        return rcnt >= k ? kthq2(rs(x), mid + 1, r, k) : kthq2(ls(x), l, mid, k - rcnt) + t[rs(x)].cfi;
    }
} T;

struct BIT {
    int sum[MAXN];

    il void add(int x, int k) {
        while (x <= n) sum[x] += k, x += lowbit(x);
    }

    il int query(int x) {
        int ans = 0;
        while (x) ans += sum[x], x -= lowbit(x);
        return ans;
    }

    il void upd(int l, int r, int k) {
        add(l, k); add(r + 1, -k);
    }
} Tb;

struct node {
    int l, r; mutable int typ;

    il bool operator < (const node &p) const {
        return l < p.l;
    }
}; set <node> odt;

il auto split(int x) {
    if (x > n) return odt.end();
    auto it = odt.lower_bound(node{x});
    if (it != end(odt) && it -> l == x) return it;
    auto [l, r, t] = *--it;
    T._split(rt[l], rt[x], x - l, t); Tb.upd(x, r, T.t[rt[l]].cfi);
    odt.erase(it); odt.emplace(node{l, x - 1, t});
    return odt.emplace(node{x, r, t}).fst;
}

il void sort(int l, int r, int tp) {
    auto itr = split(r + 1), itl = split(l);
    for (auto it = next(itl); it != itr; ++it) {
        Tb.upd(it -> l, it -> r, -T.t[rt[l]].cfi); rt[l] = T.merge(rt[l], rt[it -> l]);
    } odt.erase(itl, itr); odt.emplace(node{l, r, tp});
}

il int _query(int x) {
    auto it = --odt.upper_bound(node{x, inf});
    auto [l, r, typ] = *it;
    return typ ? T.kthq1(rt[l], 1, n, x - l + 1) : T.kthq2(rt[l], 1, n, x - l + 1);
}

int main() {
    read(n, q); int l, r, x;
    rep1(i, 1, n) read(x), odt.emplace(node{i, i, 0}), T.upd(rt[i], 1, n, x, !vis[x]), Tb.upd(i + 1, n, !vis[x]), vis[x] = 1;
    while (q--) {
        read(l, r, x); l ^= lstans; r ^= lstans; x ^= lstans;
        l > r ? sort(r, l, 0) : sort(l, r, 1);
        printf("%d\n", lstans = Tb.query(x) + _query(x));
    }
}