暑假学的东西，现在才来写
先推荐莫队算法——从入门到紫题&&dX的莫队题单
普通莫队
口胡一下时间复杂度（默认\(m，n\)同阶）
左指针单次操作在块内移动次数为\(O(\sqrt{n})\),n次操作加上从左往右总移动次数\(O(n)\),左指针移动次数为\(O(n\sqrt{n})\)
右指针在左指针每块移动次数为\(O(n)\)，左指针共经过\(O(\sqrt{n})\)块，右指针总时间复杂度为\(O(n\sqrt{n})\)
所以普通莫队的时间复杂度为\(O(n\sqrt{n}f(n)+nf'(n))\)
（默认\(n,m\)同阶,\(f(n)\)为移动单次指针的代价，\(f'(n)\)为单次询问的代价）
但是这是极限数据，事实上莫队完全跑不到这么多，且莫队常数小，开了O2跑飞快，有图为证：
普通莫队还有方法优化常数，具体见上面那篇文章
接下来讲下例题
P5268 [SNOI2017]一个简单的询问
这题直接做肯定是不可做的（四维莫队似乎也可以做到\(O(n^{\frac{7}{4}})\)
但我们可以考虑容斥
由于\(get(l,r,x)=get(1,r,x)−get(1,l−1,x)\)
我们令\(g(l,x)=get(1,l,x)\)
则要求的是\(\sum_{0}^{\infty} g(r1,x)g(r2,x)−g(r1,x)g(l2−1,x)−g(l1−1,x)g(r2,x)+g(l1−1,x)g(l2−1,x)\)
然后拆成四个询问就能做了
#include<cstdio>
#include<cmath>
#include<algorithm>
#define re register
using namespace std;
const int maxm=1e5+5;
int n,m,k,res;
int a[maxm],belong[maxm],ans[maxm],cnt1[maxm*2],cnt2[maxm<<1];
int l,r;
struct qq
{
int l,r,id;
inline bool operator<(const qq &x)const
{
return belong[l]==belong[x.l]?(belong[l]&1?r<x.r:r>x.r):l<x.l;
}
}q[maxm*2];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline void add1(int x)
{
++cnt1[a[x]];
res+=cnt2[a[x]];
}
inline void add2(int x)
{
++cnt2[a[x]];
res+=cnt1[a[x]];
}
inline void del1(int x)
{
--cnt1[a[x]];
res-=cnt2[a[x]];
}
inline void del2(int x)
{
--cnt2[a[x]];
res-=cnt1[a[x]];
}
signed main()
{
n=read();
int Q=0;
int t=sqrt(n);
for(re int i=1;i<=n;++i) a[i]=read(),belong[i]=(i-1)/t+1;
m=read();
for(re int i=1;i<=m;++i)
{
int l1=read(),r1=read(),l2=read(),r2=read();
q[++Q]=qq{r1,r2,i};
q[++Q]=qq{l1-1,r2,-i};
q[++Q]=qq{l2-1,r1,-i};
q[++Q]=qq{l1-1,l2-1,i};
}
for(re int i=1;i<=Q;++i) if(q[i].l>q[i].r) swap(q[i].l,q[i].r);
sort(q+1,q+Q+1);
for(re int i=1;i<=Q;++i)
{
while(l<q[i].l) add2(++l);
while(l>q[i].l) del2(l--);
while(r<q[i].r) add1(++r);
while(r>q[i].r) del1(r--);
int k=abs(q[i].id);
if(q[i].id<0) ans[k]-=res;
else ans[k]+=res;
}
for(re int i=1;i<=m;++i) printf("%d\n",ans[i]);
}
P4396 [AHOI2013]作业
这题我们可以联想到莫队（我也不知怎么想到的）
我们想一下莫队的复杂度\(O(n\sqrt{n}f(n)+nf'(n))\)
为了保证不鸡肋\(f(n)\)必须为\(O(1)\)(一般\(O(logn)\)就寄了)，\(f'(n)\)可以是\(O(\sqrt{n})的\)
\(O(1)-O(\sqrt{n})\),你想到了什么，分块
我们对值域分块，再随便搞搞就过了
代码就不放了，主要我也不知道当时为什么写莫队套树状数组，还能过
P3730 曼哈顿交易
同理，真的差不多
放个代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,N1=505;
int ans[N],a[N],idx,block,num,bl[N];
int v[N1],val[N],cnt[N];
int L[N1],R[N1];
int n,m;
struct node
{
int l,r,k,id;
inline bool operator<(const node res)const
{
return bl[l]!=bl[res.l]?l<res.l:(bl[l]&1?r<res.r:r>res.r);
}
}s[N];
map<int,int>mp;
inline void add(int x)
{
--v[bl[cnt[x]]],--val[cnt[x]];
++cnt[x];
++v[bl[cnt[x]]],++val[cnt[x]];
}
inline void del(int x)
{
--v[bl[cnt[x]]],--val[cnt[x]];
--cnt[x];
++v[bl[cnt[x]]],++val[cnt[x]];
}
inline int ask(int k)
{
for(int i=1;i<=num;++i)
if(k>v[i]) k-=v[i];
else
for(int j=L[i];j<=R[i];++j)
if(k>val[j]) k-=val[j];
else return j;
return -1;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)
{
cin>>a[i];
if(!mp[a[i]]) mp[a[i]]=++idx;
a[i]=mp[a[i]];
}
for(int i=1;i<=m;++i) cin>>s[i].l>>s[i].r>>s[i].k,s[i].id=i;
block=sqrt(n),num=(n-1)/block+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/block+1;
for(int i=1;i<=num;++i) L[i]=R[i-1]+1,R[i]=i*block;
R[num]=n;
sort(&s[1],&s[n+1]);
int l=1,r=0;
for(int i=1;i<=m;++i)
{
while(r<s[i].r) add(a[++r]);
while(l>s[i].l) add(a[--l]);
while(l<s[i].l) del(a[l++]);
while(r>s[i].r) del(a[r--]);
ans[s[i].id]=ask(s[i].k);
}
for(int i=1;i<=m;++i) cout<<ans[i]<<endl;
}
Tree and Queries
先把树转为dfn序，然后就是莫队板子了
代码不放了
带修莫队
就多了一维，注意块长开\(O(n^{\frac{2}{3}})\)
好像没了
P1903 [国家集训队] 数颜色 / 维护队列
板子
#include<cstdio>
#include<cmath>
#include<algorithm>
#define re register
#define int long long
using namespace std;
const int maxm=2e5+5;
int n,m,k,res;
int a[maxm],belong[maxm],ans[maxm],cnt[1000005];
struct qq
{
int l,r,t,id;
}q[maxm];
struct xg
{
int x,y;
}g[maxm];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline int cmp(qq a, qq 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.t < b.t);
}
inline void add(int x)
{
if(++cnt[x]==1) ++res;
}
inline void del(int x)
{
if(--cnt[x]==0) --res;
}
signed main()
{
n=read(),m=read();
int Q1=0,Q2=0;
int t=pow(n,2.0/3.0);
for(re int i=1;i<=n;++i) a[i]=read(),belong[i]=(i-1)/t+1;
char opt;
int x,y;
for(re int i=1;i<=m;++i)
{
scanf(" %c",&opt);
x=read(),y=read();
if(opt=='Q') ++Q1,q[Q1]={x,y,Q2,Q1};
else g[++Q2]={x,y};
}
sort(q+1,q+Q1+1,cmp);
int l=1,r=0;
t=0;
for(re int i=1;i<=Q1;++i)
{
while(r<q[i].r) add(a[++r]);
while(r>q[i].r) del(a[r--]);
while(l<q[i].l) del(a[l++]);
while(l>q[i].l) add(a[--l]);
while(t<q[i].t)
{
++t;
if(g[t].x>=q[i].l&&g[t].x<=q[i].r) del(a[g[t].x]),add(g[t].y);
swap(a[g[t].x],g[t].y);
}
while(t>q[i].t)
{
if(g[t].x>=q[i].l&&g[t].x<=q[i].r) del(a[g[t].x]),add(g[t].y);
swap(a[g[t].x],g[t].y);
--t;
}
ans[q[i].id]=res;
}
for(re int i=1;i<=Q1;++i) printf("%d\n",ans[i]);
}
Machine Learning
也是板子，暴力取mex是\(O(\sqrt{n})\)的，不影响复杂度
#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=1e6+5;
int n,m,k;
int ccnt[N],a[N],belong[N],ans[N],cnt[N],b[N];
struct qq
{
int l,r,t,id;
}q[N];
struct xg
{
int x,y;
}g[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline int cmp(qq a, qq 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.t<b.t);
}
inline void add(int x)
{
--ccnt[cnt[x]++];
++ccnt[cnt[x]];
}
inline void del(int x)
{
--ccnt[cnt[x]--];
++ccnt[cnt[x]];
}
inline int mex()
{
int res=1;
while(ccnt[res]) ++res;
return res;
}
int idx;
signed main()
{
idx=n=read(),m=read();
int Q1=0,Q2=0;
int t=pow(n,2.0/3.0);
for(re int i=1;i<=n;++i) b[i]=a[i]=read(),belong[i]=(i-1)/t+1;
int opt,x,y;
for(re int i=1;i<=m;++i)
{
opt=read(),x=read(),y=read();
if(opt==1) ++Q1,q[Q1]={x,y,Q2,Q1};
else g[++Q2]={x,y},b[++idx]=y;
}
sort(b+1,b+idx+1);
int M=unique(b+1,b+idx+1)-b-1;
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+M+1,a[i])-b;
for(int i=1;i<=Q2;++i) g[i].y=lower_bound(b+1,b+M+1,g[i].y)-b;
sort(q+1,q+Q1+1,cmp);
int l=1,r=0;
t=0;
for(re int i=1;i<=Q1;++i)
{
while(r<q[i].r) add(a[++r]);
while(r>q[i].r) del(a[r--]);
while(l<q[i].l) del(a[l++]);
while(l>q[i].l) add(a[--l]);
while(t<q[i].t)
{
++t;
if(g[t].x>=q[i].l&&g[t].x<=q[i].r) del(a[g[t].x]),add(g[t].y);
swap(a[g[t].x],g[t].y);
}
while(t>q[i].t)
{
if(g[t].x>=q[i].l&&g[t].x<=q[i].r) del(a[g[t].x]),add(g[t].y);
swap(a[g[t].x],g[t].y);
--t;
}
ans[q[i].id]=mex();
}
for(re int i=1;i<=Q1;++i) printf("%d\n",ans[i]);
}
回滚莫队
当莫队的过程中我们无法用合理的代价添加或删除时，可以考虑只删除或不添加莫队，也就是回滚莫队
歴史の研究
这题我们在插入时可以\(O(1)\)判断，可删除时便不容易寻找答案，所以我们使用回滚莫队
#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int maxm=1e5+5,maxn=1e3+5;
int n,Q,t,t1;
int belong[maxm],a[maxm],b[maxm],R[maxn],cnt[maxm],cnt1[maxm],ans[maxm];
struct query
{
int l,r,id;
inline bool operator<(const query&x)const
{
return belong[l]==belong[x.l]?r<x.r:l<x.l;
}
}q[maxm];
inline void add(const int &x,int &res)
{
++cnt[x];
res=max(res,cnt[x]*b[x]);
}
inline void del(const int &x)
{
--cnt[x];
}
inline void add1(const int &x,int &res)
{
++cnt1[x];
res=max(res,cnt1[x]*b[x]);
}
inline void del1(const int &x)
{
--cnt1[x];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>Q;
t=sqrt(n*n/Q);
t1=(n-1)/t+1;
for(re int i=1;i<=t1;++i) R[i]=i*t;
R[t1]=n;
for(re int i=1;i<=n;++i) cin>>a[i],b[i]=a[i],belong[i]=(i-1)/t+1;
sort(b+1,b+n+1);
int M=unique(b+1,b+n+1)-b-1;
for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+M+1,a[i])-b;
for(re int i=1;i<=Q;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+Q+1);
int res,res1,last=0,l=1,r=0,ll;
for(re int i=1;i<=Q;++i)
{
if(belong[q[i].l]==belong[q[i].r])
{
for(re int j=q[i].l;j<=q[i].r;++j) add1(a[j],ans[q[i].id]);
for(re int j=q[i].l;j<=q[i].r;++j) del1(a[j]);
continue;
}
if(belong[q[i].l]!=last)
{
last=belong[q[i].l];
for(re int j=l;j<=r;++j) del(a[j]);
l=R[last]+1,r=l-1;
ll=l;
res=0;
}
while(r<q[i].r) add(a[++r],res);
res1=res;
while(l>q[i].l) add(a[--l],res1);
while(l<ll) del(a[l++]);
ans[q[i].id]=res1;
}
for(re int i=1;i<=Q;++i) cout<<ans[i]<<endl;
return 0;
}
P5906 【模板】回滚莫队&不删除莫队
板子，没什么说的
#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
#define re register
using namespace std;
const int maxm=2e5+5;
int n,Q,t,t1;
int last,l=1,r,res,res1;
int a[maxm],belong[maxm],b[maxm],R[maxm],ans[maxm],pre[maxm],pre1[maxm],suc[maxm],suc2[maxm];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct qq
{
int l,r,id;
inline bool operator<(const qq &res)
{
return belong[l]==belong[res.l]?r<res.r:l<res.l;
}
}q[maxm];
signed main()
{
n=read();
for(re int i=1;i<=n;++i) b[i]=a[i]=read();
Q=read();
t=sqrt(n);
t1=(n-1)/t+1;
sort(b+1,b+n+1);
int M=unique(b+1,b+n+1)-b-1;
for(re int i=1;i<=n;++i) belong[i]=(i-1)/t+1,a[i]=lower_bound(b+1,b+M+1,a[i])-b;
for(re int i=1;i<=Q;++i) q[i]=qq{read(),read(),i};
sort(q+1,q+Q+1);
for(re int i=1;i<=t1;++i) R[i]=i*t;
R[t1]=n;
for(re int i=1;i<=Q;++i)
{
if(belong[q[i].l]==belong[q[i].r])
{
res=0;
for(re int j=q[i].l;j<=q[i].r;++j) pre1[a[j]]=0;
for(re int j=q[i].l;j<=q[i].r;++j)
{
if(!pre1[a[j]]) pre1[a[j]]=j;
res=max(res,j-pre1[a[j]]);
}
ans[q[i].id]=res;
continue;
}
if(belong[q[i].l]!=last)
{
for(re int j=l;j<=r;++j) suc[a[j]]=pre[a[j]]=0;
l=R[belong[q[i].l]]+1,r=l-1;
res1=res=0;
last=belong[q[i].l];
}
while(r<q[i].r)
{
++r;
suc[a[r]]=r;
if(!pre[a[r]]) pre[a[r]]=r;
res=max(res,r-pre[a[r]]);
}
res1=res;
while(l>q[i].l)
{
if(!suc[a[--l]]) suc[a[l]]=l;
res1=max(res1,suc[a[l]]-l);
}
while(l<R[belong[q[i].l]]+1)
{
if(suc[a[l]]==l)suc[a[l]]=0;
++l;
}
ans[q[i].id]=res1;
}
for(re int i=1;i<=Q;++i) cout<<ans[i]<<endl;
}
P3709 大爷的字符串题
就是求区间众数的出现次数（普通莫队也能做）
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int R[N],block,num,n,m;
int bl[N],idx,a[N];
struct node
{
int l,r,id;
inline bool operator<(const node &res)const
{
return bl[l]==bl[res.l]?r<res.r:l<res.l;
}
}q[N];
int cnt[N],ans[N],last,l=1,r,res,p;
int b[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
block=sqrt(n),num=(n-1)/block+1;
for(int i=1;i<=num;++i) R[i]=i*block;
R[num]=n;
for(int i=1;i<=n;++i)
cin>>a[i],b[i]=a[i],bl[i]=(i-1)/block+1;
sort(b+1,b+n+1);
int M=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+M+1,a[i])-b;
for(int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+m+1);
for(int i=1;i<=m;++i)
{
if(bl[q[i].l]==bl[q[i].r])
{
int res1=0;
for(int j=q[i].l;j<=q[i].r;++j) cnt[a[j]]=0;
for(int j=q[i].l;j<=q[i].r;++j) res1=max(res1,++cnt[a[j]]);
ans[q[i].id]=res1;
continue;
}
if(last!=bl[q[i].l])
{
while(r>R[bl[q[i].l]]) cnt[a[r--]]=0;
while(l<=R[bl[q[i].l]]) cnt[a[l++]]=0;
r=l-1,p=l,res=0,last=bl[q[i].l];
}
while(r<q[i].r) res=max(res,++cnt[a[++r]]);
int res1=res;
while(l>q[i].l) res1=max(res1,++cnt[a[--l]]);
while(l<p) --cnt[a[l++]];
ans[q[i].id]=res1;
}
for(int i=1;i<=m;++i) cout<<"-"<<ans[i]<<endl;
}
树上莫队
就是在树上跑莫队
不，是在欧拉序上莫队，也就多个lca
此时我才体会到前开后闭有多妙
COT2 - Count on a tree II
板子
#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N=5e5+5;
int to[N],head[N],ne[N],tot;
int n,m,res;
int ans[N],s[N],v[N],cnt[N],belong[N],block,num,vis[N],b[N];
inline void add(int x,int y)
{
to[++tot]=y,ne[tot]=head[x],head[x]=tot;
}
int f[N][21];
int st[N],ed[N],idx;
void dfs(int x,int fa)
{
s[++idx]=x,st[x]=idx,f[x][0]=fa;
for(int i=1;f[x][i-1];++i) f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x],y;i;i=ne[i])
if((y=to[i])!=fa) dfs(y,x);
s[++idx]=x,ed[x]=idx;
}
struct qq
{
int l,r,lca,id;
inline bool operator<(const qq &x)const
{
return belong[l]==belong[x.l]?(belong[l]&1?r<x.r:r>x.r):l<x.l;
}
}q[N];
inline int pd(int x,int y){return st[x]<=st[y]&&ed[x]>=ed[y];}
inline int lca(int x,int y)
{
if(pd(y,x)) return y;
if(pd(x,y)) return x;
for(int i=20;i>=0;--i)
if(f[x][i]&&!pd(f[x][i],y)) x=f[x][i];
return f[x][0];
}
inline void add(int x)
{
vis[x]^=1;
if(vis[x]){if(++cnt[v[x]]==1) ++res;}
else if(--cnt[v[x]]==0) --res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int x,y;
block=sqrt(2*n);
for(re int i=1;i<=2*n;++i) belong[i]=(i-1)/block+1;
for(re int i=1;i<=n;++i) cin>>v[i],b[i]=v[i];
sort(b+1,b+n+1);
int M=unique(b+1,b+n+1)-b-1;
for(re int i=1;i<=n;++i) v[i]=lower_bound(b+1,b+M+1,v[i])-b;
for(int i=1;i<n;++i) cin>>x>>y,add(x,y),add(y,x);
dfs(1,0);
for(re int i=1;i<=m;++i)
{
cin>>x>>y;
int k=lca(x,y);
if(x==k||y==k)
{
if(st[y]<st[x]) swap(x,y);
q[i]={st[x],st[y],0,i};
}
else
{
if(ed[y]<st[x]) swap(x,y);
q[i]={ed[x],st[y],k,i};
}
}
sort(q+1,q+m+1);
int l=1,r=0;
for(re int i=1;i<=m;++i)
{
while(l>q[i].l) add(s[--l]);
while(r<q[i].r) add(s[++r]);
while(l<q[i].l) add(s[l++]);
while(r>q[i].r) add(s[r--]);
if(q[i].lca) add(q[i].lca);
ans[q[i].id]=res;
if(q[i].lca) add(q[i].lca);
}
for(re int i=1;i<=m;++i) cout<<ans[i]<<endl;
}
P4074 [WC2013] 糖果公园
树上带修莫队，超级套娃
#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N=2e6+5;
int to[N],f[N],ne[N],tot,l=1,r,ti;
int n,m,res,Q;
int w[N],c[N];
int ans[N],s[N],v[N],cnt[N],belong[N],block,num,vis[N],b[N];
inline void add(int x,int y)
{
to[++tot]=y,ne[tot]=f[x],f[x]=tot;
}
int fa[N][21];
int st[N],ed[N],t;
void dfs(int x,int dad)
{
s[++t]=x,st[x]=t;
fa[x][0]=dad;
for(int i=1;i<=20;++i)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=f[x],y;i;i=ne[i])
if((y=to[i])!=dad) dfs(y,x);
s[++t]=x,ed[x]=t;
}
struct qq
{
int l,r,lca,t,id;
inline bool operator<(const qq &x)
{
return belong[l]==belong[x.l]?(belong[r]==belong[x.r]?t<x.t:r<x.r):l<x.l;
}
}q[N];
struct xg
{
int x,y;
}g[N];
inline int pd(int x,int y){return st[x]<=st[y]&&ed[x]>=ed[y];}
inline int lca(int x,int y)
{
if(pd(y,x)) return y;
if(pd(x,y)) return x;
for(int i=20;~i;--i)
if(!pd(fa[x][i],y)&&fa[x][i]) x=fa[x][i];
return fa[x][0];
}
inline void add1(int x)
{
x=s[x],vis[x]^=1;
res-=w[cnt[c[x]]]*v[c[x]];
if(vis[x]) ++cnt[c[x]];
else --cnt[c[x]];
res+=w[cnt[c[x]]]*v[c[x]];
}
inline void up(int x)
{
int x1=st[g[x].x],x2=ed[g[x].x];
if(x1>=l&&x1<=r) add1(x1);
if(x2>=l&&x2<=r) add1(x2);
swap(c[s[x1]],g[x].y);
if(x1>=l&&x1<=r) add1(x1);
if(x2>=l&&x2<=r) add1(x2);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>Q;
int QQ=0;
int x,y;
block=pow(2*n,2.0/3.0);
for(re int i=1;i<=2*n;++i) belong[i]=(i-1)/block+1;
for(re int i=1;i<=m;++i) cin>>v[i];
for(re int i=1;i<=n;++i) cin>>w[i],w[i]+=w[i-1];
for(int i=1;i<n;++i)
cin>>x>>y,add(x,y),add(y,x);
dfs(1,0);
for(re int i=1;i<=n;++i) cin>>c[i];
int T=0,ty;
for(re int i=1;i<=Q;++i)
{
cin>>ty>>x>>y;
if(ty)
{
++QQ;
int k=lca(x,y);
if(x==k||y==k)
{
if(st[y]<st[x]) swap(x,y);
q[QQ]={st[x],st[y],0,T,QQ};
}
else
{
if(ed[y]<st[x]) swap(x,y);
q[QQ]={ed[x],st[y],k,T,QQ};
}
}
else g[++T]={x,y};
}
sort(q+1,q+QQ+1);
for(re int i=1;i<=QQ;++i)
{
while(l>q[i].l) add1(--l);
while(l<q[i].l) add1(l++);
while(r>q[i].r) add1(r--);
while(r<q[i].r) add1(++r);
while(ti<q[i].t) up(++ti);
while(ti>q[i].t) up(ti--);
if(q[i].lca) add1(st[q[i].lca]);
ans[q[i].id]=res;
if(q[i].lca) add1(st[q[i].lca]);
}
for(re int i=1;i<=QQ;++i) cout<<ans[i]<<endl;
}
ADAFTBLL - Ada and Football
也是板子
贴个代码以纪念我块长取\(\sqrt{n}\)而爆炸的操作
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int head[N],to[N],ne[N],toto;
inline void add(int x,int y)
{
to[++toto]=y,ne[toto]=head[x],head[x]=toto;
}
int f[N][21];
int s[N],idx,st[N],ed[N];
int n,m,v[N],bl[N];
void dfs(int x,int fa)
{
s[++idx]=x,st[x]=idx,f[x][0]=fa;
for(int i=0;f[x][i];++i) f[x][i+1]=f[f[x][i]][i];
for(int i=head[x];i;i=ne[i])
if(to[i]!=fa) dfs(to[i],x);
s[++idx]=x,ed[x]=idx;
}
struct xg
{
int x,y;
}g[N];
struct query
{
int l,r,lca,t,id;
inline bool operator<(const query x)const
{
return bl[l]==bl[x.l]?(bl[r]==bl[x.r]?t<x.t:r<x.r):l<x.l;
}
}q[N];
inline int pd(int x,int y){return st[x]<=st[y]&&ed[x]>=ed[y];}
inline int lca(int x,int y)
{
if(pd(x,y)) return x;
if(pd(y,x)) return y;
for(int i=20;~i;--i)
if(f[x][i]&&!pd(f[x][i],y)) x=f[x][i];
return f[x][0];
}
int Q,T,ans[N],vis[N],res,cnt[N];
inline void add(int x)
{
vis[x]^=1;
if(vis[x]) res+=(cnt[v[x]]++);
else res-=(--cnt[v[x]]);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>v[i];
for(int x,y,i=1;i<n;++i) cin>>x>>y,++x,++y,add(x,y),add(y,x);
dfs(1,0);
for(int opt,x,y,i=1;i<=m;++i)
{
cin>>opt>>x>>y,++x;
if(opt==1) g[++T]={x,y};
else
{
++y,++Q;
int k=lca(x,y);
if(k==x||k==y)
{
if(st[y]<st[x]) swap(x,y);
q[Q]={st[x],st[y],0,T,Q};
}
else
{
if(ed[y]<st[x]) swap(x,y);
q[Q]={ed[x],st[y],k,T,Q};
}
}
}
int block=pow(2*n,0.666666);
for(int i=1;i<=2*n;++i) bl[i]=(i-1)/block+1;
sort(q+1,q+Q+1);
int l=1,r=0,t=0;
for(int i=1;i<=m;++i)
{
while(l<q[i].l) add(s[l++]);
while(r>q[i].r) add(s[r--]);
while(l>q[i].l) add(s[--l]);
while(r<q[i].r) add(s[++r]);
while(t<q[i].t)
{
++t;
int k1=st[g[t].x],k2=ed[g[t].x];
if(k1>=l&&k1<=r) add(s[k1]);
if(k2>=l&&k2<=r) add(s[k2]);
swap(v[g[t].x],g[t].y);
if(k1>=l&&k1<=r) add(s[k1]);
if(k2>=l&&k2<=r) add(s[k2]);
}
while(t>q[i].t)
{
int k1=st[g[t].x],k2=ed[g[t].x];
if(k1>=l&&k1<=r) add(s[k1]);
if(k2>=l&&k2<=r) add(s[k2]);
swap(v[g[t].x],g[t].y);
if(k1>=l&&k1<=r) add(s[k1]);
if(k2>=l&&k2<=r) add(s[k2]);
--t;
}
if(q[i].lca) add(q[i].lca);
ans[q[i].id]=res;
if(q[i].lca) add(q[i].lca);
}
for(int i=1;i<=Q;++i) cout<<ans[i]<<endl;
}
P4175 [CTSC2008]网络管理
树上带修第\(K\)大
#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N=2e5+5;
int to[N],f[N],ne[N],tot,l=1,r,ti;
int n,m,res,Q,su,block1,num1,L[N],R[N];
int w[N],c[N];
int ans[N],s[N],v[N],cnt[N],belong[N],block,num,vis[N],b[N],belong1[N];
int sum[N];
int ss[N];
inline void add(int x,int y)
{
to[++tot]=y,ne[tot]=f[x],f[x]=tot;
}
int fa[N][21];
int st[N],ed[N],t;
void dfs(int x,int dad)
{
s[++t]=x,st[x]=t;
fa[x][0]=dad;
for(int i=1;i<=20;++i)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=f[x],y;i;i=ne[i])
if((y=to[i])!=dad) dfs(y,x);
s[++t]=x,ed[x]=t;
}
struct qq
{
int l,r,lca,t,k,id;
inline bool operator<(const qq &x)
{
return belong[l]==belong[x.l]?(belong[r]==belong[x.r]?t<x.t:r<x.r):l<x.l;
}
}q[N];
struct xg
{
int x,y;
}g[N];
inline int pd(int x,int y){return st[x]<=st[y]&&ed[x]>=ed[y];}
inline int lca(int x,int y)
{
if(pd(y,x)) return y;
if(pd(x,y)) return x;
for(int i=20;i>=0;--i)
if(!pd(fa[x][i],y)&&fa[x][i]!=0) x=fa[x][i];
return fa[x][0];
}
inline void add1(int x)
{
x=s[x],vis[x]^=1;
int y=v[x];
if(vis[x]) ++cnt[y],++ss[belong1[y]];
else --cnt[y],--ss[belong1[y]];
}
inline int ask(int k)
{
re int res=num1;
for(;res;--res)
{
if(k>ss[res]) k-=ss[res];
else break;
}
if(!res) return -1;
for(re int i=R[res];i>=L[res];--i)
{
if(k<=cnt[i]) return sum[i];
else k-=cnt[i];
}
}
inline void up(int x)
{
int x1=st[g[x].x],x2=ed[g[x].x];
if(x1>=l&&x1<=r) add1(x1);
if(x2>=l&&x2<=r) add1(x2);
swap(v[s[x1]],g[x].y);
if(x1>=l&&x1<=r) add1(x1);
if(x2>=l&&x2<=r) add1(x2);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>Q;
int QQ=0;
int x,y;
block=pow(2*n,2.0/3.0);
for(re int i=1;i<=2*n;++i) belong[i]=(i-1)/block+1;
for(re int i=1;i<=n;++i) cin>>v[i],sum[++su]=v[i];
for(int i=1;i<n;++i) cin>>x>>y,add(x,y),add(y,x);
dfs(1,0);
int T=0,ty;
for(re int i=1;i<=Q;++i)
{
cin>>ty>>x>>y;
if(ty)
{
++QQ;
if(st[x]>st[y]) swap(x,y);
int k=lca(x,y);
if(x==k) q[QQ]={st[x],st[y],0,T,ty,QQ};
else q[QQ]={ed[x],st[y],k,T,ty,QQ};
}
else g[++T]={x,y},sum[++su]=y;
}
block1=pow(su,2.0/3.0);
num1=(su-1)/block1+1;
for(re int i=1;i<=num1;++i) L[i]=(i-1)*block1-1,R[i]=i*block1;
R[num1]=su;
for(re int i=1;i<=su;++i) belong1[i]=(i-1)/block1+1;
sort(q+1,q+QQ+1);
sort(sum+1,sum+su+1);
int M=unique(sum+1,sum+su+1)-sum-1;
for(re int i=1;i<=n;++i) v[i]=lower_bound(sum+1,sum+M+1,v[i])-sum;
for(re int i=1;i<=T;++i) g[i].y=lower_bound(sum+1,sum+M+1,g[i].y)-sum;
for(re int i=1;i<=QQ;++i)
{
while(l>q[i].l) add1(--l);
while(l<q[i].l) add1(l++);
while(r>q[i].r) add1(r--);
while(r<q[i].r) add1(++r);
while(ti<q[i].t) up(++ti);
while(ti>q[i].t) up(ti--);
if(q[i].lca) add1(st[q[i].lca]);
ans[q[i].id]=ask(q[i].k);
if(q[i].lca) add1(st[q[i].lca]);
}
for(re int i=1;i<=QQ;++i)
{
if(ans[i]==-1) cout<<"invalid request!"<<endl;
else cout<<ans[i]<<endl;
}
}
莫队二次离线
\(\text{lxl}\)神仙发明的黑科技
先膜为敬
P4887 【模板】莫队二次离线（第十四分块(前体)）
板子
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&-x
using namespace std;
const int N=1e5+5;
int n,m,k,block;
int cnt[N],a[N],g[N];
int bl[N];
ll ans[N];
vector<int>s;
struct query
{
int l,r,id;
ll v;
inline bool operator<(const query &res)const
{
return bl[l]!=bl[res.l]?l<res.l:r<res.r;
}
}q[N];
struct ask
{
int l,r,v,id;
};
vector<ask>rg[N];
inline int getcount(int x)
{
int res=0;
for(;x;x-=lowbit(x)) ++res;
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k,block=sqrt(n);
for(int i=1;i<=n;++i) cin>>a[i],bl[i]=i/block;
for(int i=0;i<1<<14;++i) if(getcount(i)==k) s.push_back(i);
for(int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+m+1);
for(int i=1;i<=n;++i)
{
g[i]=cnt[a[i]];
for(auto x:s) ++cnt[a[i]^x];
}
memset(cnt,0,sizeof cnt);
for(int i=1,L=1,R=0;i<=m;++i)
{
int l=q[i].l,r=q[i].r;
if(R>r) rg[L-1].push_back((ask){r+1,R,1,i});
while(R>r) q[i].v-=g[R--];
if(R<r) rg[L-1].push_back((ask){R+1,r,-1,i});
while(R<r) q[i].v+=g[++R];
if(L<l) rg[R].push_back((ask){L,l-1,-1,i});
while(L<l) q[i].v+=g[L++]+!k;
if(L>l) rg[R].push_back((ask){l,L-1,1,i});
while(L>l) q[i].v-=g[--L]+!k;
}
for(int i=1;i<=n;++i)
{
for(auto x:s) ++cnt[a[i]^x];
for(auto u:rg[i])
for(int p=u.l;p<=u.r;++p) q[u.id].v+=cnt[a[p]]*u.v;
}
for(int i=1;i<=m;++i) q[i].v+=q[i-1].v,ans[q[i].id]=q[i].v;
for(int i=1;i<=m;++i) cout<<ans[i]<<endl;
return 0;
}
P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II
也是板子，贴个代码以纪念把全局变量打成局部变量而爆炸的我
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&-x
using namespace std;
const int N=2e5+5,N1=505;
struct BIT
{
int n,c[N];
inline void init(int _n){n=_n;for(int i=1;i<=n;++i)c[i]=0;}
inline void add(int x,int v){for(;x<=n;x+=lowbit(x)) c[x]+=v;}
inline int ask(int x){int res=0;for(;x;x-=lowbit(x)) res+=c[x];return res;}
}t;
int block,n,m,a[N];
int bl[N],Lp[N1],Rp[N1],bk;
ll cnt[N],tag[N1];
int num[N];
ll ans[N],lv[N],rv[N];
struct query
{
int l,r,id;
inline bool operator<(const query &res)const{return bl[l]==bl[res.l]?r<res.r:l<res.l;}
}q[N];
struct rag
{
int l,r,id,v;
};
vector<rag>rg[2][N];
inline void addL(int x)
{
for(int i=x;i>=Lp[bl[x]];--i) ++cnt[i];
for(int i=bl[x]-1;i>0;--i) ++tag[i];
}
inline void addR(int x)
{
for(int i=x;i<=Rp[bl[x]];++i) ++cnt[i];
for(int i=bl[x]+1;i<=bl[n];++i) ++tag[i];
}
inline int ask(int x)
{
return cnt[x]+tag[bl[x]];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
block=sqrt(n);
for(int i=1;i<=n;++i) cin>>a[i],num[i]=a[i];
sort(num+1,num+n+1);
int M=unique(num+1,num+n+1)-num-1;
for(int i=1;i<=n;++i) a[i]=lower_bound(num+1,num+M+1,a[i])-num;
for(int i=1;i<=n;++i) bl[i]=(i-1)/block+1;
for(int i=1;i<=bl[n];++i) Lp[i]=Rp[i-1]+1,Rp[i]=i*block;
Rp[bl[n]]=n;
for(int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+m+1);
t.init(n);
for(int i=1;i<=n;++i)
lv[i]=lv[i-1]+t.ask(n)-t.ask(a[i]),t.add(a[i],1);
t.init(n);
for(int i=n;i;--i)
rv[i]=rv[i+1]+t.ask(a[i]-1),t.add(a[i],1);
for(int L=1,R=0,i=1;i<=m;++i)
{
int l=q[i].l,r=q[i].r,id=q[i].id;
if(R<r)
rg[0][L-1].push_back((rag){R+1,r,id,-1});
if(R>r)
rg[0][L-1].push_back((rag){r+1,R,id,1});
if(L>l)
rg[1][r+1].push_back((rag){l,L-1,id,-1});
if(l>L)
rg[1][r+1].push_back((rag){L,l-1,id,1});
ans[id]+=rv[l]-rv[L]+lv[r]-lv[R];
L=l,R=r;
}
for(int i=1;i<=n;++i)
{
addL(a[i]-1);
for(auto x:rg[0][i])
{
ll res=0;
for(int j=x.l;j<=x.r;++j) res+=ask(a[j]);
ans[x.id]+=x.v*res;
}
}
memset(cnt,0,sizeof cnt);
memset(tag,0,sizeof tag);
for(int i=n;i;--i)
{
addR(a[i]+1);
for(auto x:rg[1][i])
{
ll res=0;
for(int j=x.l;j<=x.r;++j) res+=ask(a[j]);
ans[x.id]+=x.v*res;
}
}
for(int i=1;i<=m;++i) ans[q[i].id]+=ans[q[i-1].id];
for(int i=1;i<=m;++i) cout<<ans[i]<<endl;
return 0;
}
P5501 [LnOI2019]来者不拒，去者不追
先咕着
莫队+bitset
有些题我们能在\(O(n\sqrt{n}+\frac{n^{2}}{w})\)的时间复杂度内解决问题
则可用莫队+\(bitset\)
P3674 小清新人渣的本愿
板子
#include<cstdio>
#include<bitset>
#include<cmath>
#include<algorithm>
#define re register
using namespace std;
const int maxm=1e5+5,N=1e5+1;
int n,m;
int a[maxm],belong[maxm],ans[maxm],cnt[maxm];
bitset<maxm>s,s1,k;
struct qq
{
int opt,l,r,x,id;
inline bool operator<(const qq &x)const
{
return belong[l]==belong[x.l]?(belong[l]&1?r<x.r:r>x.r):l<x.l;
}
}q[maxm];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline void add(int x)
{
if(++cnt[a[x]]==1) s[a[x]]=s1[N-a[x]]=1;
}
inline void del(int x)
{
if(--cnt[a[x]]==0) s[a[x]]=s1[N-a[x]]=0;
}
signed main()
{
n=read(),m=read();
int t=sqrt(n);
for(re int i=1;i<=n;++i) a[i]=read(),belong[i]=(i-1)/t+1;
for(re int i=1;i<=m;++i) q[i]=qq{read(),read(),read(),read(),i};
int l=1,r=0;
sort(q+1,q+m+1);
for(re int i=1;i<=m;++i)
{
while(l<q[i].l) del(l++);
while(l>q[i].l) add(--l);
while(r>q[i].r) del(r--);
while(r<q[i].r) add(++r);
if(q[i].opt==1)
{
k=s&(s<<q[i].x);
ans[q[i].id]=k.any();
}
else if(q[i].opt==2)
{
k=s&(s1>>N-q[i].x);
ans[q[i].id]=k.any();
}
else
{
for(re int j=1;j*j<=q[i].x;++j)
{
if(q[i].x%j==0)
{
if(s[j]&&s[q[i].x/j])
{
ans[q[i].id]=1;
break;
}
}
}
}
}
for(re int i=1;i<=m;++i)
{
if(ans[i]) printf("hana\n");
else printf("bi\n");
}
}
P5355 [Ynoi2017] 由乃的玉米田
就是在上题基础上多个根号分治
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
#define re register
using namespace std;
const int maxm=1e5+5,N=1e5+1;
int n,m,mx;
int a[maxm],belong[maxm],ans[maxm],cnt[maxm];
int la[maxm],res[maxm];
bitset<maxm>s,s1,k;
vector<int>ss[N];
struct qq
{
int opt,l,r,x,id;
inline bool operator<(const qq &x)const
{
return belong[l]==belong[x.l]?(belong[l]&1?r<x.r:r>x.r):l<x.l;
}
}q[maxm];
struct q1
{
int l,r,x,id;
inline bool operator<(const q1&b)const
{
return x<b.x;
}
}q1[maxm];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline void add(int x)
{
if(++cnt[a[x]]==1) s[a[x]]=s1[N-a[x]]=1;
}
inline void del(int x)
{
if(--cnt[a[x]]==0) s[a[x]]=s1[N-a[x]]=0;
}
signed main()
{
n=read(),m=read();
int cyq=0;
int t=sqrt(n);
for(re int i=1;i<=n;++i) a[i]=read(),belong[i]=(i-1)/t+1,mx=max(mx,a[i]);
for(re int i=1;i<=m;++i) q[i]=qq{read(),read(),read(),read(),i};
int l=1,r=0;
sort(q+1,q+m+1);
for(re int i=1;i<=m;++i)
{
while(l<q[i].l) del(l++);
while(l>q[i].l) add(--l);
while(r>q[i].r) del(r--);
while(r<q[i].r) add(++r);
if(q[i].opt==1)
{
k=s&(s<<q[i].x);
ans[q[i].id]=k.any();
}
else if(q[i].opt==2)
{
k=s&(s1>>N-q[i].x);
ans[q[i].id]=k.any();
}
else if(q[i].opt==3)
{
for(re int j=1;j*j<=q[i].x;++j)
{
if(q[i].x%j==0)
{
if(s[j]&&s[q[i].x/j])
{
ans[q[i].id]=1;
break;
}
}
}
}
else
{
if(q[i].x==0) continue;
if(q[i].x<=t)
{
q1[++cyq]={q[i].l,q[i].r,q[i].x,q[i].id};
continue;
}
for(re int j=1;j*q[i].x<=mx;++j)
{
if(s[j]&&s[j*q[i].x])
{
ans[q[i].id]=1;
break;
}
}
}
}
sort(q1+1,q1+1+cyq);
for(re int i=1;i<=cyq;++i)
{
if(q1[i].x==q1[i-1].x)
{
ans[q1[i].id]=q1[i].l<=res[q1[i].r];
continue;
}
memset(res,0,sizeof res);
memset(la,0,sizeof la);
l=0;
for(re int j=1;j<=n;++j)
{
la[a[j]]=j;
if(a[j]%q1[i].x==0) l=max(l,la[a[j]/q1[i].x]);
if(a[j]*q1[i].x<=mx) l=max(l,la[a[j]*q1[i].x]);
res[j]=l;
}
ans[q1[i].id]=q1[i].l<=res[q1[i].r];
}
for(re int i=1;i<=m;++i)
{
if(ans[i]) printf("yuno\n");
else printf("yumi\n");
}
}
P4688 [Ynoi2016] 掉进兔子洞
先咕着
标签：cnt,int,++,--,maxm,inline,莫队 From： https://www.cnblogs.com/nich666/p/16998104.html