Exber's Blog

Can't go up

莫队学习笔记

发布于 2023-03-21 | 标签: 学习笔记 、 分块 | 25分钟 | 5000字数

练习题单：dead_X 的莫队题单

众所周知，莫队是一种优雅的暴力……（两根小手指瞎跳）

Part.1 基础莫队

详解

莫队主要是用来求一段区间的某种特征值的，例如一段区间内有多少种不同的元素。

经典例题

对于一段长度为 n 的数列，有 m 个询问，每次求一段区间 [l,r] 中有多少种不同的元素。

第一行输入 n,m；

接下来输入 n 个数 a[i]；

接下来 m 行，每行两个数 l[i],r[i]。

你需要输出 m 行，为每次询问的答案。

1 <= n <= 10000

1 <= m <= 100000

1 <= a[i] <= 100000

考虑最朴素的做法，每次暴力枚举来求答案。可这样的做法是 O(nm)O(nm) 的，显然会 T 飞/fad。

考虑优化，由于可以从以前询问的答案通过移动左右端点来推出当前询问的答案，所以可以这么做：

int n,m,a[10005];
int sum,cnt[100005];
......
inline void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]==1)
	{
		sum++;
	}
}

inline void del(int x)
{
	cnt[a[x]]--;
	if(cnt[a[x]]==0)
	{
		sum--;
	}
}

int main()
{
	......
	int lpos=1,rpos=0;
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		while(lpos>l) add(--lpos);
		while(rpos<r) add(++rpos);
		while(lpos<l) del(lpos++);
		while(rpos>r) del(pos--);
		printf("%d\n",sum);
	}
	return 0;
}

但是，这么做有个缺点，如果遇到这样的询问：

1 1
10000 10000
1 1
10000 10000

那这样做就无法起到优化效果了。

但是由于询问是离线的（不必处理完第 i−1i-1 次询问才能处理第 ii 次），所以我们可以按一定方法来给询问排序，排序方法便是莫队算法的核心思想。

考虑如何排序，我们可以先把整个序列分成很多长度为 n\sqrt n 的小块，因为这样做可以分摊时间复杂度，令它大致为 O(nn)O(n\sqrt n)。在排序比较函数内判断一下两次询问的左端点的块编号，如果相同那么按右端点升序排序；否则按左端点升序排序。

这样排序的代码是这样的：

struct node
{
	int l,r,id;
}que[100005];

int n,m,blo;
......
inline bool cmp(node x,node y)
{
	int xlid=(x.l-1)/blo+1,ylid=(y.l-1)/blo+1;
	if(xlid==ylid)
	{
		return x.r<y.r;
	}
	return x.l<y.l;
}
......
int main()
{
	......
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&que[i].l,&que[i].r);
		que[i].id=i;
	}
	blo=sqrt(n);
	sort(que+1,que+m+1,cmp);
	......
	return 0;
}

但是这样的排序还是能优化的。我们可以让块编号为奇数的块左端点升序排序，块编号为偶数的块左端点降序排序。这样其实相当于让右端点移动得更少，假设左端点块编号为 ii 的所有询问已经处理完了，现在开始处理左端点块编号为 i+1i+1 的块。如果按照之前的排序方法，右端点会从最大值跳到最小值。但是这样排序可以令右端点从最大值跳到最大值或从最小值跳到最小值，可以理解成下一块“接应”上一块 awa。

这样排序的代码是这样的：（大家叫它“奇偶优化排序”）

struct node
{
	int l,r,id;
}que[100005];

int n,m,blo;
......
inline bool cmp(node x,node y)
{
	int xlid=(x.l-1)/blo+1,ylid=(y.l-1)/blo+1;
	if(xlid==ylid)
	{
		return (xlid&1)?x.r<y.r:x.r>y.r;
	}
	return x.l<y.l;
}
......
int main()
{
	......
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&que[i].l,&que[i].r);
		que[i].id=i;
	}
	blo=sqrt(n);
	sort(que+1,que+m+1,cmp);
	......
	return 0;
}

