题解 P1558 【色板游戏】

· · 题解

想要试试更加简单直白的线段树吗？

PS：食用本篇题解需要一定线段树基础

（小声：说起来你们应该都注意到到读入时l和r可以是反着的了吧）

首先看到这道题，区间更新，区间查询，还是比较好想到线段树的。具体在于怎么建树，树里要维护什么，怎么维护。

这里提供一种比较直白的思路，没错，就是直接维护每个节点上是什么颜色！

这个思路肯定大家都进行过尝试，但是却不好想到怎么维护，毕竟一段区间里可以是五颜六色的（所以这里就出现了状压流派，直接压缩状态维护五颜六色区间），不好直接求到，但如果往“深”处想，这个区间五颜六色，这个区间的儿子们呢？儿子们的儿子们呢？所以向下找总会遇到完整区间的，大不了一直找到叶节点去。

所以我们的思路就是从上往下找，找到颜色完整的区间就停止向下并统计答案。

(这种方法应该可以解决颜色较多的情况下，速度上略逊于状压，但适用范围更广）

细节方面：

维护什么：颜色+是否只有一种颜色（如果后者不满足则前者的值没有意义）

建树：正常建树，并将所有节点的颜色涂为1并标记为完整区间。

修改：如果当前遍历到的区间不是修改区间的子集则当前区间的完整性被破坏（可能你会问如果那个区间原本就是A颜色，又被涂上A颜色怎么办，这个可以通过一个上传操作实现，等会儿会提到），一直找到被修改区间完全包含的区间，同时中途会有下放操作以保证区间内数据的正确性

查询：从根节点开始向下找，一直找到完整区间为止，中途和正常线段树一样会有下放操作以保证区间内数据的正确性，注意要有颜色判重的操作，可以直接用暴力的bool标记判断，记得每次查询要初始化一遍（要是没这个初始化的话，不管有多少种颜色我都能跑（小优越））

上传：(本人喜欢叫做update,但主流叫法好像是pushup?)如果这个区间左儿子，右儿子都是完整的，并且颜色相同，那么这个区间就是完整的，颜色与左儿子/右儿子相同。

下放：(本人喜欢叫做spread,但主流叫法好像是pushdown?)如果这个区间完整，那么他的左儿子和右儿子也可以被染成完整的区间，颜色与这个区间相同。

更细的细节看代码吧

#include <bits/stdc++.h>
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define mx 100005
using namespace std;
struct node//个人比较喜欢结构体版的线段树
{
    int l, r, clr;//左右端点以及区间里是什么颜色
    bool all;//区间完整性
};
inline int FS()//以老婆名字命名的标准快读
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
node tree[mx << 2];
bool mark[35];//提到的判重标记
void spread(int p)//下放
{
    tree[ls(p)].clr = tree[p].clr;
    tree[rs(p)].clr = tree[p].clr;
    tree[ls(p)].all = tree[rs(p)].all = 1;
}
void update(int p)//上传
{
    if (tree[ls(p)].all && tree[rs(p)].all && tree[ls(p)].clr == tree[rs(p)].clr)
    {
        tree[p].clr = tree[ls(p)].clr;
        tree[p].all = 1;
    }
}
void build(int l, int r, int p)//建树
{
    tree[p].l = l;
    tree[p].r = r;
    tree[p].all = 1;
    tree[p].clr = 1;//一开始时，所以区间都是完整的并且颜色为1
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, ls(p));
    build(mid + 1, r, rs(p));
}
void change(int l, int r, int c, int p)//染色
{
    if (l <= tree[p].l && tree[p].r <= r)//如果被完全包含
    {
        tree[p].all = 1;//区间会完完整整地被染成c号颜色
        tree[p].clr = c;
        return;
    }
    if (tree[p].all)//如果是完整的就需要下放以维护正确性（不完整的不能下放，因为不完整的区间的颜色根本没有意义）
        spread(p);
    tree[p].all = 0;//能走到这一步来，说明当前区间肯定不是染色区间的子集，同时又含有部分染色区间，那么它的完整性会被破坏
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid)
        change(l, r, c, ls(p));
    if (mid + 1 <= r)
        change(l, r, c, rs(p));
    update(p);//上传更新操作
}
int ans;//用于累计查询的颜色数量
void qry(int l, int r, int p)//查询
{
    if (tree[p].all)//一直找到区间完整为止
    {
        if (!mark[tree[p].clr])//判重
        {
            mark[tree[p].clr] = 1;
            ans++;
            return;
        }
        return;
    }
    if (tree[p].all)
        spread(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid)
        qry(l, r, ls(p));
    if (mid + 1 <= r)
        qry(l, r, rs(p));
    update(p);
}
int main()
{
    int L, T, O;
    L = FS();
    T = FS();
    O = FS();
    build(1, L, 1);
    for (int i = 1, c1, c2, c3; i <= O; i++)
    {
        char ch;
        do
        {
            ch = getchar();
        } while (ch != 'C' && ch != 'P');//防止读入稀奇古怪的空格之类的东西
        if (ch == 'C')
        {
            c1 = FS();
            c2 = FS();
            c3 = FS();
            if(c1 > c2) swap(c1 ,c2);//说出来你可能不信，这东西调了我一个小时
            change(c1, c2, c3, 1);
        }
        else
        {
            c1 = FS();
            c2 = FS();
            memset(mark, 0, sizeof(mark));//别忘了要先清标记哦~
            ans = 0;
            if(c1 > c2) swap(c1 ,c2);
            qry(c1, c2, 1);
            cout << ans << endl;
        }
    }
    return 0;//收工~
}

(这可能是我洛谷上最后一篇题解了吧)