题解 P1558 【色板游戏】

· · 题解

这道题小蒟蒻做时间也不短了，前两天看人发讨论求助就从新看了下这道题，

然后突然发现了一个不珂学的事情= =:

居然没有珂朵莉树的题解？珂学家们会很伤心的QAQAQ嘤嘤嘤！

果断补充一发。qwqwq

观察题目：有区间推平操作。珂朵莉树常规骗分操作，代码简单，思路清晰，调试方便。

如果想要深入♂学习珂朵莉树的话可以右转 CF896C QωQ

这里只是大概介绍一下：

一开始每个点都有一个set，区间覆盖（推平）的时候只需要把该区间内所有的set都删掉用一个大set替换之，其他所有操作直接暴力枚举区间内所有的set进行处理就可以了。

直接贴代码：

#include<iostream>
#include<cstring>
#include<cstdio> 
#include<algorithm>
#include<cmath>
#include<set>
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;++i)
#define IT set<node>::iterator
using namespace std;

int n,m,c,r,t,x,y,z,cnt,num,anss,kk;
int b[35];
char ch;

inline void in(re int &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9'){
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
}

inline void out(re int a){
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

struct node{ 
    int l,r;
    mutable int v;
    node(int L,int R=-1,int V=0): l(L),r(R),v(V) {}
    bool operator <(const node &o)const{
        return l<o.l;
    }
};
set<node> s;

IT split(int pos){ //找到要推平的位置的地址
    IT it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos)
      return it;
    --it;
    int L=it->l;
    int R=it->r;
    int V=it->v;
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}

void assign_val(int l,int r,int val=0){ //简单的推平操作
    IT itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,val));
}

int query(int l,int r){ //暴力枚举统计区间
    int res=0;
    memset(b,0,sizeof(b));
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl){
        int qwq=itl->v;
        b[qwq]=1;
    }
    FOR(i,1,30)
      if(b[i])
        ++res;
    return res;
}

int main(){
    in(n),in(kk),in(m);
    s.insert(node(1,n,1));
    FOR(i,1,m){
        cin>>ch;
        if(ch=='C'){
            in(x),in(y),in(z);
            if(x>y)
              swap(x,y);
            assign_val(x,y,z);
        }
        else{
            in(x),in(y);
            if(x>y)
              swap(x,y);
            out(query(x,y));
            puts("");
        }
    }
}