至此，这道例题的莫队解法便呼之欲出了。完整代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

struct node
{
	int l,r,id;
}que[100005];

int n,m,blo,a[10005];
int sum,cnt[100005];
int ans[100005];

inline bool cmp(node x,node y)
{
	int xlid=(x.l-1)/blo+1,ylid=(y.l-1)/blo+1;
	if(xlid==ylid)
	{
		return (xlid&1)?x.r<y.r:x.r>y.r;
	}
	return x.l<y.l;
}

inline void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]==1)
	{
		sum++;
	}
}

inline void del(int x)
{
	cnt[a[x]]--;
	if(cnt[a[x]]==0)
	{
		sum--;
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&que[i].l,&que[i].r);
		que[i].id=i;
	}
	blo=sqrt(n);
	sort(que+1,que+m+1,cmp);
	int lpos=1,rpos=0;
	for(int i=1;i<=m;i++)
	{
		int l=que[i].l,r=que[i].r,id=que[i].id;
		while(lpos>l) add(--lpos);
		while(rpos<r) add(++rpos);
		while(lpos<l) del(lpos++);
		while(rpos>r) del(pos--);
		ans[id]=sum;
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}

练习题目

P3901 数列找不同

P1494 [国家集训队]小Z的袜子

CF86D Powerful array

P2709 小B的询问

P5355 [Ynoi2017] 由乃的玉米田
双倍经验

P5072 [Ynoi 2015] 盼君莫忘

Part.2 带修莫队

基础的莫队是不支持修改操作的，不过想要支持也不是不可以，只需要加上一条时间轴即可。

例题：P1903 [国家集训队]数颜色 / 维护队列

这题除了有修改操作外和普通莫队的例题差不多，所以可以直接把上一题的代码拿过来用。不过需要给询问结构体多加一个变量来存当前询问是第几次修改之后的，移动区间也要在时间轴上移动，而排序时也要根据时间轴排序。

最后值得注意的一点是，带修莫队的块长是 n2/3n^{2/3}，具体讲解可以看这一篇博客。

完整代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

#define S1 200005
#define S2 1000005

using namespace std;

struct node
{
	int l,r,gsum,id;
}que[S1];

struct change
{
	int wh,lst,nxt;
}cge[S1];

int n,m,a[S1];
int suma,sumc;
int lpos=1,rpos,preans,cgecnt,cnt[S2];
int blo;
int ans[S1];

inline bool cmp(node x,node y)
{
	int xlid=(x.l-1)/blo+1,ylid=(y.l-1)/blo+1;
	int xrid=(x.r-1)/blo+1,yrid=(y.r-1)/blo+1;
	if(xlid==ylid)
	{
		if(xrid==yrid)
		{
			return x.gsum<y.gsum;
		}
		return x.r<y.r;
	}
	return x.l<y.l;
}

inline void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]==1)
	{
		preans++;
	}
}

inline void del(int x)
{
	cnt[a[x]]--;
	if(cnt[a[x]]==0)
	{
		preans--;
	}
}

