##借鉴的博客
莫队
const int maxn = 1000000+100;
int n,m,k,len,ans;
int num[maxn],cnt[maxn],a[maxn];
struct query{
int l,r,in,id;
I bool operator <(const query &a)const
{return (in^a.in)?in<a.in:((in&1)?r<a.r:r>a.r);}
}q[maxn];
signed main(){
read(n);
int QAQ=pow(n,0.6);
len=QAQ*QAQ*QAQ;
for(R int *S=a,*T=a+n;S!=T;)read(*++S);
read(m);
int x,y;
FOR(i,1,m)
read(q[i].l),read(q[i].r),
q[i].in=(q[i].l-1)/len+1,
q[i].id=i;
sort(q+1,q+1+m);
int l=1,r=0;
FOR(i,1,m){
int x=q[i].l,y=q[i].r;
while(l<x)ans-=(!--cnt[a[l++]]);
while(l>x)ans+=(!cnt[a[--l]]++);
while(r<y)ans+=(!cnt[a[++r]]++);
while(r>y)ans-=(!--cnt[a[r--]]);
num[q[i].id]=ans;
}
for(R int *S=num,*T=num+m;S!=T;)write(*++S),pc('\n');
flush();
return 0;
}
待修莫队：
const int maxn=2*1e6+10;
int n,m,a[maxn],in[maxn];
struct Query{
int x,y,pre,id;
}Q[maxn];
struct Change{
int pos,val;
}C[maxn];
int Qnum=0,Cnum=0;
int cnt[maxn],ans=0,base,out[maxn];
I int cmp(const Query &a,const Query &b){
if(a.x!=b.x)return in[a.x]<in[b.x];
if(a.y!=b.x)return in[a.y]<in[b.y];
return a.pre<b.pre;
}
I void work(int now,int i){
if(C[now].pos>=Q[i].x&&C[now].pos<=Q[i].y){
if(--cnt[a[C[now].pos]]==0)ans--;
if(++cnt[C[now].val]==1)ans++;
}
swap(C[now].val,a[C[now].pos]);
}
I void MoQueue(){
int l=1,r=0,now=0;
FOR(i,1,Qnum){
while(l<Q[i].x)ans-=!--cnt[a[l++]];
while(l>Q[i].x)ans+=!cnt[a[--l]]++;
while(r<Q[i].y)ans+=!cnt[a[++r]]++;
while(r>Q[i].y)ans-=!--cnt[a[r--]];
while(now<Q[i].pre)work(++now,i);
while(now>Q[i].pre)work(now--,i);
out[Q[i].id]=ans;
}
FOR(i,1,Qnum)
write(out[i]),pc('\n');
}
signed main(){
read(n),read(m);
base=pow(n,(double)2/(double)3);
FOR(i,1,n)read(a[i]),in[i]=(i-1)/base+1;
while(m--){
if(Read()){
read(Q[++Qnum].x),
read(Q[Qnum].y),
Q[Qnum].pre=Cnum,
Q[Qnum].id=Qnum;
}else{
read(C[++Cnum].pos);
read(C[Cnum].val);
}
}
sort(Q+1,Q+Qnum+1,cmp);
MoQueue();
flush();
return 0;
}
树上莫队：
//a,cnt,first,last,ans,belong,inp,vis,ncnt,l,r,now,size,bnum莫队相关
int a[maxn],cnt[maxn],first[maxn],last[maxn];
int ans[maxn],belong[maxn],inp[maxn],vis[maxn];
int ord[maxn],val[maxn],head[maxn],dep[maxn];
int fa[maxn][21],ecnt,ncnt,l=1,r,now,len,bnum,n,m;
// ord Euler-pos first Euler->begin last Euler->end;
struct edge{
int v,n;
I edge(const int &vv=0,const int & nn=0):v(vv),n(nn){}
}e[maxn];
void add(int u,int v){
e[++ecnt]=edge(v,head[u]),head[u]=ecnt;
e[++ecnt]=edge(u,head[v]),head[v]=ecnt;
}
void dfs(int u){
ord[++ncnt]=u;
first[u]=ncnt;
for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
if(v!=fa[u][0]){
dep[v]=dep[u]+1;
fa[v][0]=u;
for(int i=1;(1<<i)<=dep[v];++i)fa[v][i]=fa[fa[v][i-1]][i-1];
dfs(v);
}
ord[++ncnt]=u;
last[u]=ncnt;
}
int get_lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i+1;--i)
if(dep[u]-(1<<i)>=dep[v])u=fa[u][i];
if(u==v)return u;
for(int i=20;i+1;--i)
if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
struct query{
int l,r,lca,id;
}q[maxn];
int cmp(const query &a,const query &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);
}
I void work(int pos){
vis[pos]?
now-=!--cnt[val[pos]]:
now+=!cnt[val[pos]]++;
vis[pos]^=1;
}
signed main(){
read(n),read(m);
FOR(i,1,n)read(val[i]),inp[i]=val[i];
sort(inp+1,inp+1+n);
int tot=unique(inp+1,inp+1+n)-inp-1;
FOR(i,1,n)
val[i]=lower_bound(inp+1,inp+tot+1,val[i])-inp;
int x,y;
FOR(i,1,n-1)read(x),read(y),add(x,y);
dep[1]=1;dfs(1);
len=sqrt(ncnt),bnum=ceil((double)ncnt/len);
FOR(i,1,bnum)
for(int j=len*(i-1)+1;j<=i*len;++j)
belong[j]=i;
FOR(i,1,m){
int x,y,lca;
read(x),read(y),lca=get_lca(x,y);
if(first[x]>first[y])swap(x,y);
if(x==lca){
q[i].l=first[x];
q[i].r=first[y];
}else{
q[i].l=last[x];
q[i].r=first[y];
q[i].lca=lca;
}
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
FOR(i,1,m){
int ql=q[i].l,qr=q[i].r,lca=q[i].lca;
while(l<ql)work(ord[l++]);
while(l>ql)work(ord[--l]);
while(r<qr)work(ord[++r]);
while(r>qr)work(ord[r--]);
if(lca)work(lca);
ans[q[i].id]=now;
if(lca)work(lca);
}
FOR(i,1,m)write(ans[i]),pc('\n');
flush();
return 0;
}
回滚莫队：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define maxn 100100
#define maxb 5050
#define ll long long
int aa[maxn], typ[maxn], cnt[maxn], cnt2[maxn], belong[maxn], lb[maxn], rb[maxn], inp[maxn];
ll ans[maxn];
struct query {
int l, r, id;
} q[maxn];
int n, m, size, bnum;
#define isdigit(x) ((x) >= '0' && (x) <= '9')
inline int read() {
int res = 0;
char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) res = (res << 1) + (res << 3) + (c ^ 48), c = getchar();
return res;
}
int cmp(query a, query b) {
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : a.r < b.r;
}
int main() {
n = read(), m = read();
size = sqrt(n);
bnum = ceil((double) n / size);
for(int i = 1; i <= bnum; ++i) {
lb[i] = size * (i - 1) + 1;
rb[i] = size * i;
for(int j = lb[i]; j <= rb[i]; ++j) belong[j] = i;
}
rb[bnum] = n;
for(int i = 1; i <= n; ++i) inp[i] = aa[i] = read();
sort(inp + 1, inp + n + 1);
int tot = unique(inp + 1, inp + n + 1) - inp - 1;
for(int i = 1; i <= n; ++i) typ[i] = lower_bound(inp + 1, inp + tot + 1, aa[i]) - inp;
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 i = 1;
for(int k = 0; k <= bnum; ++k) {
int l = rb[k] + 1, r = rb[k];
ll now = 0;
memset(cnt, 0, sizeof(cnt));
for( ; belong[q[i].l] == k; ++i) {
int ql = q[i].l, qr = q[i].r;
ll tmp;
if(belong[ql] == belong[qr]) {
tmp = 0;
for(int j = ql; j <= qr; ++j) cnt2[typ[j]] = 0;
for(int j = ql; j <= qr; ++j) {
++cnt2[typ[j]]; tmp = max(tmp, 1ll * cnt2[typ[j]] * aa[j]);
}
ans[q[i].id] = tmp;
continue;
}
while(r < qr) {
++r; ++cnt[typ[r]]; now = max(now, 1ll * cnt[typ[r]] * aa[r]);
}
tmp = now;
while(l > ql){
--l; ++cnt[typ[l]]; now = max(now, 1ll * cnt[typ[l]] * aa[l]);
}
ans[q[i].id] = now;
while(l < rb[k] + 1) {
--cnt[typ[l]];
l++;
}
now = tmp;
}
}
for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
return 0;
}
