题意：询问区间有多少个连续的段，而且这段的颜色在[L,R]才算贡献，每段贡献是1。 有单点修改和区间查询。
思路：46min交了第一发树套树，T了。 稍加优化多交几次就过了。
不难想到，除了L这个点，其他的点都可以只统计这一段的段首。把位置看成x，颜色看成y，就成了二维平面就矩形内点的个数，这就是裸的树套树或者CDQ了。
树套树：34**ms。
/*
2019南昌网络赛I。
询问区间有多少个连续的段，而且这段的颜色在[L,R]才算贡献，每段贡献是1。 有单点修改和区间查询。
也可以CDQ来做，常数小很多。
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
struct in{
int l,r,sum;
}s[maxn*];
int a[maxn],rt[maxn],N,M,cnt;
void add(int &Now,int L,int R,int pos,int v)
{
if(!Now) Now=++cnt; s[Now].sum+=v;
if(L==R) return ;int Mid=(L+R)>>;
if(pos<=Mid) add(s[Now].l,L,Mid,pos,v);
else add(s[Now].r,Mid+,R,pos,v);
}
void Add(int x,int pos,int v)
{
while(x<=N){
add(rt[x],,N,pos,v);
x+=(-x)&x;
}
}
int query(int Now,int L,int R,int l,int r)
{
if(!Now||s[Now].sum==) return ;
if(l<=L&&r>=R) return s[Now].sum;
int Mid=(L+R)>>,res=;
if(l<=Mid) res+=query(s[Now].l,L,Mid,l,r);
if(r>Mid) res+=query(s[Now].r,Mid+,R,l,r);
return res;
}
int Query(int x,int L,int R)
{
if(L>R||x==) return ;
int res=; while(x){
res+=query(rt[x],,N,L,R);
x-=(-x)&x;
} return res;
}
void read(int &x){
x=; char c=getchar();
while(c>''||c<'') c=getchar();
while(c>=''&&c<='') x=x*+c-'',c=getchar();
}
int main()
{
scanf("%d%d",&N,&M);
rep(i,,N) {
read(a[i]);
if(a[i]!=a[i-]) Add(i,a[i],);
}
int opt,pos,L,R,x,y;
while(M--){
read(opt);
if(opt==){
read(L); read(R); read(x); read(y);
int ans=Query(R,x,y)-Query(L-,x,y);
if(a[L]==a[L-]&&a[L]<=y&&a[L]>=x) ans++;
printf("%d\n",ans);
}
else {
read(pos); read(x);
if(a[pos]==x) continue;
if(a[pos]!=a[pos-]) Add(pos,a[pos],-);
if(pos+!=N&&a[pos+]!=a[pos]) Add(pos+,a[pos+],-);
a[pos]=x;
if(a[pos]!=a[pos-]) Add(pos,a[pos],);
if(pos+!=N&&a[pos+]!=a[pos]) Add(pos+,a[pos+],);
}
}
return ;
}
CDQ：700ms。
/*
2019南昌网络赛I：
*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
struct in{
int opt,x,y,z,id;
//opt=0是修改，否则是查询。
//opt=1表示时间为x，查询[1,x],[y,z]的矩形面积
//时间为第一维，x为第二维，y到z为第三维
}s[maxn<<],q[maxn<<];
int c[maxn],ans[maxn],tot,Q;
int sum[maxn],N,M;
void add(int x,int val)
{
for(int i=x;i<=N;i+=(-i)&i) sum[i]+=val;
}
int query(int x){
int res=;
for(int i=x;i;i-=(-i)&i) res+=sum[i];
return res;
}
void CDQ(int y,int z,int L,int R) //x在[y,z]区间,操作在[L,R]。 不停地对x进行分治，并把[L,R]进行相应的划分
{
if(L>=R) return ;
if(y>z) return ;
if(y==z){ //特殊的一行
rep(i,L,R) {
if(!s[i].opt) add(s[i].y,s[i].z);
if(s[i].opt!=) ans[s[i].id]+=s[i].opt*(query(s[i].z)-query(s[i].y-));
}
rep(i,L,R) if(!s[i].opt) add(s[i].y,-s[i].z);
return ;
}
int Mid=(y+z)>>,F=L,C=L;
rep(i,L,R) {
if(s[i].x<=Mid) C++;
if(!s[i].opt&&s[i].x<=Mid) add(s[i].y,s[i].z);
if(s[i].opt!=&&s[i].x>Mid) ans[s[i].id]+=s[i].opt*(query(s[i].z)-query(s[i].y-));
}
rep(i,L,R) if(!s[i].opt&&s[i].x<=Mid) add(s[i].y,-s[i].z);
rep(i,L,R) if(s[i].x<=Mid) q[F++]=s[i]; else q[C++]=s[i];
rep(i,L,R) s[i]=q[i];
CDQ(y,Mid,L,F-); CDQ(Mid+,z,F,R);
}
int main()
{
scanf("%d%d",&N,&M);
rep(i,,N) {
scanf("%d",&c[i]);
if(c[i]!=c[i-]) s[++tot]=in{,i,c[i],,};
}
int opt,L,R,x,y;
rep(i,,M){
scanf("%d",&opt);
if(opt&){
scanf("%d%d",&x,&y);
if(y==c[x]) continue;
if(c[x]!=c[x-]) s[++tot]=in{,x,c[x],-,};
if(x<N&&c[x]!=c[x+]) s[++tot]=in{,x+,c[x+],-,};
c[x]=y;
if(c[x]!=c[x-]) s[++tot]=in{,x,c[x],,};
if(x<N&&c[x]!=c[x+]) s[++tot]=in{,x+,c[x+],,};
}
else {
scanf("%d%d%d%d",&L,&R,&x,&y); Q++;
s[++tot]=in{,R,x,y,Q};
s[++tot]=in{-,L,x,y,Q};
if(c[L]>=x&&c[L]<=y) ans[Q]++;
}
}
CDQ(,N,,tot);
rep(i,,Q) printf("%d\n",ans[i]);
return ;
}