莫队学习

大致思路：
1.分块

2.对提问排序

3.暴力处理

# 莫队模板
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e6+10;
int a[N],belong[N],bnum,cnt[N];
int n,q,len,ans[M];
struct node
{
int l,r,id;
}e[M];
bool cmp(node a,node b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r: a.r>b.r);
}
void solve()
{
scanf("%d",&n);
len=sqrt(n);
bnum=ceil((double)n/len);

for(int i=1;i<=bnum;i++)
for(int j=(i-1)*len+1;j<=i*len;j++)
belong[j]=i;

for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&q);

for(int i=1;i<=q;i++)
{
int id=i;
int l,r;
scanf("%d%d",&l,&r);
e[i]={l,r,id};
}
sort(e+1,e+q+1,cmp);
int l=1,r=0;
int now=0;
for(int i=1;i<=q;i++)
{
int ql=e[i].l,qr=e[i].r;
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--]];
ans[e[i].id]=now;
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
}
int main()
{
solve();
return 0;
}

```
# 带修莫队

带修莫队学习

1.定义时间戳，多了往回跳，少了往后跳

2.排序最后一个关键字改为时间戳

3.注意常数大小，尽量使用快读

4.块长改为n的2/3次方

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10,M=2e5+10;
int a[M],cnt[N],ans[M];
int len,bnum,belong[M];
int n,q,cnt1,cnt2;
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;
}
inline void write(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
struct node
{
int l,r,time,id;
}e[M];
struct query
{
int pos,col;
}ch[M];
int cmp(node a, node b)
{
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r]) ? belong[a.r] < belong[b.r] : a.time < b.time);
}
void init()
{
n=read(),q=read();

for(int i=1;i<=n;i++) a[i]=read();

for(int i=1;i<=q;i++)
{
char op[100];
int l,r;
scanf("%s",op);
if(op[0]=='Q')
{
e[++cnt1].l=read();
e[cnt1].r=read();
e[cnt1].time=cnt2;
e[cnt1].id=cnt1;
}
else
{
ch[++cnt2].pos=read();
ch[cnt2].col=read();
}
}

len=pow(n,2.0/3.0);

bnum=ceil((double)n/len);

for(int i=1;i<=n;i++) belong[i]=(i-1)/len+1;

sort(e+1,e+cnt1+1,cmp);
}
void solve()
{
int time=0,now=0,l=1,r=0;
for(int i=1;i<=cnt1;i++)
{
int ql=e[i].l,qr=e[i].r,qt=e[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(time<qt)
{
++time;
if(ql<=ch[time].pos&&ch[time].pos<=qr)
now-=!--cnt[a[ch[time].pos]]-!cnt[ch[time].col]++;
swap(a[ch[time].pos],ch[time].col);
}

while(time>qt)
{
if(ql<=ch[time].pos&&ch[time].pos<=qr)
now-=!--cnt[a[ch[time].pos]]-!cnt[ch[time].col]++;
swap(a[ch[time].pos],ch[time].col);
--time;
}
ans[e[i].id]=now;
}

for(int i=1;i<=cnt1;i++) printf("%d\n",ans[i]);
}
int main()
{
init();
solve();
return 0;
}
```
# 回滚莫队

应用的原因：

普通莫队带有删除操作，但有时（如区间最值）由于有删除，并不能很好维护
于是便产生此思想

1.按左端点所处块排序，若相同，则右端点递增排序

2.分块处理，若左右端点所处块相同，则暴力处理，此外，则左端点暴力处理，右端点依次递增，这样右端点维护信息为一段连续信息

3.及时备份保存信息（now值），及时清空数组（cnt）

4.每处理一个询问，左端点暴力回退，右端点继续递增，若端点处在同一块，处理外后及时continue

5.左端点初始位置为当前处理块最右段+1，右端点为最右端，类比普通莫队

```cpp
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+10,M=N*2;
int a[N],b[N],lb[N],rb[N],ty[N];
int n,q,len,belong[M],bnum;
int cnt1[N],cnt2[N];
LL ans[N];
struct node
{
int l,r,id;
}e[N];
inline int read()
{
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
bool cmp(node a,node b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]: a.r<b.r;
}
void init()
{
n=read(),q=read();
for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];

len=sqrt(n);

bnum=ceil((double)n/len);

for(int i=1;i<=bnum;i++)
{
lb[i]=(i-1)*len+1;
rb[i]=i*len;
for(int j=lb[i];j<=rb[i];j++) belong[j]=i;
}

rb[bnum]=n;//最后一块可能长度不够，手动

for(int i=1;i<=q;i++)
{
int l,r;
l=read(),r=read();
e[i]={l,r,i};
}
sort(b+1,b+n+1);
sort(e+1,e+q+1,cmp);
int tot=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++) ty[i]=lower_bound(b+1,b+tot+1,a[i])-b;
}
void solve()
{
int i=1;
for(int k=0;k<=bnum;k++)
{
int l=rb[k]+1,r=rb[k];
LL now=0;
memset(cnt1,0,sizeof(cnt1));
for(;belong[e[i].l]==k;i++)
{
int ql=e[i].l,qr=e[i].r;
LL tmp;
if(belong[ql]==belong[qr])
{
tmp=0;
for(int j=ql;j<=qr;j++) cnt2[ty[j]]=0;
for(int j=ql;j<=qr;j++)
{
++cnt2[ty[j]],tmp=max(tmp,1ll*cnt2[ty[j]]*a[j]);
}
ans[e[i].id]=tmp;
continue;
}
while(r<qr)
{
++cnt1[ty[++r]],now=max(now,1ll*cnt1[ty[r]]*a[r]);
}
tmp=now;
while(l>ql)
{
++cnt1[ty[--l]],now=max(now,1ll*cnt1[ty[l]]*a[l]);
}
ans[e[i].id]=now;
now=tmp;
while(l<rb[k]+1) --cnt1[ty[l++]];
}
}
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}
int main()
{
init();
solve();
return 0;
}