莫队学习笔记
ETHANK
·
·
个人记录
P1972 [SDOI2009]HH的项链
题意
给一个有n个正整数的序列，m个询问，问区间内有多少个不同的数。
【数据范围】
1\le n,m,a_i \le 10^6, 1\le l \le r\le n
思路
由于[l,r]的答案可以O(1)扩展到[l,r+1],[l+1,r],[l-1,r],[l,r-1]的答案，我们考虑莫队算法。
时间复杂度
我们设分块长度为B，那么对于任意多个在同一块内的询问，由于R已经在块内排好序，右指针在块内最多移动n次，一共\dfrac{n}{B}个块，移动的总次数就是\dfrac{n^2}{B}。
左指针每次最多移动B，总次数就是mB。于是总复杂度为O(\dfrac{n^2}{B}+mB)。
由均值不等式可得：
\frac{n^2}{B}+mB\ge2\sqrt{\frac{n^2}{B}\cdot mB}=2n\sqrt{m}
不等式取等号当且仅当\dfrac{n^2}{B}=mB，即B=\dfrac{n}{\sqrt{m}}。
此时时间复杂度为\boxed{O(n\sqrt{m})}。
[ [Tutorial] Square root decomposition and applications](https://codeforces.com/blog/entry/83248)
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct query{
int l,r,id;
}q[N];
int n,m,len,a[N],id[N],now,ans[N];
int pre[N],nxt[N],tmp[N];
inline bool cmp(query a, query b) {
return (id[a.l]^id[b.l]) ? id[a.l] < id[b.l] : ((id[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
int main(){
n=read();
len=sqrt(n);
for(int i=1;i<=n;i++){
a[i]=read();
id[i]=(i-1)/len+1;
}
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=n;i++){
pre[i]=tmp[a[i]];
tmp[a[i]]=i;
}
memset(tmp,0x3f,sizeof(tmp));
for(int i=n;i>=1;i--){
nxt[i]=tmp[a[i]];
tmp[a[i]]=i;
}
m=read();
for(int i=1;i<=m;i++){
q[i].l=read(),q[i].r=read(),q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
int ql=q[i].l,qr=q[i].r;
while(l<ql){
now-=(nxt[l++]>r);
}
while(l>ql){
now+=(nxt[--l]>r);
}
while(r>qr){
now-=(pre[r--]<l);
}
while(r<qr){
now+=(pre[++r]<l);
}
ans[q[i].id]=now;
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
```
# P1903 [国家集训队]数颜色 / 维护队列
## 题意
上道题目带修改。
## 思路
带修莫队模板题。我们考虑对每条询问加一维时间维，即从$(l,r)$变成$(l,r,t)$。不难发现，$(l,r,t)$到$(l,r,t+1)$和$(l,r,t-1)$都可以通过直接单点修改来$O(1)$转移。通过上一题普通莫队类似的套路，就可以写出这道题目。
### 时间复杂度
记$q$为询问数，$T$为修改数。对前两维分块后分别以第一、第二关键字排序，时间维为第三关键字。设块长为$B$，那么会产生$(\dfrac{n}{B})^2$块。对于每一块，时间在排序后最多移动$T$次，复杂度为$O(\dfrac{n^2T}{B^2})$。每个询问贡献$O(B)$的时间复杂度，总复杂度为$O(qB)$。于是最后的复杂度为$O(\dfrac{n^2T}{B^2}+qB)$。
由均值不等式得：
$$\frac{n^2T}{B^2}+qB=\frac{n^2T}{B^2}+\frac{qB}{2}+\frac{qB}{2}\ge3\sqrt[3]\frac{Tn^2q^2}{4}$$
不等式取等号当且仅当$\dfrac{n^2T}{B^2}=\dfrac{qB}{2}$，即$B=\sqrt[3]{\frac{2n^2T}{q}}$。
此时时间复杂度为$\boxed{O(\sqrt[3]{Tn^2q^2})}$。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,C=1e6+5;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch))ch=getchar();
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct query{
int l,r,Tim,id;
}q[N];
struct change{
int pos,Old,New;
}c[N];
int n,m,a[N],cnt[C],blo[N],ans[N];
int t,Time,now[N],T,l=1,r,Ans;
inline bool cmp(query a, query b) {
return blo[a.l]==blo[b.l]?(blo[a.r]==blo[b.r]?a.Tim<b.Tim:a.r<b.r):a.l<b.l;
}
inline void rem(int col,int opt){
cnt[col]+=opt;
if(opt>0) Ans+=(cnt[col]==1);
else Ans-=(cnt[col]==0);
}
inline void doit(int pos,int col){
if(l<=pos&&pos<=r){
rem(col,1);rem(a[pos],-1);
}
a[pos]=col;
}
int main(){
n=read(),m=read();
int B=2*n/pow(n,1.0/3);
for(int i=1;i<=n;i++){
a[i]=read();
now[i]=a[i];
blo[i]=(i-1)/B+1;
}
for(int i=1;i<=m;i++){
char ch;int x,y;
cin>>ch;
x=read(),y=read();
if(ch=='Q'){
t++;
q[t]=(query){x,y,Time,t};
}else{
c[++Time]=(change){x,now[x],y};
now[x]=y;
}
}
sort(q+1,q+t+1,cmp);
for(int i=1;i<=t;i++){
while(T<q[i].Tim){
++T;
doit(c[T].pos,c[T].New);
}
while(T>q[i].Tim){
doit(c[T].pos,c[T].Old);
--T;
}
int ql=q[i].l,qr=q[i].r;
while(l<ql)rem(a[l++],-1);
while(l>ql)rem(a[--l],1);
while(r>qr)rem(a[r--],-1);
while(r<qr)rem(a[++r],1);
ans[q[i].id]=Ans;
}
for(int i=1;i<=t;i++)printf("%d\n",ans[i]);
return 0;
}
```
# AT1219 歴史の研究
## 题意
给一个长度为$n$的数组$A$和$m$个询问$(1\le n,m\le10^5)$，每次询问一个区间$[L,R]$内重要度最大的数字，要求**输出其重要度** 。一个数字$i$重要度的定义为$i$乘上$i$在区间内出现的次数。
## 思路
我们发现增加的操作很好实现，但是删除的操作不太好实现。因为删除后如果影响答案，我们很难确定新的答案是哪一个，所以这道题目不能直接普通莫队。
考虑一种只需要扩张区间，不需要做删除的莫队——**回滚莫队**。我们把左端点按所属块升序为第一关键字，右端点升序为第二关键字排序。
如何处理询问呢？
- 如果询问的左端点所在块$B$和上一个询问不同，我们把莫队的左指针初始化为$B$的右端点$+1$，把右指针初始化为$B$的右端点。
- 如果左右端点在同一块内，直接暴力扫描区间回答询问。
- 如果左右端点不在同一块内，我们先扩展莫队的左右指针来更新答案，再把左指针滚回到$B$的右端点$+1$。
### 时间复杂度
设左右端点在同一块内的询问数量为$C_1$，不在同一块内的询问数量为$C_2$。
对于左右端点在同一块内的询问，时间复杂度为$O(\sqrt n)$。总时间复杂度就是$O(C_1\sqrt n)$。
对于不在同一块内的询问，对于左端点在块$B$内的所有询问，右指针最多扩展$n$次，左端扩展和回滚的复杂度为$O(\sqrt n)$。总共有$\sqrt n$个块，所以总复杂度为$O(C_2\sqrt n+n\sqrt n)$。
综上，这个算法的总复杂度为$O(C_2\sqrt n+n\sqrt n)+O(C_1\sqrt n)=\boxed{O(n\sqrt n+m\sqrt n)}$。
## 代码
```cpp
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+5;
int n,m,q,B,x[N],t[N],blo[N],cnt[N],tmp[N];
ll ans[N];
struct query{
int l,r,id;
}Q[N];
inline bool cmp(query a,query b){
return (blo[a.l]==blo[b.l])?a.r<b.r:a.l<b.l;
}
inline void add(int v,ll& Ans){
++cnt[v];
Ans=max(Ans,1ll*cnt[v]*t[v]);
}
inline void del(int v){--cnt[v];}
int R[N];
int main(){
scanf("%d%d",&n,&q);
B=sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
blo[i]=(i-1+B)/B;
t[++m]=x[i];
}
for(int i=1;i<=blo[n];i++)R[i]=min(i*B,n);
for(int i=1;i<=q;i++){
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].id=i;
}
sort(Q+1,Q+q+1,cmp);
sort(t+1,t+m+1);
m=unique(t+1,t+m+1)-t-1;
for(int i=1;i<=n;i++){
x[i]=lower_bound(t+1,t+m+1,x[i])-t;
}
int l=1,r=0,last=0,nl;
ll Ans=0,nans;
for(int i=1;i<=q;i++){
if(blo[Q[i].l]==blo[Q[i].r]){//相同块内暴力
for(int j=Q[i].l;j<=Q[i].r;j++)++tmp[x[j]];
for(int j=Q[i].l;j<=Q[i].r;j++){
ans[Q[i].id]=max(ans[Q[i].id],1ll*tmp[x[j]]*t[x[j]]);
}
for(int j=Q[i].l;j<=Q[i].r;j++)--tmp[x[j]];
continue;
}
if(blo[Q[i].l]!=last){//初始化
while(r>R[blo[Q[i].l]])del(x[r--]);
while(l<R[blo[Q[i].l]]+1)del(x[l++]);
Ans=0;
last=blo[Q[i].l];
}
while(r<Q[i].r)add(x[++r],Ans);
nl=l,nans=Ans;
while(nl>Q[i].l)add(x[--nl],nans);
ans[Q[i].id]=nans;
//回滚
while(nl<l)del(x[nl++]);
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
```