[bzoj2648]小$Z$的袜子——普通莫队
题目大意
给出一个有$n$个数的数列$A:a_1,a_2,a_3\dots a_n$，询问$m$次
每次询问给出一个区间$[l,r]$，询问区间$[l,r]$内抽到一对数值相等的数的概率大小
数据范围
$n,m\leqslant 50000$，$1\leqslant l< r\leqslant n$，$a_i\leqslant n$
题解
不妨设区间$[l,r]$里元素个数为$len$，显然，抽一对数的情况总数为$C_{len}^2$
同时区间里只有$k$种数值，每种数值对应的元素有$s_1,s_2\dots s_k$个，抽一对数值相等的数的情况总数为$C_{s_1}^2+C_{s_2}^2+\dots C_{s_k}^2$
则答案为$$\frac{C_{s_1}^2+C_{s_2}^2+\dots C_{s_k}^2}{C_{len}^2}=\frac{s_1(s_1-1)+s_2(s_2-1)+\dots s_k(s_k-1)}{len(len-1)}=\frac{s_1^2+s_2^2+\dots s_k^2-len}{len(len-1)}$$
那么现在问题简化为，如何即时地统计所有的$s_1,s_2\dots s_k$
这个时候引入一个东西，莫队算法，是莫涛前几年提出的算法，适用于解决离线区间查询问题
Question Ⅰ：这个算法怎么用啊？假设已经得到了区间$[l,r]$需要统计的信息，可以在常数级别的时间内转移到区间$[l-1,r]$、区间$[l+1,r]$、区间$[l,r-1]$、区间$[l,r+1]$
那么可以在$O(n\sqrt n)$的时间复杂度求得所有答案
Question Ⅱ：这个时间复杂度？我们可以调整一下处理每个查询的顺序，保证最优的顺序之下转移区间
将$n$个数分成$\sqrt n$块
按区间排序，以左端点所在块内为第一关键字，右端点为第二关键字，进行排序
然后按这个排序直接暴力，复杂度分析是这样的：
$i$与$i+1$在同一块内，$r$单调递增，所以$r$是$O(n)$的，由于有$\sqrt n$块，所以这一部分时间复杂度是$n\sqrt n$
$i$与$i+1$跨越一块，$r$最多变化$n$，由于有$\sqrt n$块，所以这一部分时间复杂度是$n\sqrt n$
$i$与$i+1$在同一块内，$l$变化不超过$\sqrt n$，跨越一块也不会超过$\sqrt n \times 2$
由于有$m$次询问（和$n$同级），所以时间复杂度是$n\sqrt n$
代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Ford(i,r,l) for(int i=r;i>=l;--i)
inline int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return x;
}
using namespace std;
int n,m,size;
struct data{int l,r,id;long long up,down;}q[50050];
int a[50050],belong[50050];
ll ans,s[50050];
inline bool cmp1(data x,data y) {return belong[x.l]==belong[y.l]?x.r<y.r:x.l<y.l;}
inline bool cmp2(data x,data y) {return x.id<y.id;}
inline ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
inline void update(int x,int c){
ans-=s[x]*s[x];
s[x]+=(ll)c;
ans+=s[x]*s[x];
}
int main(){
n=read(),m=read();
For(i,1,n) a[i]=read();
For(i,1,m) q[i]=(data){read(),read(),i};
size=(int)sqrt(n);
For(i,1,n) belong[i]=(i-1)/size+1;
sort(q+1,q+m+1,cmp1);
int l=1,r=0;
For(i,1,m){
for(;r<q[i].r;r++) update(a[r+1],1);
for(;r>q[i].r;r--) update(a[r],-1);
for(;l<q[i].l;l++) update(a[l],-1);
for(;l>q[i].l;l--) update(a[l-1],1);
if (q[i].l==q[i].r){
q[i].up=0;q[i].down=1;
continue;
}
ll len=q[i].r-q[i].l+1;
q[i].up=ans-len,q[i].down=(len-1)*len;
ll g=gcd(q[i].up,q[i].down);
q[i].up/=g,q[i].down/=g;
}
sort(q+1,q+m+1,cmp2);
For(i,1,m) printf("%lld/%lld\n",q[i].up,q[i].down);
return 0;
}[bzoj2120]数颜色——带修改莫队
题目大意
有$n$支彩色画笔（颜色可能相同）排成一排，有$m$次操作
询问在$[l,r]$中共有几种颜色不同的画笔
把其中一只画笔替换为别的颜色的画笔
数据范围
$n\leqslant 10000,m\leqslant 10000$
所有画笔的颜色表示为$1\leqslant c[i]\leqslant 10^6$
题解
以前做这道题的时候想过用分块去做，具体戳分块题解
其实这道题除了分块，也可以想想莫队的思路
Question Ⅲ：查询操作的区间还是要调整成最优区间，那么修改操作的顺序就会被打乱，怎么解决？对于每一个查询操作，我们记录在它之前最近的修改操作的编号，维护两个时间段之间的修改操作
就是对于现在的这个查询，在它之后执行过的修改操作改回去，在它之前没执行的修改就执行
Question Ⅳ：这个时间复杂度？排序方法：设定块的长度为$S_1$和$S_2$，按照$(\lfloor \frac{l}{S_1} \rfloor,\lfloor \frac{r}{S_2} \rfloor,t)$的三元组小到大排序，其中$t$表示这个询问的时刻之前经历过了几次修改操作
复杂度分析：考虑询问序列中的每个小块，小块内每个询问的一二关键字相同
在这个小块内，显然$t$最多变化$m$，对于每个询问，$l,r$最多变化$S_1$和$S_2$，一共有$\frac{n^2}{S_1S_2}$个这样的块，相邻块之间转移的复杂度为$O(n)$，总复杂度就是$$O(mS_1+mS_2+\frac{n^2m}{S_1S_2}+\frac{n^2m}{S_1S_2})$$
不妨设$n,m$同阶，取$S_1=S_2=n^{\frac{2}{3}}$时可达到最优复杂度$O(n^{\frac{5}{3}})$
程序
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Ford(i,r,l) for(int i=r;i>=l;--i)
inline int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return x;
}
using namespace std;
int n,m,cnt_r,cnt_q;
struct revise{int pos,col,pre;}c[1050];
struct query{int l,r,id,time;}q[10050];
int belong[10050],last[10050];
int colour[1000500],num[1000500],vis[10050];
int ans[10050],sum;
inline bool cmp(query a,query b){return belong[a.l]==belong[b.l]?a.r<b.r:belong[a.l]<belong[b.l];}
inline void cal(int x){
if (vis[x]){
num[colour[x]]--;
if (num[colour[x]]==0) sum--;
}
else{
if (num[colour[x]]==0) sum++;
num[colour[x]]++;
}
vis[x]^=1;
}
inline void change(int x,int c){
if (vis[x]){
cal(x);
colour[x]=c;
cal(x);
}
else colour[x]=c;
}
int main(){
n=read(),m=read();
For(i,1,n) colour[i]=last[i]=read();
For(i,1,m){
char ch[5];scanf("%s",ch);
int x=read(),y=read();
if (ch[0]=='R') c[++cnt_r]=(revise){x,y,last[x]},last[x]=y;
else q[++cnt_q]=(query){x,y,cnt_q,cnt_r};
}
int size=ceil(pow(cnt_q,2.0/3));
For(i,1,cnt_q) belong[i]=(i-1)/size+1;
sort(q+1,q+cnt_q+1,cmp);
int l=1,r=0;
For(i,1,cnt_q){
for (int j=q[i-1].time+1;j<=q[i].time;j++) change(c[j].pos,c[j].col);
for (int j=q[i-1].time;j>=q[i].time+1;j--) change(c[j].pos,c[j].pre);
for (;r<q[i].r;r++) cal(r+1);
for (;r>q[i].r;r--) cal(r);
for (;l<q[i].l;l++) cal(l);
for (;l>q[i].l;l--) cal(l-1);
ans[q[i].id]=sum;
}
For(i,1,cnt_q) printf("%d\n",ans[i]);
}[bzoj3757]苹果树——树上无修改莫队
题目大意
有一棵有$n$个节点的树，执行$m$次询问，每个点有一种颜色
每次询问$u$到$v$路径上把颜色$a$和颜色$b$当作同一种颜色后路径上不同颜色的数目
数据范围
$n\leqslant 5\times 10^4,m\leqslant 10^5$
题解
参考：https://blog.sengxian.com/algorithms/mo-s-algorithm
程序
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cctype>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define N 50500
using namespace std;
inline int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return x;
}
int n,m,block,root,et,cnt,tot,top,ans;
struct edge{int to,next;}e[2*N];
struct data{int u,v,a,b,id;}q[2*N];
int last[N],bin[25];
int dfn[N],deep[N],belong[N],st[N],fa[N][25];
int c[N],sum[N],vis[N],result[2*N];
inline bool cmp(data x,data y){
return belong[x.u]==belong[y.u]?dfn[x.v]<dfn[y.v]:belong[x.u]<belong[y.u];
}
inline void addedge(int u,int v){
e[++et]=(edge){v,last[u]};last[u]=et;
e[++et]=(edge){u,last[v]};last[v]=et;
}
inline int lca(int u,int v){
if (deep[u]<deep[v]) swap(u,v);
int t=deep[u]-deep[v];
for(int i=0;bin[i]<=t;i++)
if (t&bin[i]) u=fa[u][i];
for(int i=16;i>=0;i--)
if (fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
if (u==v) return u;
return fa[u][0];
}
int dfs(int x){
int size=0;
dfn[x]=++cnt;
For(i,1,16){
if (deep[x]>=bin[i])
fa[x][i]=fa[fa[x][i-1]][i-1];
else break;
}
goedge(i,x){
if (e[i].to==fa[x][0]) continue;
deep[e[i].to]=deep[x]+1;
fa[e[i].to][0]=x;
size+=dfs(e[i].to);
if (size>block){
tot++;
For(i,1,size) belong[st[top--]]=tot;
size=0;
}
}
st[++top]=x;
return size+1;
}
inline void reverse(int x){
if (!vis[x]) {vis[x]=1;sum[c[x]]++;if (sum[c[x]]==1) ans++;}
else {vis[x]=0;sum[c[x]]--;if (sum[c[x]]==0) ans--;}
}
inline void solve(int u,int v){
while (u!=v){
if (deep[u]>deep[v]) reverse(u),u=fa[u][0];
else reverse(v),v=fa[v][0];
}
}
int main(){
bin[0]=1;For(i,1,20) bin[i]=bin[i-1]<<1;
n=read(),m=read();
For(i,1,n) c[i]=read();
For(i,1,n){
int u=read(),v=read();
if (!u) root=v;
else if (!v) root=u;
else addedge(u,v);
}
block=sqrt(n);
dfs(root);
tot++;
while (top) belong[st[top--]]=tot;
For(i,1,m){
q[i]=(data){read(),read(),read(),read(),i};
if (dfn[q[i].u]>dfn[q[i].v]) swap(q[i].u,q[i].v);
}
sort(q+1,q+m+1,cmp);
int h=lca(q[1].u,q[1].v);
solve(q[1].u,q[1].v);
reverse(h);
result[q[1].id]=ans;
if (sum[q[1].a] && sum[q[1].b] && q[1].a!=q[1].b)
result[q[1].id]--;
reverse(h);
For(i,2,m){
solve(q[i-1].u,q[i].u);
solve(q[i-1].v,q[i].v);
int h=lca(q[i].u,q[i].v);
reverse(h);
result[q[i].id]=ans;
if (sum[q[i].a] && sum[q[i].b] && q[i].a!=q[i].b)
result[q[i].id]--;
reverse(h);
}
For(i,1,m) printf("%d\n",result[i]);
return 0;
}
鄂公网安备 42010202000505 号