题解 P1558 【色板游戏】

ztyqwq · 2019-04-18 22:01:37 · 题解

稍微看了看题解，貌似没有用珂朵莉树解这道题的qwq...
萌新的第一篇题解，做的不好还请谅解...
珂朵莉树将数据内的连续一段相同数据变为某一个单独的“块”，这一“块”数据会一起被处理。
建立一个结构体

struct node{
    int l, r;
    mutable int val; //简单来说mutable就是强行让不可修改的变量变为可修改的变量
    node(int al, int ar = 0, int aval = 0){l = al; r = ar; val = aval;}
    bool operator< (const node &x) const{
        return l < x.l;
    }
};

用一个set维护珂朵莉树：

set<node> odt;

然后就基本模板，直接上题解吧：

#include<bits/stdc++.h>
using namespace std;
const int MAXT = 30 + 34;

int len, t, o;
struct node{
    int l, r;
    mutable int val;
    node(int al, int ar = 0, int aval = 0){l = al; r = ar; val = aval;}
    bool operator< (const node &x) const{
        return l < x.l;
    }
};
typedef set<node>::iterator _it;
set<node> odt;
_it split(int pos){
    _it it = odt.lower_bound(node(pos));
    if(it != odt.end() && it->l == pos) return it;
    it--;
    int al = it->l, ar = it->r;
    int aval = it->val;
    odt.erase(it);
    odt.insert(node(al, pos - 1, aval));
    return odt.insert(node(pos, ar, aval)).first;
}
void flat(int l, int r, int val){
    _it itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(node(l, r, val));
}
int solve(int l, int r){
    static bool color[MAXT];
    static int ret;
    ret = 0;
    memset(color, 0, sizeof(color));
    _it itr = split(r + 1), itl = split(l);
    for(; itl != itr; itl++) color[itl->val] = true;
    for(int i = 1; i <= t; i++) if(color[i]) ret++;
    return ret;
}

int main(){
    scanf("%d %d %d", &len, &t, &o);
    odt.insert(node(1, len, 1));
    odt.insert(node(len + 1, len + 1, 0));
    for(int i = 1; i <= o; i++){
        static char opt;
        static int a, b, c;
        do{scanf("%c", &opt);}while(opt != 'C' && opt != 'P');
        if(opt == 'C'){
            scanf("%d %d %d", &a, &b, &c);
            if(a > b) swap(a, b);
            flat(a, b, c);
        }
        else if(opt == 'P'){
            scanf("%d %d", &a, &b);
            if(a > b) swap(a, b);
            printf("%d\n", solve(a, b));
        }
    }
    return 1; //抄题解不是好孩子哦 qwq
}

至于为什么要写珂朵莉树：
1.因为它是珂朵莉树（划掉）
2.珂朵莉树代码打起来方便，qwq本蒻蒟打这道题用odt就花了5分钟
3.炫耀一下你的学识qwq

PS：神奇的O2优化
优化前:
优化后:
快了一倍多诶...qwq