题解：P5066 [Ynoi Easy Round 2014] 人人本着正义之名

Loyal_Soldier · 2026-08-10 15:40:20 · 题解

思路

发现这个 3, 4, 5, 6 操作有点特殊，考虑模拟一下：

0, 0, 0, 1, 1, 1, 0, 0, 1

对于整个序列进行 3 操作后：

0, 0, 1, 1, 1, 1, 0, 1, 1

发现，对于全是 0 的极长连续段，右端点向左收缩了一位，全是 1 的极长连续段，左端点向左扩展了一位。

同理，手玩这下操作，发现都是极长连续段进行扩展/收缩，那么对于这些量，可以打标记处理。

但是直接上 ODT 由于数据不随机会被卡，于是考虑使用平衡树维护 ODT，每个节点对应一个极长连续段，我使用的是 FHQ Treap。

除了常规平衡树维护的东西，我们需要维护区间对应的编号、区间中 1 的个数、0/1 极长连续段个数、最小 0/1 极长连续段，以及扩展/收缩对应的标记。

接下来讲解代码。

新建节点

没什么好说的。

//[l, r] 全部为 v 的极长连续段
struct node {
    int ls, rs;
    int pri, siz;
    int key;
    int l, r;//区间编号 
    int sum, cnt[2];//1 的个数，子树中 0/1 段个数 
    int Min[2];//子树中最小 0/1 段 
    int ltag[2], rtag[2];//0/1 段左右移动量 
} t[MAXN];
void new_node(int &p, int l, int r, int v) {
    p = ++cnt;
    t[p].ls = t[p].rs = 0;
    t[p].siz = 1;
    t[p].ltag[0] = t[p].ltag[1] = t[p].rtag[0] = t[p].rtag[1] = 0;
    t[p].key = v;
    t[p].pri = rand();
    t[p].l = l;
    t[p].r = r;
    t[p].sum = (r - l + 1) * v;
    t[p].cnt[v] = 1;
    t[p].cnt[v ^ 1] = 0;
    t[p].Min[v] = r - l + 1;
    t[p].Min[v ^ 1] = inf;
}

pushup

还是没什么好说的，注意不是这个区间颜色的 Min 以及 cnt，直接取左右子树最小值/相加即可。

void pushup(int u) {
    if (!u) return;
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
    t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum + (t[u].r - t[u].l + 1) * t[u].key;
    t[u].cnt[t[u].key] = t[t[u].ls].cnt[t[u].key] + t[t[u].rs].cnt[t[u].key] + 1;
    t[u].cnt[t[u].key ^ 1] = t[t[u].ls].cnt[t[u].key ^ 1] + t[t[u].rs].cnt[t[u].key ^ 1];
    t[u].Min[t[u].key] = min(min(t[t[u].ls].Min[t[u].key], t[t[u].rs].Min[t[u].key]), t[u].r - t[u].l + 1);
    t[u].Min[t[u].key ^ 1] = min(t[t[u].ls].Min[t[u].key ^ 1], t[t[u].rs].Min[t[u].key ^ 1]);
}

maketag & pushdown

其实也没什么好说的，只是对于 Min_{0/1} 和 sum，需要增加对应偏移量。

void maketag(int u, int lt0, int lt1, int rt0, int rt1) {//左右移动量 
    if (!u) return;
    t[u].Min[0] += rt0 - lt0;
    t[u].Min[1] += rt1 - lt1;
    t[u].ltag[0] += lt0, t[u].ltag[1] += lt1;
    t[u].rtag[0] += rt0, t[u].rtag[1] += rt1;
    t[u].sum += t[u].cnt[1] * (rt1 - lt1);
    if (t[u].key) t[u].l += lt1, t[u].r += rt1;
    else t[u].l += lt0, t[u].r += rt0;
}
void pushdown(int u) {
    if (!u) return;
    if (t[u].ltag[0] || t[u].ltag[1] || t[u].rtag[0] || t[u].rtag[1]) {
        maketag(t[u].ls, t[u].ltag[0], t[u].ltag[1], t[u].rtag[0], t[u].rtag[1]);
        maketag(t[u].rs, t[u].ltag[0], t[u].ltag[1], t[u].rtag[0], t[u].rtag[1]);
        t[u].ltag[0] = t[u].ltag[1] = t[u].rtag[0] = t[u].rtag[1] = 0;
    }
}

分裂与合并

由于维护的是连续段，所以不能向通常 FHQ Treap 一样分裂，而需要按左右端点分裂分出一个区间。