inline void upd(int type)
{
	if(type==-1)
	{
		int pt=cge[cgecnt].wh;
		if(pt>=lpos&&pt<=rpos)
		{
			del(pt);
		}
		a[pt]=cge[cgecnt].lst;
		if(pt>=lpos&&pt<=rpos)
		{
			add(pt);
		}
	}
	cgecnt+=type;
	if(type==1)
	{
		int pt=cge[cgecnt].wh;
		if(pt>=lpos&&pt<=rpos)
		{
			del(pt);
		}
		a[pt]=cge[cgecnt].nxt;
		if(pt>=lpos&&pt<=rpos)
		{
			add(pt);
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		char opt;
		scanf(" %c",&opt);
		if(opt=='Q')
		{
			int l,r;
			scanf("%d%d",&l,&r);
			suma++;
			que[suma]=(node){l,r,sumc,suma};
		}
		else
		{
			int p,x;
			scanf("%d%d",&p,&x);
			cge[++sumc]=(change){p,a[p],x};
			a[p]=x;
		}
	}
	for(int i=sumc;i>=1;i--)
	{
		a[cge[i].wh]=cge[i].lst;
	}
	blo=pow(n,0.66666);
	sort(que+1,que+suma+1,cmp);
	for(int i=1;i<=suma;i++)
	{
		int l=que[i].l,r=que[i].r,gsum=que[i].gsum,id=que[i].id;
		while(lpos<l) del(lpos++);
		while(rpos>r) del(rpos--);
		while(lpos>l) add(--lpos);
		while(rpos<r) add(++rpos);
		while(gsum>cgecnt) upd(1);
		while(gsum<cgecnt) upd(-1);
		ans[id]=preans;
	}
	for(int i=1;i<=suma;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}

练习题目

CF940F Machine Learning

Part.3 回滚莫队

顾名思义，回滚莫队就是滚来滚去的莫队。

回滚莫队主要用来处理一些方便扩区间但不方便缩区间的情况，例如下面这道题：

经典例题

AT1219 歴史の研究

如果我们还用普通莫队的思路来解这道题，add 函数还很好写，可是到了 del 函数，我们就发现很难写了。因为维护重要度最大，需要维护重要度次大；维护重要度次大，需要维护重要度第大……这就是方便扩区间但不方便缩区间的情况。

出现这种情况，我们可以排序时先按左端点块编号升序排序，对于块编号一样的情况，按右端点升序排序。这样就能保证左端点块编号相同的询问右端点只需要扩展而不需要收缩了。另外，对于左端点和右端点在同一块内的情况，直接暴力处理即可。

考虑处理连续的一段左端点块编号相同的询问。可以先把莫队区间右端点移到当前左端点所属块的右端点，左端点为右端点加一，每次扩区间的时候右端点就可以保持只往右扩了。由于左端点不一定只往左扩，所以我们需要先把右端点扩完，记录下当前的答案 lstans，再把左端点扩到适当的位置，求出当前的答案。

接下来就需要进行“回滚”操作了，具体就是先把左端点移回 R[l]+1，但不改变答案，这时，答案可以直接赋值为之前保存的 lstans，因为区间一样，答案自然也一样了。

回滚莫队的精髓就体现在“回滚”操作上了。

完整代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define S 100005

using namespace std;

struct ask
{
    int l,r,id;
}q[S];

struct node
{
    int x,id;
}temp[S];

int n,m,a[S],bullet[S];
long long pre,lst,ans[S],cnt[S],cntt[S];
int blo,who[S],L[S],R[S];

inline int read()
{
    int s=0,w=1,ch=getchar();
    while(ch<'0'||ch>'9') ch=='-'?w=-1,ch=getchar():ch=getchar();
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return s*w;
}

inline bool cmp(node &x,node &y)
{
    return x.x<y.x;
}

inline bool cmp1(node &x,node &y)
{
    return x.id<y.id;
}

inline bool cmp2(ask &x,ask &y)
{
    return (who[x.l]==who[y.l])?(x.r<y.r):(who[x.l]<who[y.l]);
}

inline void add(int x)
{
    pre=max(pre,++cnt[a[x]]*bullet[a[x]]);
}

inline void del(int x)
{
    --cnt[a[x]];
}

int main()
{
    n=read();
    m=read();
    blo=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        temp[i].x=read();
        temp[i].id=i;
        who[i]=(i-1)/blo+1;
        L[who[i]]=(who[i]-1)*blo+1;
        R[who[i]]=min(who[i]*blo,n);
    }
    for(int i=1;i<=m;i++)
    {
        q[i].l=read();
        q[i].r=read();
        q[i].id=i;
    }
    sort(temp+1,temp+n+1,cmp);
    int tail=0;
    for(int i=1;i<=n;i++)
    {
        if(temp[i].x!=bullet[tail])
        {
            bullet[++tail]=temp[i].x;
        }
        temp[i].x=tail;
    }
    sort(temp+1,temp+n+1,cmp1);
    for(int i=1;i<=n;i++)
    {
        a[i]=temp[i].x;
    }
    sort(q+1,q+m+1,cmp2);
    int lpos=1,rpos=0;
    for(int i=1;i<=m;i++)
    {
        int l=q[i].l,r=q[i].r,id=q[i].id;
        lpos=R[who[l]];
        if(who[l]>who[q[i-1].l])
        {
            memset(cnt,0,sizeof(cnt));
            pre=0;
            lst=0;
            rpos=lpos-1;
        }
        if(who[l]==who[r])
        {
            long long maxx=0;
            for(int j=l;j<=r;j++)
            {
                maxx=max(maxx,++cntt[a[j]]*bullet[a[j]]);
            }
            ans[id]=maxx;
            for(int j=l;j<=r;j++)
            {
            	cntt[a[j]]=0;
            }
            continue;
        }
        while(rpos<r) add(++rpos);
        lst=pre;
        while(lpos>l) add(--lpos);
        ans[id]=pre;
        while(lpos<R[who[l]]) del(lpos++);
        pre=lst;
    }
    for(int i=1;i<=m;i++)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

同理，方便缩区间但不方便扩区间的情况回滚莫队也可以做。

经典例题

P8078 [WC2022] 秃子酋长

这道题显然莫队要维护一个有序的序列，支持插入、删除和求前驱后继。

容易发现，如果没有插入操作的话，前驱后继只要仿照双向链表删除的方法来维护就行了。所以考虑不插入的回滚莫队。

仿照不删除的回滚莫队：

首先把莫队区间设置为 [1,n][1,n]。

排序时先按左端点块编号升序排序，对于块编号一样的情况，按右端点降序排序。这样就能保证左端点块编号相同的询问右端点只需要收缩而不需要扩展了。需要注意的是，对于左端点和右端点在同一块内的情况，不需要暴力处理。

考虑处理连续的一段左端点块编号相同的询问。可以先把莫队区间右端点移到 nn，左端点为当前块的左端点，每次缩区间的时候右端点就可以保持只往左缩了。由于左端点不一定只往右边缩，所以我们需要先把右端点缩完，再把左端点缩到适当的位置，求出当前的答案。

和不删除的回滚莫队不一样的是，缩左端点和右端点时要把一路上更改的前驱后继用栈记录下来，这样执行“回滚”操作时就能成功恢复了，处理下一个块时右端点也能顺利恢复到 nn。

求出当前答案后就需要进行“回滚”操作了，具体就是按照栈中的值来更新答案并且扩展左端点。

注意要特判没有前驱或者后继的节点，然后就是要开 long long。

完整代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

const long long MS=500005;

struct pr
{
	int x,y;
}b[MS];

struct tr
{
	int x,y,z;
}sta[MS];

struct node
{
	int l,r,id;
}que[MS];

int n,m,blo;
int L[MS],a[MS];
int fir[MS],nxt[MS];
long long preans,ans[MS];
int top;

inline bool cmp(node x,node y)
{
	int xid=(x.l-1)/blo+1,yid=(y.l-1)/blo+1;
	return xid!=yid?x.l<y.l:x.r>y.r;
}

inline bool cmp2(pr x,pr y)
{
	return x.x<y.x;
}

inline void del(int x)
{
	int lb=fir[x],rb=nxt[x];
	sta[++top]=(tr){lb,x,rb};
	nxt[lb]=rb;
	if(rb==x)
	{
		nxt[lb]=lb;
	}
	fir[rb]=lb;
	if(lb==x)
	{
		fir[rb]=rb;
	}
	preans-=abs(x-lb)+abs(x-rb);
	if(lb!=x&&rb!=x)
	{
		preans+=abs(lb-rb);
	}
}

inline void bak()
{
	int lb=sta[top].x,x=sta[top].y,rb=sta[top].z;
	top--;
	fir[x]=lb;
	if(lb!=x)
	{
		nxt[lb]=x;
	}
	nxt[x]=rb;
	if(rb!=x)
	{
		fir[rb]=x;
	}
	if(lb!=x&&rb!=x)
	{
		preans-=abs(lb-rb);
	}
	preans+=abs(x-lb)+abs(x-rb);
}

int main()
{
	scanf("%d%d",&n,&m);
	blo=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i].x=a[i];
		b[i].y=i;
		L[i]=(i-1)/blo!=(i-2)/blo||i==1?i:L[i-1];
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&que[i].l,&que[i].r);
		que[i].id=i;
	}
	sort(que+1,que+m+1,cmp);
	int lpos=1,rpos=n;
	sort(b+1,b+n+1,cmp2);
	fir[b[1].y]=b[1].y;
	nxt[b[n].y]=b[n].y;
	for(int i=2;i<=n-1;i++)
	{
		fir[b[i].y]=b[i-1].y;
		nxt[b[i-1].y]=b[i].y;
		nxt[b[i].y]=b[i+1].y;
		fir[b[i+1].y]=b[i].y;
		preans+=abs(b[i].y-b[i-1].y);
	}
	preans+=abs(b[n].y-b[n-1].y);
	for(int i=1;i<=m;i++)
	{
		int l=que[i].l,r=que[i].r,id=que[i].id;
		int LL=L[l],lstL=L[que[i-1].l];
		if(LL!=lstL)
		{
			while(top>0) bak();
			lpos=max(1,lstL);
			rpos=n;
			while(lpos<LL) del(lpos++);
			top=0;
		}
		while(rpos>r) del(rpos--);
		while(lpos<l) del(lpos++);
		ans[id]=preans;
		while(lpos>LL) bak(),lpos--;
	}
	for(int i=1;i<=m;i++)
	{
		printf("%lld\n",ans[i]);
	}
	return 0;
}

