P1903 [国家集训队] 数颜色 / 维护队列（单点修改莫队）

P1903 [国家集训队] 数颜色 / 维护队列 - 洛谷

与基础莫队的区别在于需要多维护一个变量---时间，用于标记修改操作的时间T，当每次询问区间[ L,R]时，我们就要把时间点调整到这个询问所处的时刻T。

利用分块算法将给定的 n 个数分成  块，而不是基础莫队算法的 sqrt(n) 个块；

分块排序时，将T作为最不优先的判定。即在初级莫队算法的基础上，排序时多考虑一个时间T。

每次区间查询时，将时间T调整到当前区间所处时间，再进行和初级莫队一样的查询操作。

Code:

const int N=1e6+5,mod=998244353;int pos[N],cnt[N],n,q,res,ans[N];
int a[N];struct node{int l,r,id,tt;
}tr[N];struct R{int p,v;
}R[N];void add(int x)
{if(!cnt[a[x]]) res++;cnt[a[x]]++;
}void sub(int x)
{if(cnt[a[x]]==1) res--;cnt[a[x]]--;
}void modify(int t,int i)
{int x=R[t].p;if(tr[i].l<=R[t].p&&tr[i].r>=R[t].p){int temp=R[t].v;int temp1=a[x];a[x]=temp;add(x);a[x]=temp1;sub(x);} swap(a[x],R[t].v);
}
void solve()
{cin>>n>>q;int sz=pow(n,2.0/3.0);for(int i=1;i<=n;i++){cin>>a[i];pos[i]=i/sz;}int id=0,tt=0;for(int i=1;i<=q;i++){char c;cin>>c;int l,r;cin>>l>>r;if(c=='Q') tr[++id]={l,r,id,tt};else R[++tt]={l,r};}sort(tr+1,tr+1+id,[](node x,node y){if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];if(pos[x.r]!=pos[y.r]) return pos[x.r]<pos[y.r];return x.tt<y.tt;});int l=1,r=0;tt=0;for(int i=1;i<=id;i++){while(tr[i].l<l) add(--l);while(tr[i].r>r) add(++r);while(tr[i].r<r) sub(r--);while(tr[i].l>l) sub(l++);while(tt<tr[i].tt) modify(++tt,i);while(tt>tr[i].tt) modify(tt--,i);ans[tr[i].id]=res;}for(int i=1;i<=id;i++) cout<<ans[i]<<endl;
}