题目描述
可以采用只统计区间内第一次出现的颜色的策略,维护一个lst数组用于记录该颜色上一次出现的位置。对于区间[l,r],若lst[i]<l,则说明i位置的颜色第一次出现,需要统计上。这样问题就转化为了[l,r]内有多少lst<l,可以主席树维护,考虑到还有修改操作,可以在外面套一层树状数组,这样每次修改只用修改log(n)棵树。同时还要快速修改lst数组,可以考虑对每个颜色开一个set,可以通过查询前驱后继来快速维护lst。这样总时间复杂度就是O(nlog^2(n))的。
时间复杂度
O(nlog^2(n))
C++ 代码
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<iostream>
#include<vector>
#include<unordered_map>
#include<set>
using namespace std;
#define ls(u) tr[u].son[0]
#define rs(u) tr[u].son[1]
const int N=133331+10,M=1e6+10;
const int INF=0x3f3f3f3f;
int n,m,lst[N];
unordered_map<int,set<int>> col;
inline int pre(int id,int val){
if(col[id].empty())return 0;
auto it=col[id].lower_bound(val);
if(it==col[id].begin())return 0;
it--;
return *it;
}
inline int suc(int id,int val){
auto it=col[id].upper_bound(val);
if(it==col[id].end())return INF;
return *it;
}
int rt[N],idx,v[N];
struct Node{
int son[2];
int cnt;
}tr[10*M];
inline void insert(int& u,int l,int r,int x){
if(!u)u=++idx;
tr[u].cnt++;
if(l==r)return ;
int mid=l+r>>1;
if(x<=mid)insert(ls(u),l,mid,x);
else insert(rs(u),mid+1,r,x);
}
inline void del(int& u,int l,int r,int x){
tr[u].cnt--;
if(l==r)return ;
int mid=l+r>>1;
if(x<=mid)del(ls(u),l,mid,x);
else del(rs(u),mid+1,r,x);
}
inline void insert(int x){
for(int i=x;i<=n;i+=i&-i)
insert(rt[i],0,n,lst[x]);
}
inline void update(int x,int c){
int last_l=pre(v[x],x),last_r=suc(v[x],x);
int now_l=pre(c,x),now_r=suc(c,x);
for(int i=x;i<=n;i+=i&-i)del(rt[i],0,n,last_l);
if(last_r!=INF){
lst[last_r]=last_l;
for(int i=last_r;i<=n;i+=i&-i)del(rt[i],0,n,x),insert(rt[i],0,n,last_l);
}
if(now_r!=INF){
lst[now_r]=x;
for(int i=now_r;i<=n;i+=i&-i)del(rt[i],0,n,now_l),insert(rt[i],0,n,x);
}
for(int i=x;i<=n;i+=i&-i)insert(rt[i],0,n,now_l);
col[v[x]].erase(x),col[c].insert(x);
lst[x]=now_l,v[x]=c;
}
inline int query(vector<int>& q1,vector<int>& q2,int l,int r,int ql,int qr){
if(ql>qr)return 0;
if(l>=ql&&r<=qr){
int res=0;
for(auto u:q1)res+=tr[u].cnt;
for(auto u:q2)res-=tr[u].cnt;
return res;
}
else {
int mid=l+r>>1,res=0;
if(qr<=mid){
for(auto& u:q1)u=ls(u);
for(auto& u:q2)u=ls(u);
res=query(q1,q2,l,mid,ql,qr);
}
else if(ql>mid){
for(auto& u:q1)u=rs(u);
for(auto& u:q2)u=rs(u);
res=query(q1,q2,mid+1,r,ql,qr);
}
else {
vector<int> nq1=q1,nq2=q2;
for(auto& u:q1)u=ls(u);
for(auto& u:q2)u=ls(u);
for(auto& u:nq1)u=rs(u);
for(auto& u:nq2)u=rs(u);
res=query(q1,q2,l,mid,ql,qr)+query(nq1,nq2,mid+1,r,ql,qr);
}
return res;
}
}
inline int query(int l,int r){
vector<int> q1,q2;
for(int i=r;i;i-=i&-i)q1.push_back(rt[i]);
for(int i=l-1;i;i-=i&-i)q2.push_back(rt[i]);
return query(q1,q2,0,n,0,l-1);
}
inline void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
lst[i]=pre(x,i),v[i]=x;
col[x].insert(i);
insert(i);
}
char opt[2];
for(int i=0;i<m;i++){
cin>>opt;
if(opt[0]=='Q'){
int l,r;
cin>>l>>r;
cout<<query(l,r)<<'\n';
}
else {
int x,c;
cin>>x>>c;
update(x,c);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int testcase=1;
while(testcase--)solve();
}
喔豁,酸爽。