练习题目

P5906 【模板】回滚莫队&不删除莫队

Part.4 树上莫队

树上莫队，顾名思义，就是莫队上树了。

树上莫队主要是用来求树上两点之间最短路径的某种特征值的，例如两点的最短路径上有多少种不同的元素。

经典例题

SP10707 COT2 - Count on a tree II

首先我们考虑如何把一棵树“拍扁”。dfs 序固然可以，但它无法维护树上父子关系。这时就需要介绍一种新的把树“拍扁”的方式了——欧拉序。

欧拉序和 dfs 序基本上是一样的，但是一个点在刚访问和访问结束的时候都会加进序列里，也就是说对于一个 nn 个节点的树，它的欧拉序长度为 2n2n，每个点都会在欧拉序中出现两次。

为了下文表述方便，我们记 iniin_i 表示点 ii 在欧拉序中第一次出现的位置，outiout_i 表示点 ii 在欧拉序中最后一次出现的位置。显然，ii 的子树的欧拉序就是 [ini,outi][in_i,out_i] 这段区间所对应的欧拉序。

这样，我们就实现了“拍扁”一颗树 awa。

但这还没完，考虑如何处理询问。首先记 xx 为一组询问中 inin 较小的那个点，yy 为一组询问中 inin 较大的那个点。那么如果询问的两个点在同一棵子树内，即 lca(x,y)=xlca(x,y)=x，那么需要处理的区间即为 [inx,iny][in_x,in_y]。但是由于树可能会有分叉，所以区间中出现两次的点不能算贡献。

