一道罕见的没有卡掉珂朵莉树的良心题（
前置知识：珂朵莉树
可能有些同学还是不太了解珂朵莉树，这里简单说两句。
珂朵莉树，其实就是一种另类的暴力。
只不过它把值相同的区间合并成一个结点，并保存在了 set 里面。
存储方式：
struct Node{
int l,r;
mutable int val;
//意思是区间 [l,r] 内的值全是 val。
//mutable的作用是让val能够被修改。
Node(int L,int R,int V):l(L),r(R),val(V){}
Node(int L):l(L){}
//构造函数，不多说
bool operator<(const Node &o)const{
return l<o.l;
}
//重载小于号运算符，这个会在 split 操作中用到。
};
set<Node>s;
只要有区间赋值操作的数据结构，都可以用珂朵莉树来骗分。
其实这个道理很容易想明白：本来珂朵莉树就是专门存储值相同的区间的，区间赋值一下，刚好成了一个值相同的区间，用珂朵莉树很好存储。
比如一个序列：1 2 3 3 3 4 5 5 6 6 7 8 9 9 9 9
在珂朵莉树中，就会这么存储：
| val | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| l | 1 | 2 | 3 | 6 | 7 | 9 | 11 | 12 | 13 |
| r | 1 | 2 | 5 | 6 | 8 | 10 | 11 | 12 | 16 |
现在要查询区间 的和。
我们发现，左端点 刚好是珂朵莉树第三个节点的左端点，右端点 也刚好是珂朵莉树第六个节点的右端点。
因此，直接把第三个节点到第六个节点的信息统计一下，即：
那么，区间 的和就是 。
但是，如果这个区间不能被几个节点凑出来呢？
比如 ，没法被凑出来。
这就涉及到珂朵莉树的核心操作：split
我们把区间 和区间 分裂一下，变成这样：
| val | 1 | 2 | 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| l | 1 | 2 | 3 | 4 | 6 | 7 | 9 | 11 | 12 | 13 | 14 |
| r | 1 | 2 | 4 | 5 | 6 | 8 | 10 | 11 | 12 | 14 | 14 |
这样，就变成了上一种情况。
split 代码如下：
#define Sit set<Node>::iterator
Sit split(int pos){
Sit it=s.lower_bound(Node(pos));
if(it!=s.end()&&it->l==pos){
return it;
}//如果无需分裂，直接返回
it--;
int L=it->l,R=it->r,V=it->val;
s.erase(it);//删除原节点
s.insert(Node(L,pos-1,V));
return s.insert(Node(pos,R,V)).first;
//分裂成两个子节点
}
这段代码很短，应该不难。
但是如果一直分裂下去，最终总会分裂成许多长度为 的子结点，珂朵莉树会退化成暴力，该怎么办呢？
不要忘了，我们还有区间赋值操作呢！
将一个区间 赋值成 ，其实就相当于在珂朵莉树上插入一个子节点： Node(l,r,x)，然后删除原来的子结点即可。
代码如下：
inline void assign(int l,int r,int v){
Sit itr=split(r+1),itl=split(l);
s.erase(itl,itr);//删除原节点
s.insert(Node(l,r,v));//插入新节点
}
这段代码更短，应该不难。
这样，我们就保证了结点的数量，从而保证了珂朵莉树的复杂度。
当然，这是在数据完全随机生成的情况下，不然凉心出题人搞得一个assign操作都没有，复杂度立刻爆炸。
这也是珂朵莉树经常被卡的原因之一......珂怜的珂朵莉
解题思路：
- 对于操作 ，就是珂朵莉树基本操作：
assign区间推平。 - 对于操作 ：
- 先从 到 挨个枚举，一看到不同的就
return false; - 然后再判断第 个矿石和第 个矿石是否相同即可。
- 记得特判 或者 的情况。
- 先从 到 挨个枚举，一看到不同的就
最后，一起来做个英语完形填空吧：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
int f(char _________){
return _________-'A';
}
struct ____{
int l,r;
mutable int ________________;
____(int L,int R,int V):l(L),r(R),________________(V){}
____(int L):l(L){}
bool operator<(const ____ &o)const{
return l<o.l;
}
};
set<____>s;
int _______________,_____________________;
#define ______ set<____>::iterator
______ ___(int pos){
______ it=s.lower_bound(____(pos));
if(it!=s.end()&&it->l==pos){
return it;
}
it--;
int L=it->l,R=it->r,V=it->________________;
s.erase(it);
s.insert(____(L,pos-1,V));
return s.insert(____(pos,R,V)).first;
}
inline void __(int l,int r,int v){
______ _____=___(r+1),__=___(l);
s.erase(__,_____);
s.insert(____(l,r,v));
}
bool _______(int l,int r){
______ _____=___(r+1),__=___(l);
int k=__->________________;
for(______ it=__;it!=_____;it++){
if(it->________________!=k){
return false;
}
}
if(l==1||r==_______________)return true;
__--;
return __->________________!=_____->________________;
}
string str;
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>_______________;
cin>>str;
int ________=str.size();
for(int i=0;i<________;i++){
s.insert(____(i+1,i+1,f(str[i])));
}
cin>>_____________________;
while(_____________________--){
char _________;
int l,r;
char k;
cin>>_________;
if(_________=='A'){
cin>>l>>r>>k;
__(l,r,f(k));
}
else{
cin>>l>>r;
bool __________________________________________=_______(l,r);
if(__________________________________________)cout<<"Yes\n";
else cout<<"No\n";
}
}
return 0;
}
对个答案？（附注释）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
int f(char ch){
return ch-'A';
}
//由于是字符，怕出错，保险起见把字符全部换成了数字。
struct Node{
int l,r;
mutable int val;
//意思是区间 [l,r] 内的值全是 val。
//mutable的作用是让val能够被修改。
Node(int L,int R,int V):l(L),r(R),val(V){}
Node(int L):l(L){}
//构造函数，不多说
bool operator<(const Node &o)const{
return l<o.l;
}
//重载小于号运算符，这个会在 split 操作中用到。
};
set<Node>s;
int n,m;
#define Sit set<Node>::iterator
Sit split(int pos){
Sit it=s.lower_bound(Node(pos));
if(it!=s.end()&&it->l==pos){
return it;
}//如果无需分裂，直接返回
it--;
int L=it->l,R=it->r,V=it->val;
s.erase(it);//删除原节点
s.insert(Node(L,pos-1,V));
return s.insert(Node(pos,R,V)).first;
//分裂成两个子节点
}
inline void assign(int l,int r,int v){
Sit itr=split(r+1),itl=split(l);
s.erase(itl,itr);//删除原节点
s.insert(Node(l,r,v));//插入新节点
}
bool check(int l,int r){
Sit itr=split(r+1),itl=split(l);
int k=itl->val;//取出左端点
for(Sit it=itl;it!=itr;it++){
if(it->val!=k){//一旦发现区间中有一个元素不相同
return false;//就不满足要求
}
}
//运行到这里还没有return，就说明这个区间内的元素确实都相同。
if(l==1||r==n)return true;
itl--;
return itl->val!=itr->val;
}
string str;
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
cin>>str;
int len=str.size();
for(int i=0;i<len;i++){
s.insert(Node(i+1,i+1,f(str[i])));
//初始情况下，区间 [i+1,i+1] 内当然都是相同的元素。
}
cin>>m;
while(m--){
char ch;
int l,r;
char k;
cin>>ch;
if(ch=='A'){
cin>>l>>r>>k;
assign(l,r,f(k));
}
else{
cin>>l>>r;
bool p=check(l,r);
if(p)cout<<"Yes\n";
else cout<<"No\n";
}
}
return 0;
}
