[洛谷 4979]矿洞：坍塌

题目链接

https://www.luogu.org/problem/P4979

题解

Part 1 线段树做法

用 \(1,2,3\) 分别代表原来的三种颜色，\(-1\) 代表该区间内有多种颜色。

修改操作就和普通的区间修改操作一样了。

而对于查询操作，我们先查查询区间内的颜色是否为单种颜色，再查区间两侧颜色是否不同。

代码这里略去。

Part 2 珂朵莉树做法

个人认为本题采用珂朵莉树来解决，理解和实现都相对于线段树容易不少。

当然，由于题目中没有明确提到数据随机，所以该做法事实上是可以卡的。（下面的代码在不开 -O2 优化的情况下并不能通过这道题）

查询操作暴力遍历所有区间，判断每个区间颜色是否相同即可。

一种看上去有用的优化是在查询的时候顺带合并颜色相同的区间，不过实测反而起到了负优化…（参见 R23465047，猜测可能是调用函数过多的原因）

#include <cstdio>
#include <set>
using namespace std;
struct node
{
 int l,r;
 mutable int val;
 node(int L=0,int R=-1,int Val=0)
 {
  l=L,r=R,val=Val;
 }
 bool operator<(const node&a)const
 {
  return l<a.l;
 }
};
set<node> se;
char s[500005];
int n,k;
set<node>::iterator split(int pos)
{
 auto it=se.lower_bound(node(pos));
 if(it!=se.end()&&it->l==pos)return it;
 it--;
 int l=it->l,r=it->r,val=it->val;
 se.erase(it);
 se.insert(node(l,pos-1,val));
 return se.insert(node(pos,r,val)).first;
}
void assign(int l,int r,int val)
{
 auto itr=split(r+1),itl=split(l);
 se.erase(itl,itr);
 se.insert(node(l,r,val));
}
bool query(int l,int r)
{
 auto itr=split(r+1),itl=split(l);
 for(auto it=itl;it!=itr;it++)
  if(it->val!=itl->val)return false;
 if(l!=1&&r!=n)
 {
  itl--;
  return itl->val!=itr->val;
 }
 else return true;
}
int main()
{
 scanf("%d",&n);
 scanf("%s",s+1);
 for(int i=1;i<=n;i++)
  se.insert(node(i,i,s[i]-'A'));
 scanf("%d",&k);
 while(k--)
 {
  scanf("%s",s);
  if(s[0]=='A')
  {
   int x,y;
   scanf("%d%d",&x,&y);
   scanf("%s",s);
   assign(x,y,s[0]-'A');
  }
  else
  {
   int x,y;
   scanf("%d%d",&x,&y);
   puts(query(x,y)?"Yes":"No");
  }
 }
 return 0;
}