先上一波题目 https://www.luogu.org/problem/P1972
这道题是询问区间内不同数的个数 明显不是正常的数据结构能够维护的
首先考虑 因为对于若干个询问的区间[l,r]，如果他们的r都相等的话，那么项链中出现的同一个数字，一定是只关心出现在最右边的那一个的
例如项链：1 3 4 5 1
那么，对于r=5的所有的询问来说，第一个位置上的1完全没有意义，因为r已经在第五个1的右边，对于任何查询的[L,5]区间来说，如果第一个1被算了，那么他完全可以用第五个1来替代。
那么我们将询问按右端点从小到大进行排序 利用数据结构维护前缀和 涉及的操作有单点修改和区间（前缀和）查询
这样每次我们更新一个点的时候 就可以将和他同颜色的上一个点的影响消除 即将上一个点所在的位置-1 然后将当前点位置+1
这样问题就解决了qwq
然而这道题对线段树并不友好（可能我写的太丑了加上数据又加强了）T了一个点
经过各种玄学修改 比如将结构体换成数组 加上inline 甚至在读入优化的基础上 加上输出优化 还是T掉了qwq
但毕竟也算是正解 就挂一下好了
涉及的操作就是单点修改和区间求和了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int M=1e6+;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,s[M];
int last[M],ans[M];
struct node{int l,r,sum;}e[*M];
struct qwq{int id,l,r;}q[M];
int cmp(qwq x,qwq y){return x.r<y.r;}
void up(int x){e[x].sum=e[x<<].sum+e[x<<^].sum;}
void build(int x,int l,int r){
e[x].l=l; e[x].r=r;
if(l==r) return ;
int mid=l+r>>;
build(x<<,l,mid);
build(x<<^,mid+,r);
}
void del(int x,int D){
if(e[x].l==e[x].r&&e[x].l==D){
e[x].sum=;
return ;
}
int mid=e[x].l+e[x].r>>;
if(D<=mid) del(x<<,D);
if(D>mid) del(x<<^,D);
up(x);
}
void add(int x,int D){
if(e[x].l==e[x].r&&e[x].l==D){
e[x].sum=;
return ;
}
int mid=e[x].l+e[x].r>>;
if(D<=mid) add(x<<,D);
if(D>mid) add(x<<^,D);
up(x);
}
int p_ans(int x,int L,int R){
if(L>R) return ;
if(L<=e[x].l&&e[x].r<=R) return e[x].sum;
int ans=,mid=e[x].l+e[x].r>>;
if(L<=mid) ans+=p_ans(x<<,L,R);
if(R>mid) ans+=p_ans(x<<^,L,R);
return ans;
}
int main(){
n=read(); build(,,n);
for(int i=;i<=n;i++) s[i]=read();
m=read();
for(int i=;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+,q++m,cmp);
// for(int i=1;i<=m;i++) printf("qwq%d %d\n",q[i].l,q[i].r);
int x=;
for(int i=;i<=m;i++){
while(x<=q[i].r){
if(last[s[x]]) del(,last[s[x]]);
add(,x); last[s[x]]=x;
x++;
}
ans[q[i].id]=p_ans(,,q[i].r)-p_ans(,,q[i].l-);
// printf("qaq%d\n",x); }
for(int i=;i<=m;i++) printf("%d\n",ans[i]);
return ;
}
第二种做法自然就是树状数组了 树状数组的常数果然比线段树要小很多 跑得飞快
涉及的操作自然就是单点修改和求前缀和了
也算是复习了一波树状数组 这里挂一个大大的优秀讲解好了 https://www.cnblogs.com/xenny/p/9739600.html
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define lowbit(x) x&(-x)
using namespace std;
const int M=1e6+;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,s[M],sum[M*];
int last[M],ans[M];
struct qwq{int id,l,r;}q[M];
int cmp(qwq x,qwq y){return x.r<y.r;}
void update(int x,int k){
while(x<=n){
sum[x]+=k;
x+=lowbit(x);
}
}
int p_ans(int x){
int ans=;
while(x){
ans+=sum[x];
x-=lowbit(x);
}
return ans;
}
int main(){
n=read();
for(int i=;i<=n;i++) s[i]=read();
m=read();
for(int i=;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+,q++m,cmp);
int x=;
for(int i=;i<=m;i++){
while(x<=q[i].r){
if(last[s[x]]) update(last[s[x]],-);
update(x,); last[s[x]]=x;
x++;
}
ans[q[i].id]=p_ans(q[i].r)-p_ans(q[i].l-);
}
for(int i=;i<=m;i++) printf("%d\n",ans[i]);
return ;
}