W同学的新画板 QDUOJ 线段树 区间颜色段数
题意
W同学在每天的刻苦学习完成功课之余，都会去找一些有趣的事情来放松自己；恰巧今天他收到了朋友送给他的一套画板，于是他立刻拆开了包装，拿出其中的画板和一些画笔，开心地画了起来；这时W同学注意到了闲暇的你正好待在一旁，于是他灵机一动，打算考验一下你的眼力，具体过程是这样的：
W同学收到的画板可看作一个长条状的木板，画板从左端到右端可划分为等长的连续的n段（自左至右依次编号为第1段,第2段,第3段,...,第n段，如下图所示），开始时每一段都有一个初始的颜色，之后W同学会进行一些操作，每次操作中他都会选一段区间[L,R]，然后用画笔把画板的第L段~第R段这一块连续的部分染为颜色C（被染色的某段先前已存在的颜色会被新颜色覆盖），而且每当进行一些染色操作后，W同学都有可能会让你立即答出他给你的某段区间[L,R]*有多少个颜色段，以此考察你的眼力，聪明的你敢不敢接受W同学的考验？
解题思路
使用线段树来进行处理这个题是大体的思路，原因在于题目要求一段区间内的颜色段数。要注意的是，这里是求取一段区间内的颜色的段数，不是有多少种颜色，比如 1 2 2 1 1 这个画板就有3段颜色，和自己以前做的求取区间内的颜色的种类数不同，这个题目还没想过，确实很新，参考的CH大佬的代码，下方链接。
代码实现（带注释）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5e5+7;
struct Node{
int l, r;
int sum, lazy;//sum记录这里有几段颜色段，lazy就是线段树常用的标记
int le, re; //这里是来记录这段区间的左右端点处的颜色种类
}node[maxn<<2];
int col[maxn]; //存储初始的颜色种类
void up(int rt)
{
node[rt].sum=node[rt<<1].sum+node[rt<<1|1].sum; //左右区间段数相加
if(node[rt<<1].re==node[rt<<1|1].le)//这里需要注意左右段的交界处，如果相等的话，总的段数是要进行减一的
node[rt].sum--; //这里想一想是不是
node[rt].le=node[rt<<1].le;
node[rt].re=node[rt<<1|1].re;
}
void build(int rt, int l, int r)
{
node[rt].l=l;
node[rt].r=r;
node[rt].lazy=-1;
if(l==r)
{
node[rt].sum=1;
node[rt].le=node[rt].re=col[l];
return ;
}
int mid=(l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
up(rt);
}
void down(int rt)
{
node[rt<<1].lazy=node[rt<<1|1].lazy=node[rt].lazy;
node[rt<<1].sum=node[rt<<1|1].sum=1; //左右的段数都归为1
node[rt<<1].le=node[rt<<1].re=node[rt].lazy;
node[rt<<1|1].le=node[rt<<1|1].re=node[rt].lazy;
node[rt].lazy=-1;
}
void update(int rt, int l, int r, int v)
{
if(l <= node[rt].l && node[rt].r <= r)
{
node[rt].lazy = node[rt].le = node[rt].re = v;
node[rt].sum=1;
return ;
}
int mid=(node[rt].l+node[rt].r)>>1;
if(node[rt].lazy!=-1) //这里有点不一样
down(rt);
if(l<=mid) update(rt<<1, l, r, v);
if(r>mid) update(rt<<1|1, l, r, v);
up(rt);
}
int query(int rt, int l, int r)
{
if(l <= node[rt].l && node[rt].r <=r)
{
return node[rt].sum;
}
if(node[rt].lazy!=-1)
down(rt);
int ans=0, mid=(node[rt].l + node[rt].r)>>1;
//这里因为交界处的特殊性，所以询问的方式不再是if(l<=mid)……然后if(r>mid)……
//这里需要判断三种情况
//1.全部在左区间 2.全部在右区间 3.左右区间都有
//这里1，2种情况比较好处理，就是第3种情况需要特殊一些
//第三种情况也是分开两半来计算的，但是需要判断中间交汇处是不是需要进行减一
if(r<=mid) return query(rt<<1, l, r); //第一种情况
else if(l>mid) return query(rt<<1|1, l, r); //第二种情况
else ans=query(rt<<1, l, r)+query(rt<<1|1, l, r); //第三种情况，也是比较特殊的一种情况
if(node[rt<<1].re == node[rt<<1|1].le)//这是关键，判断中间交汇处的颜色是不是相等，相等需要减一
ans--;
return ans;
}
int main()
{
int n, q, op, a, b, c;
cin>>n>>q;
for(int i=1; i<=n; i++)
cin>>col[i];
build(1, 1, n);
for(int i=1; i<=q; i++)
{
cin>>op;
if(op==1)
{
cin>>a>>b>>c;
update(1, a, b, c);
}
else if(op==2)
{
cin>>a>>b;
cout<<query(1, a, b)<<endl;
}
}
return 0;
}