考虑 lca(x,y)≠xlca(x,y)\ne x 的情况。对于这种情况，我们需要处理的区间便变为了 [outx,iny][out_x,in_y]。同样的，区间中出现两次的点不能算贡献。但由于没有把 lca(x,y)lca(x,y) 算进去，所以还需要算上 lca(x,y)lca(x,y) 的贡献。

这是树上莫队最难懂的地方，我也是看了好多文章才理解的 /kk。

梳理一下思路：

  • 先 dfs 一次预处理出欧拉序和倍增数组

  • 处理每一次询问，处理出询问对应的区间

  • 正常莫队处理

例题完整代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

#define S 200005
#define MS 100005

struct node
{
	int l,r,lca,id;
}que[MS];

int n,m;
int col[MS],b[MS];
int esum,to[S],nxt[S],h[MS];
int dep[MS],up[MS][30];
int cnt,a[MS],in[MS],out[MS];
int blo;
bool vis[MS];
int tot[MS],preans;
int ans[MS];

inline bool cmp(node x,node y)
{
	int xlid=(x.l-1)/blo+1,ylid=(y.l-1)/blo+1;
	if(xlid==ylid)
	{
		return (xlid&1)?x.r<y.r:x.r>y.r;
	}
	return x.l<y.l;
}

inline void added(int x,int y)
{
	to[++esum]=y;
	nxt[esum]=h[x];
	h[x]=esum;
}

