Solution
这是一道很经典的题目吖
莫队的话,在洛谷上吸吸氧就能过了
其实这题是由很多做法的吧
我们一种颜色显然只有在它第一次出现的时候有贡献
或者说,我们让它在最后一次出现的时候有贡献
然后把按照r从小到大排序,用树状数组维护每个点最后一次出现的位置(权值为1,之前的为0)
然后区间求和就行啦
主席树也能做?
这下我们让每个数第一次出现有贡献~
对于每个位置,记下该数上次出现的位置,如果小于
l
,那么它是第一次出现的维护一个last的权值线段树,然后每次查询区间中小于
l
的数
Code
#include#define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}#define MN 500005int col[MN],l,r,pos[MN];struct ques{ int l,r,id; bool operator<(const ques&x) const{return pos[l]^pos[x.l]?pos[l] q[i].r;--R) ans-=(num[col[R]]==1),num[col[R]]--; for(;L>q[i].l;--L) ans+=(!num[col[L-1]]),num[col[L-1]]++; for(;L
Blog来自PaperCloud,未经允许,请勿转载,TKS!