//按左端点分裂 
void splitl(int u, int x, int &l, int &r) {
    if (u == 0) { l = r = 0; return; }
    pushdown(u);
    if (t[u].l <= x) {
        l = u;
        splitl(t[u].rs, x, t[u].rs, r);
    } else {
        r = u;
        splitl(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
//按右端点分裂 
void splitr(int u, int x, int &l, int &r) {
    if (u == 0) { l = r = 0; return; }
    pushdown(u);
    if (t[u].r < x) {
        l = u;
        splitr(t[u].rs, x, t[u].rs, r);
    } else {
        r = u;
        splitr(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
int merge(int l, int r) {
    if (l == 0 || r == 0) return l + r;
    if (t[l].pri < t[r].pri) {
        pushdown(l);
        t[l].rs = merge(t[l].rs, r);
        pushup(l);
        return l;
    } else {
        pushdown(r);
        t[r].ls = merge(l, t[r].ls);
        pushup(r);
        return r;
    }
}

区间赋值

首先分出 [l, r] 对应区间，设 L, R 为区间中最左/最右连续段。

处理左边界：
- 若 L 对应颜色与修改的 val 相同，则修改区间和 L 可以合并成一个极长连续段。
- 否则，L 左端点到 l - 1 单独一个极长连续段。
处理右边界，与左边界同理：
- 若 R 对应颜色与修改的 val 相同，则修改区间和 R 可以合并成一个极长连续段。
- 否则，r + 1 到 R 右端点单独一个极长连续段。
若分裂出的左半区间的最右区间，与 [l, r] 同色，则和修改区间合并成一个极长连续段，并删除这一段区间。
若分裂出的右半区间的最左区间，与 [l, r] 同色，则和修改区间合并成一个极长连续段，并删除这一段区间。

//Left 和 Right 是找到子树种最左/右连续段
void assign(int l, int r, int v) {
    int x, y, p;
    splitr(root, l, x, y);
    splitl(y, r, y, p);
    int L = Left(y), R = Right(y);
    // 处理左边界
    if (t[L].key == v) l = t[L].l;
    else {
        int tmp;
        new_node(tmp, t[L].l, l - 1, t[L].key);
        x = merge(x, tmp);
    }
    // 处理右边界
    if (t[R].key == v) r = t[R].r;
    else {
        int tmp;
        new_node(tmp, r + 1, t[R].r, t[R].key);
        p = merge(tmp, p);
    }
    // 检查 x 的右边界是否与新区间同色
    if (x) {
        L = Right(x);
        if (t[L].key == v) {
            l = t[L].l;
            splitr(x, t[L].l, x, L);
        }
    }
    // 检查 p 的左边界是否与新区间同色
    if (p) {
        R = Left(p);
        if (t[R].key == v) {
            r = t[R].r;
            splitr(p, t[R].r + 1, R, p);
        }
    }
    int tmp;
    new_node(tmp, l, r, v);
    root = merge(merge(x, tmp), p);
}

扩展/收缩区间

首先分出 [l, r] 对应区间，设 L, R 为区间中最左/最右连续段。

若 L 颜色与对应颜色相同，则分裂出去，合并到左半区间。
若 R 颜色与对应颜色不同，则分裂出去，合并到右半区间。

最后 maketag。

void update(int l, int r, int col, int lt0, int lt1, int rt0, int rt1) {
    int x, yp, p;
    splitr(root, l, x, yp);
    splitl(yp, r, yp, p);
    if (!yp) {
        root = merge(x, p);
        return;
    }
    int L = Left(yp), R = Right(yp);
    //切出去归 x 
    if (t[L].key == col) {
        splitl(yp, t[L].l, L, yp);
        x = merge(x, L);
        if (!yp) {
            root = merge(x, p);
            return;
        }
        L = Left(yp);
    }
    //扩出去归 p 
    if (t[R].key != col) {
        splitr(yp, t[R].l, yp, R);
        p = merge(R, p);
        if (!yp) {
            root = merge(x, p);
            return;
        }
        R = Right(yp);
    }
    maketag(yp, lt0, lt1, rt0, rt1);
    root = merge(merge(x, yp), p);
}

查询

分裂出来的和减去最左/右多出的即可。

int query(int l, int r) {
    int x, y, p;
    splitr(root, l, x, y);
    splitl(y, r, y, p);
    int L = Left(y), R = Right(y);
    //减去左右边多出的 
    int res = t[y].sum - (l - t[L].l) * t[L].key - (t[R].r - r) * t[R].key;
    root = merge(merge(x, y), p);
    return res;
}

处理空段

处理每次操作完后平衡树中的空段。

如果当前段是空段（l > r）：
- 如果是序列中最左边的段或者最右边，直接分裂出去。
- 否则，设 L, R 为当前区间最左/右极长连续段，将 [L, R] 重新作为一个极长连续段。
否则继续递归。

void clear(int u) {
    if (!u) return;
    pushdown(u);
    //删除空段 
    if (t[u].l > t[u].r) {
        int x, y, p;
        if (t[u].l == 1) {
            splitr(root, 1, x, root);
            return;
        }
        if (t[u].r == n) {
            splitl(root, n, root, x);
            return;
        }
        splitr(root, t[u].r, x, y);
        splitl(y, t[u].l, y, p);
        int L = Left(y), R = Right(y);
        new_node(y, t[L].l, t[R].r, t[L].key);
        root = merge(merge(x, y), p);
        return;
    }
    //可能是空段，继续递归
    if (min(t[t[u].ls].Min[0], t[t[u].ls].Min[1]) <= 0) {
        clear(t[u].ls);
        return;
    }
    if (min(t[t[u].rs].Min[0], t[t[u].rs].Min[1]) <= 0) clear(t[u].rs);
}

主函数

建树之后处理操作即可。

cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
//建树 
int idx = 1;
while (idx <= n) {
    int r = idx;
    while (r < n && a[idx] == a[r + 1]) r++;
    int tmp;
    new_node(tmp, idx, r, a[idx]);
    root = merge(root, tmp);
    idx = r + 1;
}
int last = 0;
while (m--) {
    int op, l, r;
    cin >> op >> l >> r;
    l ^= last, r ^= last;
    //处理操作 
    if (op == 1) {
        assign(l, r, 0);
    } else if (op == 2) {
        assign(l, r, 1);
    } else if (op == 3) {
        update(l, r, 1, 0, -1, -1, 0);
    } else if (op == 4) {
        update(l, r, 0, 1, 0, 0, 1);
    } else if (op == 5) {
        update(l, r, 0, -1, 0, 0, -1);
    } else if (op == 6) {
        update(l, r, 1, 0, 1, 1, 0);
    } else if (op == 7) {
        last = query(l, r);
        cout << last << '\n';
    }
    //清除空段 
    while (min(t[root].Min[0], t[root].Min[1]) <= 0) clear(root);
}