看到这个题,你不由自主地想到了莫队算法,(不了解莫队算法的看这里:莫队(一):莫队初步基础与思想),但是你看到题目中还有修改操作,莫队GG了!怎么办?这时候就有了莫队的修改版:

带修莫队

前面说过,莫队算法是离线算法,不支持修改,强制在线需要另寻他法。的确,遇到强制在线的题目莫队基本上萎了,但是对于某些允许离线的带修改区间查询来说,莫队还是能用的。做法就是把莫队直接加上一维,变为带修莫队。

这里我们说的加上一维是什么意思呢?就是把修改操作进行编号,即加入了时间维度,编号即为“时间戳”。在进行查询的时候定义当前时间戳为\(t\),对于每一个查询操作,如果当前的时间戳相对太大了,就说明这里包含了一些要查询的时间点之后的修改,就要把多改的改回去,反之则向后修改。只有当当前区间和查询区间完全一致时,查询结束,此时的答案即是这个查询的结果。

//区间完全一致当且仅当\(l,r,t\)三个维度的值完全一样

这就是带修莫队了,是不是很简单,于是我当年就写了个这:
别着急复制,这个只有40分,题面说: 本题可能轻微卡常数
那我得用尽所有优化方式了,小伙伴们可以把这一份40分代码拿去自己优化一下试试。AC代码放在下面了

时限是2s肯定是被卡常了!
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring> 
#include<algorithm>
using namespace std;

const int MAXN=2*1e6+10;
inline int read(){
    char c=getchar();int x=0,f=1;
    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;
}
int N,M;
int a[MAXN],where[MAXN];
struct Query
{
    int x,y,pre,id;
}Q[MAXN];
int Qnum=0;
struct Change
{
    int pos,val;
}C[MAXN];
int Cnum=0;
int color[MAXN],ans=0,base,out[MAXN];

int comp(const Query &a,const Query &b){
    if(a.x!=b.x) return where[a.x]<where[b.x];
    if(a.y!=b.y) return where[a.y]<where[b.y];
    return a.pre<b.pre;
}

void Add(int val){    
    if(++color[val]==1) ans++;
} 

void Delet(int val){
    if(--color[val]==0) ans--;
}

void Work(int now,int i){
    if(C[now].pos>=Q[i].x&&C[now].pos<=Q[i].y){
        if(--color[a[C[now].pos]]==0) ans--;
        if(++color[C[now].val]==1) ans++; 
    }
    swap(C[now].val,a[C[now].pos]);
}
void MoQueue(){
    int l=1,r=0,now=0; 
    for(int i=1;i<=Qnum;i++)    {
        while(l<Q[i].x) Delet(a[l++]);
        while(l>Q[i].x) Add(a[--l]);
        while(r<Q[i].y) Add(a[++r]);
        while(r>Q[i].y) Delet(a[r--]);
        while(now<Q[i].pre) Work(++now,i);
        while(now>Q[i].pre) Work(now--,i);
        out[Q[i].id]=ans;
    }
    for(int i=1;i<=Qnum;i++)
    	printf("%d\n",out[i]);
}

int main(){
    N=read();M=read();
    base=sqrt(N);
    for(int i=1;i<=N;i++) a[i]=read(),where[i]=(i-1)/base+1;
    while(M--){
        char opt[5];
        scanf("%s",opt);
        if(opt[0]=='Q'){
            Q[++Qnum].x=read();
            Q[Qnum].y=read();
            Q[Qnum].pre=Cnum;
        	Q[Qnum].id=Qnum;        
        }
        else if(opt[0]=='R'){
            C[++Cnum].pos=read();
            C[Cnum].val=read();
        }
    }
    sort(Q+1,Q+Qnum+1,comp);
    MoQueue();
    return 0;
}

上面一份代码为什么凉凉?不光是少了几步优化,还有一点:有大佬证明了这道题分块大小设置为\(n^{\frac{2}{3}}\)时优于大小为\(\sqrt n\)的情况,总复杂度为\(O(n^{\frac{5}{3}})\),优于大小为\(\sqrt n\)时最差\(O(n^2)\)的总复杂度。

所以就有了这样的代码!

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RE register
using namespace std;

const int N=1e6+10;
const int M=5e4+10;
int n,m,cntq,cntc;
int l=1,r,tim,now;
int be[M],a[M],ans[M];
int cnt[N];
struct query{
	int l,r,id,time;
}q[M];
struct node{
	int pos,col,last;
}c[M];

inline int Read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

inline void Print(int x){
	if(x>9)
		Print(x/10);
	putchar(x%10+'0');
}

inline bool CMP(query a,query b){
	if(be[a.l]^be[b.l])
		return be[a.l]<be[b.l];
	else
		if(be[a.r]^be[b.r])
			return be[a.r]<be[b.r];
		else return a.time<b.time;
}

//Ask和Change两部分看起来好像没必要拎出来 
inline void Ask(int l,int r){
	cntq++;
	q[cntq].l=l;
	q[cntq].r=r;
	q[cntq].time=cntc;
	q[cntq].id=cntq;
}

inline void Change(int p,int co){
	cntc++;
	c[cntc].pos=p;
	c[cntc].col=co;
}

int main(){
	n=Read();
	m=Read();
	int size=pow(n,2.0/3.0);
	int bnum=ceil((double)n/size);
	for(RE int i=1;i<=bnum;i++)
		for(RE int j=(i-1)*size+1;j<=i*size;j++)
			be[j]=i;
	for(int i=1;i<=n;i++)
		a[i]=Read();
	for(RE int i=1;i<=m;i++){
		char tmp;
		scanf("\n%c",&tmp);
		if(tmp=='Q'){
			RE int l=Read(),r=Read();
			Ask(l,r);
		}
		if(tmp=='R'){
			RE int p=Read(),co=Read();
			Change(p,co);
		}
	}
	sort(q+1,q+cntq+1,CMP);
	for(RE int i=1;i<=cntq;i++){
		int ql=q[i].l,qr=q[i].r,qt=q[i].time;
		while(l<ql) now-=!--cnt[a[l++]];
		while(l>ql) now+=!cnt[a[--l]]++;
		while(r<qr) now+=!cnt[a[++r]]++;
		while(r>qr) now-=!--cnt[a[r--]];
		//以下就是带修莫队的时间点左右横跳实现部分 
		while(tim<qt){
			tim++;
			if(ql<=c[tim].pos&&c[tim].pos<=qr)
				now-=!--cnt[a[c[tim].pos]]-!cnt[c[tim].col]++;
			swap(a[c[tim].pos],c[tim].col);//记录上一次修改的操作,一点小小的优化 
		}
		while(tim>qt){
			if(ql<=c[tim].pos&&c[tim].pos<=qr)
				now-=!--cnt[a[c[tim].pos]]-!cnt[c[tim].col]++;
			swap(a[c[tim].pos],c[tim].col);
			tim--;
		}
		ans[q[i].id]=now;
	}
	for(RE int i=1;i<=cntq;i++){
		Print(ans[i]);
		putchar('\n');
	}
	return 0;
}
改完之后是不是比原来快多了呢?

想必你已经学会了带修莫队,如果你还没有了解过其他莫队算法看这里:
莫队(三):莫队算法的拓展

0 0 votes
文章评分

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments