【模板】不带删整体二分 / P8955 「VUSC」Card Tricks 题解

zesqwq · 2023-02-11 15:15:33 · 题解

【模板】不撤销整体二分 / P8955 「VUSC」Card Tricks 题解

~~ds 真好玩~~

你考虑整体二分，区间或上一个值是很好维护的操作，但是我们发现整体二分中有一个操作叫做撤销最后的操作，我认为撤销操作并不方便维护，于是我们引入一个新的技巧，叫做不撤销的整体二分。

整体二分实际上是一个线段树的结构，一般的整体二分都是从根节点向下递归判定每个询问的答案在左区间还是右区间，然后递归解决，类似 \text{dfs}，但是我们可以用一个不太一样的做法：从上至下对每一层进行判定答案在左区间还是右区间。

具体的，假设我们二分答案 \in [1, 8]，则过程如下：

先扫描根节点 [1, 8] 把存的询问判定是否符合要求并将符合的下放到 [1, 4]，不符合的放到 [5, 8]；
再扫描第二层节点 [1, 4]，[5, 8]，并判定将其存储的询问需要放入左孩子还是右孩子；
再扫描第三层节点 [1, 2]，[3, 4]，[5, 6]，[7, 8] ......；
再扫描第四层节点，得出每个询问的答案。

也就是我们对线段树的每一层节点进行遍历，然后把当前节点的询问放入左儿子或右儿子，遍历完一层之后重置回初始状态。

你发现因为你是从左到右遍历的，因此你可以规避掉撤销这个操作。

或许可以叫它整体二分二次离线？

在实际的实现中，你甚至不需要把这个线段树建立出来，只需要进行 \lceil \log n \rceil 次二分，每次记录每个询问的答案范围，然后将询问按照左或右端点排序，扫描询问，挨个判定使答案范围缩小一半即可。

然后这道题直接使用这个技巧就可以解决了。卡常就自己试试吧，很快乐的。

时间复杂度 O(n \log n \log V)，空间复杂度 O(n)。

代码十分简短：

int n, m, p;
int a[N], lzy[N << 1], w[N << 1];
struct OP {
    int l, r, v;
} q[N];
struct Answer {
    int l, r, id;
    inline bool operator<(const Answer &b) const { return r < b.r; }
} ans[N];
int h[30], cnt = 0;
inline void maketag(int u, int v) { w[u] |= v, lzy[u] |= v; }
inline void pushdown(int u, int M) {
    if (lzy[u]) maketag(M << 1, lzy[u]), maketag(M << 1 | 1, lzy[u]), lzy[u] = 0;
}
void update(int u, int L, int R, int l, int r, int v) {
    if (L > r || R < l || ((w[u] | v) == w[u])) return;
    if (L >= l && R <= r) return maketag(u, v);
    int M = L + R >> 1;
    pushdown(u, M);
    update(M << 1, L, M, l, r, v), update(M << 1 | 1, M + 1, R, l, r, v);
    w[u] = w[M << 1] & w[M << 1 | 1];
}
int query(int u, int L, int R, int x) {
    if (L == R) return w[u];
    int M = L + R >> 1;
    pushdown(u, M);
    if (x <= M) return query(M << 1, L, M, x);
    return query(M << 1 | 1, M + 1, R, x);
}
void build(int u, int L, int R) {
    lzy[u] = 0;
    if (L == R) return void(w[u] = a[L]);
    int M = L + R >> 1;
    build(M << 1, L, M), build(M << 1 | 1, M + 1, R), w[u] = w[M << 1] & w[M << 1 | 1];
}
int as[N];
int main() {
    read(n), read(m), read(p);
    for (int i = 1; i <= n; i++) read(a[i]), ans[i].l = 1, ans[i].r = m + 1, ans[i].id = i;
    for (int i = 1; i <= m; i++) read(q[i].l), read(q[i].r), read(q[i].v);
    for (int k = 1; k <= __lg(n) + 1; k++) {
        sort(ans + 1, ans + n + 1), build(1, 1, n);
        int nr = 1;
        for (int i = 1; i <= n; i++) {
            if (ans[i].l == ans[i].r) continue;
            while (nr <= (ans[i].l + ans[i].r >> 1)) update(1, 1, n, q[nr].l, q[nr].r, q[nr].v), ++nr;
            if (query(1, 1, n, ans[i].id) <= p) ans[i].l = (ans[i].l + ans[i].r >> 1) + 1;
            else ans[i].r = (ans[i].l + ans[i].r) >> 1;
        }
    }
    for (int i = 1; i <= n; i++) as[ans[i].id] = ans[i].l;
    for (int i = 1; i <= n; i++) write(as[i] <= m ? as[i] : -1), IO::putc(' ');
    do_flush();
    return 0;
}