带修莫队
版本更新内容：
- 在普通莫队基础上增加时间坐标，提高游戏难度；
- 排序时以时间坐标为第三关键字，奇偶排序玄学值上调 \(20\%\)；
- 代码常数加大，请玩家将分块大小调至 \(n^{\frac{2}{3}}\) 以抵消常数因子;
- 莫队函数主体内容增加：双指针操作完后，请将时间轴调至正确位置，并关注区间内时间扰动；
- 在时间跳跃时，若目标是未来，请先抵达未来再处理时间扰动，若目标是过去，请先处理时间扰动再回到过去。\(swap\) 是个神奇且玄妙的操作，请学会使用；详见代码中 \(upd()\) 函数的注释；
- 请分别储存时间节点与询问节点，提问者会感谢你；
- 请勿忘记 \(I/O\) 优化 , 祝您游戏愉快。
#include<bits/stdc++.h>
#define re register
#define rep(i,a,n) for(re int i=a;i<=n;++i)
using namespace std;
inline int read() {
re int x=0,f=1;re char c=getchar();//getchar()yyds!
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
const int maxn = 1e6;
struct area{int l,r,id,tm;}dui[maxn];
int a[maxn],ans,n,m,bel[maxn],ens[maxn];
int cntr,cntq;
int cnt[maxn];
bool cmp(area x,area y) {
if(bel[x.l]==bel[y.l]) {
if(bel[x.r]==bel[y.r]) return x.tm < y.tm;
return x.r < y.r;
}
return x.l < y.l;
}
bool cmp1(area x,area y)
{
if(bel[x.l] != bel[y.l]) return x.l<y.l;
if(bel[x.r] != bel[y.r]) if(bel[x.l]^1) return x.r < y.r;
return x.tm > y.tm;
}
struct Memory {int pos,val;}mem[maxn];
void upd(int l,int r,int tm)
{
re int pos = mem[tm].pos ,val = mem[tm].val;
if(pos >= l && pos <= r)
{
ans -= !(--cnt[a[pos]]);
ans += !(cnt[val]); cnt[val]++;
}
swap(a[pos],mem[tm].val);
//这里有个很巧妙的操作
//对于一个操作，下一次需要为的颜色是本次被改变的颜色
//比如，我把颜色3改为了7，那么再进行这次修改的时候就是把7改为3
//所以直接交换两种颜色就好
// 假如经过两次，则swap操作就奇妙地把原数组还原了
}
void solv() {
ans=0;
re int il=1,ir=0,nt=0;
rep(i,1,cntq)
{
int l=dui[i].l,r=dui[i].r,tm=dui[i].tm;
while(il < l){--cnt[a[il]];ans -= !(cnt[a[il]]);++il;}
while(il > l){il--; ans += !cnt[a[il]]; ++cnt[a[il]]; }
while(ir < r){++ir; ans += !cnt[a[ir]]; ++cnt[a[ir]];}
while(ir > r){--cnt[a[ir]]; ans -= !cnt[a[ir]]; --ir;}
while(nt > tm){upd(il,ir,nt);--nt;} // 先更新再回溯
while(nt < tm){++nt;upd(il,ir,nt);} // 先回溯再更新，原因是upd里的 swap
ens[dui[i].id] = ans;
}
}
int main()
{
n=read(),m=read();
int blk = (int)pow(n,(double)2*1.0/(double)3); // 2/3次方块长优化
//int blk = (int)sqrt(n); // 根号已落后于版本
rep(i,1,n) a[i] = read(),bel[i]=(i-1)/blk;
char ch;
int l,r,p,co;
rep(i,1,m) {
scanf("%c",&ch);
if(ch == 'R')
{
++cntr; p=read(),co=read();
mem[cntr].pos = p, mem[cntr].val = co;
}
else
{
dui[++cntq].l=read(),dui[cntq].r=read();
dui[cntq].id = cntq;
dui[cntq].tm = cntr;
}
}
sort(dui+1,dui+cntq+1,cmp);
solv();
rep(i,1,cntq) printf("%d\n",ens[i]);
return 0;
}
作者：@魔幻世界魔幻人生
本文为作者原创，转载请注明出处：https://www.cnblogs.com/subtlemaple/p/16618356.html