void dfs(int u,int fa)
{
	a[++cnt]=u;
	in[u]=cnt;
	dep[u]=dep[fa]+1;
	up[u][0]=fa;
	for(int i=1;i<=25;i++)
	{
		up[u][i]=up[up[u][i-1]][i-1];
	}
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa)
		{
			continue;
		}
		dfs(v,u);
	}
	a[++cnt]=u;
	out[u]=cnt;
}

inline int getlca(int x,int y)
{
	if(dep[x]<dep[y])
	{
		int t=x;
		x=y;
		y=t;
	}
	for(int i=25;i>=0;i--)
	{
		if(dep[up[x][i]]>=dep[y])
		{
			x=up[x][i];
		}
	}
	if(x==y)
	{
		return x;
	}
	for(int i=25;i>=0;i--)
	{
		if(up[x][i]!=up[y][i])
		{
			x=up[x][i];
			y=up[y][i];
		}
	}
	return up[x][0];
}

inline void add(int x)
{
	if(!vis[x])
	{
		vis[x]=true;
		tot[col[x]]++;
		if(tot[col[x]]==1)
		{
			preans++;
		}
	}
	else
	{
		vis[x]=false;
		tot[col[x]]--;
		if(tot[col[x]]==0)
		{
			preans--;
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&col[i]);
		b[i]=col[i];
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
	{
		col[i]=lower_bound(b+1,b+n+1,col[i])-b;
	}
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		added(x,y);
		added(y,x);
	}
	dfs(1,0);
	blo=sqrt(n*2);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(in[x]>in[y])
		{
			int t=x;
			x=y;
			y=t;
		}
		int lca=getlca(x,y);
		if(lca==x)
		{
			que[i]=(node){in[x],in[y],0,i};
		}
		else
		{
			que[i]=(node){out[x],in[y],lca,i};
		}
	}
	sort(que+1,que+m+1,cmp);
	int lpos=1,rpos=0;
	for(int i=1;i<=m;i++)
	{
		int l=que[i].l,r=que[i].r,lca=que[i].lca,id=que[i].id;
		while(lpos>l) add(a[--lpos]);
		while(rpos<r) add(a[++rpos]);
		while(lpos<l) add(a[lpos++]);
		while(rpos>r) add(a[rpos--]);
		if(lca!=0)
		{
			add(lca);
		}
		ans[id]=preans;
		if(lca!=0)
		{
			add(lca);
		}
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}

练习题目

P4074 [WC2013] 糖果公园

小技巧

  • 莫队常配合其它数据结构，如莫队套树状数组、莫队套 bitset 等等

  • 强制在线的题莫队无法解决

  • 莫队一定要先扩区间再缩区间

# 学习笔记 # 分块
主席树（可持久化线段树）学习笔记 上一篇
数列分块学习笔记 下一篇
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea
0%