题解：P7707 「Wdsr-2.7」百花齐放的太阳花田

原题链接: P7707 「Wdsr-2.7」百花齐放的太阳花田 - 洛谷

分析

如果没有高度的限制, 这个题就是统计区间颜色段数, 非常简单. 但是有高度的限制, 怎么办呢?

如果考虑给每一种 都建一棵线段树, 一是内存会超, 二是时间也不够, 因为查询时需要遍历 的线段树.

调一下思路, 按原下标构建线段树, 每个节点维护其对应区间在不同阈值 下的状态, 即区间内所有满足 的花朵, 按原顺序排列后, 其颜色序列的连续段信息.

由于状态仅随 增大而改变, 且只有当 跨越区间内某个实际的 值时才会更新, 因此每个节点中不同的有效状态数恰好等于该区间内不同 值的种类数, 至多等于区间长度.

此外, 单点修改(新增一枝花)只会影响该点所在路径上的 个线段树节点. 所以整棵线段树的状态数总和不会超过 . 以上是对这种做法可行的简要说明.

这样子, 查询时只需递归覆盖查询区间, 在每个完全覆盖的节点中二分找到阈值 对应的状态, 再按顺序合并各节点返回的状态, 即可得到答案.

实现

线段树每个节点是一个 vector, 其中每一项存储 , 表示区间内 的子序列中, 颜色段有 个, 最左侧颜色为 , 最右侧颜色为 .

修改时, 从左右子树合并不同 的状态. 具体来讲, 如果左右都有 , 那么两个颜色段直接合并. 若只有一侧有 , 则与另一次最大的 合并, 新的状态为 . 为了保证时间复杂度, 可以采用类似于归并排序的方法合并, 这样子每次合并的时间不会超过 , 其中 为区间长度.

颜色段合并: 左右段数相加, 若左侧最右与右侧最左的颜色相同, 则说明合并成一个颜色段, 段数减一.

优化: 由于是不断向后插入的过程, 所以, 如果未插入到这个线段树节点的最右侧, 说明这个线段树节点目前一定不会被查询区间完全包含, 且其区间时不完整的. 因此, 每个节点只需要在插入其区间最右侧的那个位置后做一次合并.

另外, 可以先 resize(), 避免不断申请内存造成的时间开销. 可选进行 shrink_to_fit(), 实测不释放空间也可以正常通过.

查询 时, 如果线段树节点被查询区间完全覆盖, 则二分查找状态中最大的小于等于 的 , 并返回其状态的颜色段信息.

参考代码

通过记录: 记录详情

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 2 * 5e5 + 5, tN = 2 * N, INF = (1ll << 31) - 1;
int h[N], t[N];
struct node {
    int l, r, sum, x;
    node(int _l, int _r, int _sum, int _x) { l = _l, r = _r, sum = _sum, x = _x; }
    node operator+(const node& o) {
        return node(l, o.r, sum + o.sum + (r == o.l ? -1 : 0), max(x, o.x));
    }
};
vector<node> tr[tN];
int lc[tN], rc[tN], cnt = 1;
#define mid ((l + r) / 2)
void pushup(int u) {
    tr[u].reserve(tr[lc[u]].size() + tr[rc[u]].size());
    auto i = tr[lc[u]].begin(), j = tr[rc[u]].begin();
    while (i < tr[lc[u]].end() && j < tr[rc[u]].end()) {
        if (i->x == j->x) {
            tr[u].push_back(*i + *j);
            i++, j++;
        } else if (i->x < j->x) {
            if (j != tr[rc[u]].begin())
                tr[u].push_back(*i + *(j - 1));
            else
                tr[u].push_back(*i);
            i++;
        } else {
            if (i != tr[lc[u]].begin())
                tr[u].push_back(*(i - 1) + *j);
            else
                tr[u].push_back(*j);
            j++;
        }
    }
    while (i < tr[lc[u]].end()) {
        if (tr[rc[u]].empty())
            tr[u].push_back(*i);
        else
            tr[u].push_back(*i + *(j - 1));
        i++;
    }
    while (j < tr[rc[u]].end()) {
        if (tr[lc[u]].empty())
            tr[u].push_back(*j);
        else
            tr[u].push_back(*(i - 1) + *j);
        j++;
    }
    // tr[u].shrink_to_fit();
}
void build(int u, int l, int r) {
    if (l == r) {
        return;
    }
    build(lc[u] = ++cnt, l, mid);
    build(rc[u] = ++cnt, mid + 1, r);
}
void update(int u, int l, int r, int x) {
    if (l == r) {
        tr[u].clear();
        tr[u].push_back(node(t[l], t[l], 1, h[l]));
        // tr[u].shrink_to_fit();
        return;
    }
    if (x <= mid)
        update(lc[u], l, mid, x);
    else
        update(rc[u], mid + 1, r, x);
    tr[u].clear();
    if (x == r) pushup(u);
}
struct Res {
    int l, r, sum;
    Res(int _l, int _r, int _sum) {
        l = _l;
        r = _r;
        sum = _sum;
    }
    Res() { l = r = sum = 0; }
    Res(const node& o) { l = o.l, r = o.r, sum = o.sum; }
    Res operator+(const Res& o) { return Res(l, o.r, sum + o.sum + (r == o.l ? -1 : 0)); }
};
Res query(int u, int l, int r, int xl, int xr, int x) {
    if (xl <= l && r <= xr) {
        auto it = upper_bound(tr[u].begin(), tr[u].end(), node(0, 0, 0, x),
                              [](const node& x, const node& y) { return x.x < y.x; });
        if (it == tr[u].begin()) return Res();
        return Res(*(--it));
    }
    Res rl, rr;
    if (xl <= mid) rl = query(lc[u], l, mid, xl, xr, x);
    if (mid + 1 <= xr) rr = query(rc[u], mid + 1, r, xl, xr, x);
    if (rl.sum == 0) return rr;
    if (rr.sum == 0) return rl;
    return rl + rr;
}
#undef mid
int main() {
    // freopen("subsequence.in", "r", stdin);
    // freopen("subsequence.out", "w", stdout);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    int tn = n + m;
    build(1, 1, tn);
    for (int i = 1; i <= n; i++) {
        update(1, 1, m + n, i);
    }
    int lans = 0, pos = n;
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            l ^= k * lans, r ^= k * lans, x ^= k * lans;
            lans = query(1, 1, tn, l, r, x).sum;
            cout << lans << "\n";
        } else {
            pos++;
            cin >> h[pos] >> t[pos];
            h[pos] ^= k * lans, t[pos] ^= k * lans;
            update(1, 1, tn, pos);
        }
    }
    return 0;
}