莫队--优雅的暴力

当遇到大量的区间询问时，假如区间的左右下标有着一定的规律，我们可以如何求解？

如：

$[1,3],[1,4],[1,5],[2,5]$。

当然是双指针！其时间复杂度从$n^2$下降到$o(n)$。

莫队就是这样一个算法，通过预处理询问顺序，来降低时间复杂度，当然，前提是能够预处理，强制在线的题目便与莫队无缘。

其预处理流程如下：

• 首先将数据分块，分块大小为size
• 将区间排序，如果区间的左端点落在同一个块中，那么我们将其按右端点大小排序。
• 如果它们的左端点不在同一块中，那么便按照左端点升序排序。

当我们处理完区间顺序之后，剩下的就是之后双指针的左右移动罢了，考虑增加和删除对与答案的影响，也就结束了。

ll sum = 0;
	s[a[1]]++;
	for (int i = 1; i <= m; i++)
	{
    
		while (l < q[i].l)sum += del(l++);
		while (l > q[i].l)sum += add(--l);
		while (r < q[i].r)sum += add(++r);
		while (r > q[i].r)sum += del(r--);
		ans[q[i].id] = sum;
	}

那么问题来了，如何分析莫队算法的时间复杂度呢？

考虑对单一块进行询问，我们考虑最糟糕的情况，同一块中的左端点再反复横跳，先是再块的最左端，然后跑到最右端如此反复，当然，右端点是有序的，它只会后移操作。那么其实时间复杂度为$o(\sqrt{size}\ast m_i+n)$，其中$m_i$表示再第i块中的区间数.

那么对于总体的时间复杂度为$o(\sqrt{size}\ast m+n\ast (\frac{n}{size}))$​。

洛谷P1494

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e4 + 5;
struct node {
    
	int l, r, id;
}q[maxn];
ll n, m, a[maxn], ans[maxn], l = 1, r = 1, sum, s[maxn], id[maxn], Size;
ll lef[maxn], righ[maxn];
bool cmp(struct node x, struct node y)
{
    
	if (id[x.l] == id[y.l])
	{
    
		if(id[x.l]&1)return x.r < y.r;
		return x.r>y.r;
	}//排序，左端点在同一块内，按右区间升序排序 ,奇数偶数优化
	return x.l < y.l;//否则，按左区间排序 
}
ll add(int x)
{
    
	ll gs = ++s[a[x]];
	return s[a[x]] * (s[a[x]] - 1) / 2 - (s[a[x]] - 1)*(s[a[x]] - 2) / 2;//返回影响
}
ll del(int x)
{
    
	ll gs = --s[a[x]];
	return gs * (gs - 1) / 2 - gs * (gs + 1) / 2;//返回影响
}
ll gcd(ll a, ll b)
{
    
	if (a == 0)return b>0?b:1;
	return b == 0 ? a : gcd(b, a%b);
}
int main()
{
    
	ios::sync_with_stdio(false);
	//freopen("P1494_1.in", "r+", stdin);
	cin >> n >> m;
	Size = n / sqrt(m * 2 / 3);//分块大小，会影响时间复杂度。
	for (int i = 1; i <= n; i++)
	{
    
		cin >> a[i];
		id[i] = (i - 1) / Size + 1;
	}
	for (int i = 1; i <= m; i++)
	{
    
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
		lef[i] = q[i].l;
		righ[i] = q[i].r;
	}
	sort(q + 1, q + m + 1, cmp);
	ll sum = 0;
	s[a[1]]++;
	for (int i = 1; i <= m; i++)
	{
    
		while (l < q[i].l)sum += del(l++);
		while (l > q[i].l)sum += add(--l);
		while (r < q[i].r)sum += add(++r);
		while (r > q[i].r)sum += del(r--);
		ans[q[i].id] = sum;
	}
	//cout << m << endl;
	for (int i = 1; i <= m; i++)
	{
    
		ll gs = righ[i] - lef[i] + 1;
		if (gs == 1) {
     cout << "0/1" << endl; continue; }
		ll g=gcd(ans[i], gs*(gs - 1) / 2);
		//cout <<i<<" "<< ans[i]<<" "<<g << endl;
		cout<<  ans[i] / g << '/' << gs * (gs - 1) / 2 / g << endl;
	}
	return 0;
}

codeforces

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+6;
#define ll long long
ll a[maxn],cnt=0,buc1[maxn],buc2[maxn],id[maxn],ans[maxn];
int Size;
struct mo
{
    
	int l,r;
	int pos;
	bool operator <(const struct mo x)const
	{
    
		if(id[l]==id[x.l])
        {
    
            if(id[l]&1)return r<x.r;
            return r>x.r;
        }
		return l<x.l;
	}
}q[maxn];
int main()
{
    
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	Size=(int)sqrt(n);
	for(int i=1;i<=n;i++)
	{
    
		//cin>>a[i];
		scanf("%lld",&a[i]);
		a[i]^=a[i-1];
		id[i]=(i-1)/Size+1;
	}
	//for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
	for(int i=1;i<=m;i++)
	{
    
		//cin>>q[i].l>>q[i].r;
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].pos=i;
	}
	sort(q+1,q+m+1);
	ll l=1,r=1,cnt=0;
	buc1[0]=1;
	buc2[a[1]]=1;
	if(a[1]==k)cnt++;
	for(int i=1;i<=m;i++)
	{
    
		//cout<<q[i].pos<<endl; 
		while(r<q[i].r)
		{
    	
			buc1[a[r]]++;buc2[a[r+1]]++;
			cnt+=buc1[a[r+1]^k];
		// if(buc1[a[r+1]^k]>0)cout<<i<<" "<<l<<" "<<r+1<<" +"<<buc1[a[r+1]^k]<<endl;
			r++;
			
		}
		while(r>q[i].r)
		{
    	
			
			cnt-=buc1[a[r]^k];
		// if(buc1[a[r]^k]>0)cout<<i<<" "<<l<<" "<<r-1<<" -"<<buc1[a[r]^k]<<endl;
			buc1[a[r-1]]--;buc2[a[r]]--;
			r--;
		}
		while(l<q[i].l)
		{
    
			cnt-=buc2[a[l-1]^k];
		// if(buc2[a[l-1]^k]>0)cout<<i<<" "<<l+1<<" "<<r<<" -"<<buc2[a[l-1]^k]<<endl;
			buc1[a[l-1]]--;buc2[a[l]]--;
			l++;
		}
		while(l>q[i].l)
		{
    	
			buc2[a[l-1]]++;
			cnt+=buc2[a[l-2]^k];
		// if(buc2[a[l-2]^k]>0)cout<<i<<" "<<l-1<<" "<<r<<" +"<<buc2[a[l-2]^k]<<endl;
			l--;
			buc1[a[l-1]]++;
		}
		ans[q[i].pos]=cnt;
	}
	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}

2021牛客国庆

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e6+6;
#define scf(x) scanf("%d",&x)
int pos[maxn],a[maxn],Size,buc[maxn],cnt,ans[maxn];
struct mo
{
    
    int l,r;
    int id;
    bool operator <(const struct mo y)const
    {
    
        if(pos[l]==pos[y.l])
        {
    
            if(pos[l]&1)return r<y.r;
            return r>y.r;                
        }
        return l<y.l;
    }
}q[maxn];
inline void add(int x)
{
    
    if(buc[a[x]]==0)cnt++;
    buc[a[x]]++;
}
inline void del(int x)
{
    
    if(buc[a[x]]==1&&x!=0)cnt--;
    buc[a[x]]--;
}
int main()
{
    
    int n,m;
    while(~scanf("%d %d",&n,&m)){
    
        Size=sqrt(n);
        cnt=0;
        for(int i=1;i<=n;i++)scf(a[i]),pos[i]=(i-1)/Size+1,buc[i]=0;
        for(int i=1;i<=n;i++)
        {
    
            if(buc[a[i]]==0)cnt++;
            buc[a[i]]++;
        }
       // cout<<cnt<<endl;
        for(int i=1;i<=m;i++)scf(q[i].l),scf(q[i].r),q[i].id=i;
        sort(q+1,q+m+1);
        int l=0,r=0;
        for(int i=1;i<=m;i++)
        {
    
            while(r<q[i].r)del(r++);
            while(r>q[i].r)add(--r);
            while(l<q[i].l)add(++l);
            while(l>q[i].l)del(l--);
            ans[q[i].id]=cnt;
        }
        for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    }
    return 0;
}

莫队进阶–带修莫队

由于需要修改，因此不能再简单的移动的左右指针，还需要增加一维的信息(时间维度)，

细节:时间指针可以往上走，也可以往下走，取巧写法，将要操作的数和操作中的数swap。

如何排序？

• l的所在块的编号
• r的所在的编号
• t

需要计算快的大小。

y总分析方法:

首先计算O(l),O(t),O;

然后理性分析一下。

y总建议$O(g3n\ast t)$, 网友建议O(g3 n^2),如果这两个都不行，那就自己算算吧。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e4+5;
const int maxs=1e6+1;
int n,m,len,mc,mq;
int w[maxn],cnt[maxs],ans[maxn];
struct Query
{
    
    int id,l,r,t;
}q[maxn];

struct Modify
{
    
    int p,c;
}c[maxn];
int get(int x)
{
    
    return x/len;
}
bool cmp(const Query& a,const Query& b)
{
    
    int al=get(a.l),ar=get(a.r);
    int bl=get(b.l),br=get(b.r);
    if(al!=bl)return al<bl;
    if(ar!=br)return ar<br;
    return a.t<b.t;
}
void add(int x,int&res)
{
    
    if(!cnt[x])res++;
    cnt[x]++;
}
void del(int x,int&res){
    
    cnt[x]--;
    if(cnt[x]==0)res--;
}
int  main()
{
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    char op[2];int a,b;
    for(int i=1;i<=m;i++)
    {
    
        scanf("%s%d%d",op,&a,&b);
        if(*op=='Q')mq++,q[mq]={
    mq,a,b,mc};
        else c[++mc]={
    a,b};
    }
    len = cbrt((double)n*max(1,mc))+1;//求开三次方，+1防止为0,max防止修改0;
    sort(q+1,q+mq+1,cmp);
    int res=0;
    for(int i=0,j=1,t=0,k=1;k<=mq;k++)
    {
    
        int id=q[k].id,l=q[k].l,r=q[k].r,tm=q[k].t;
        while(i<r)add(w[++i],res);
        while(i>r)del(w[i--],res);
        while(j<l)del(w[j++],res);
        while(j>l)add(w[--j],res);
        while(t<tm)
        {
    
            t++;
            if(c[t].p>=j&&c[t].p<=i)
            {
    
                del(w[c[t].p],res);
                add(c[t].c,res);
            }
            swap(w[c[t].p],c[t].c);
        }
        while(t>tm)
        {
    
            if(c[t].p>=j&&c[t].p<=i)
            {
    
                del(w[c[t].p],res);
                add(c[t].c,res);
            }
            swap(w[c[t].p],c[t].c);
            t--;
        }
        ans[id]=res;
    }
    for(int i=1;i<=mq;i++)printf("%d\n",ans[i]);
    return 0;
}

莫队进阶二–回滚莫队

回滚莫队应用：当我们发现莫队的插入比较容易即 o(1),但删除比较难维护时使用回滚莫队

排序同上，当l,r在同一个块中时，采用暴力算法求解

将需要维护的分为两个部分一个左部，一个右部，左边小于根号n，故左边采用暴力方法是的端点到达右端点，右边由于只会递增，故只需要维护插入操作,需要记录右部答案，在施行完左部分后可以恢复。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
vector<ll>nums;
int n,m,len;
ll w[maxn],ans[maxn],cnt[maxn];
int get(int x)
{
    
    return x/len;
}
struct Querry
{
    
    int id,l,r;
    bool operator < (Querry &x)const 
    {
    
        int il=get(l),ir=get(x.l);
        if(il!=ir)return il<ir;
        return r<x.r;
    } 
}q[maxn];
void add(int x,ll &res)		
{
    
    cnt[x]++;
    res=max(res,(ll)cnt[x]*nums[x]);
}
int main()
{
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]),nums.push_back(w[i]);
    sort(nums.begin(),nums.end());
    nums.resize(unique(nums.begin(),nums.end())-nums.begin());
    for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
    len = sqrt(n);
    for(int i=1;i<=m;i++)
    {
    
        int id,l,r;
        scanf("%d%d",&l,&r);
        q[i]={
    i,l,r};
    }
    sort(q+1,q+m+1);
    //for(int i=1;i<=m;i++)printf("find:%d\n",q[i].id);

    for(int x=1;x<=m;)
    {
    
        int y=x;
        int right=get(q[x].l)*len+len-1;
        while(y<=m&&get(q[y].l)==get(q[x].l))y++;
        //printf("%d %d %d %d\n",x,y,get(q[x].l),get(q[x].r));
        while(x<y&&q[x].r<=right)
        {
       
            ll res=0;
            int id=q[x].id,l=q[x].l,r=q[x].r;
            for(int i=l;i<=r;i++)add(w[i],res);
            ans[id]=res;
            for(int i=l;i<=r;i++)cnt[w[i]]--;
            //printf("find1:%d\n",x);
            x++;
        }
        int  i,j=0;
        i=right+1,j=right;//i从当前块的最后一个开始，j从下一个块的起点开始
        ll res=0;
        while(x<y)
        {
    
            int id=q[x].id,l=q[x].l,r=q[x].r;
            while(j<r)add(w[++j],res);
            ll temp=res;
            while(i>l)add(w[--i],res);
            ans[id]=res;
            while(i<right+1)cnt[w[i++]]--;
            res=temp;
            //printf("find2:%d\n",x);
            x++;
        }
        memset(cnt,0,sizeof cnt);
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
    return 0;

}

莫队进阶三—树上莫队

将树用dfs序，对dfs序进行遍历。

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

using namespace std;

const int N = 100010;

int n, m, len;
int w[N];
int h[N], e[N], ne[N], idx;
int depth[N], f[N][16];
int seq[N], top, first[N], last[N];
int cnt[N], st[N], ans[N];
int que[N];
struct Query
{
    
    int id, l, r, p;
}q[N];
vector<int> nums;

void add_edge(int a, int b)
{
    
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int father)
{
    
    seq[ ++ top] = u;
    first[u] = top;
    for (int i = h[u]; ~i; i = ne[i])
    {
    
        int j = e[i];
        if (j != father) dfs(j, u);
    }
    seq[ ++ top] = u;
    last[u] = top;
}

void bfs()
{
    
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    int hh = 0, tt = 0;
    que[0] = 1;
    while (hh <= tt)
    {
    
        int t = que[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
    
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
    
                depth[j] = depth[t] + 1;
                f[j][0] = t;
                for (int k = 1; k <= 15; k ++ )
                    f[j][k] = f[f[j][k - 1]][k - 1];
                que[ ++ tt] = j;
            }
        }
    }
}

int lca(int a, int b)
{
    
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[f[a][k]] >= depth[b])
            a = f[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (f[a][k] != f[b][k])
        {
    
            a = f[a][k];
            b = f[b][k];
        }
    return f[a][0];
}

int get(int x)
{
    
    return x / len;
}

bool cmp(const Query& a, const Query& b)
{
    
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}

void add(int x, int& res)
{
    
    st[x] ^= 1;
    if (st[x] == 0)
    {
    
        cnt[w[x]] -- ;
        if (!cnt[w[x]]) res -- ;
    }
    else
    {
    
        if (!cnt[w[x]]) res ++ ;
        cnt[w[x]] ++ ;
    }
}

int main()
{
    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), nums.push_back(w[i]);
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int i = 1; i <= n; i ++ )
        w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
    
        int a, b;
        scanf("%d%d", &a, &b);
        add_edge(a, b), add_edge(b, a);
    }

    dfs(1, -1);
    bfs();

    for (int i = 0; i < m; i ++ )
    {
    
        int a, b;
        scanf("%d%d", &a, &b);
        if (first[a] > first[b]) swap(a, b);
        int p = lca(a, b);
        if (a == p) q[i] = {
    i, first[a], first[b]};
        else q[i] = {
    i, last[a], first[b], p};
    }

    len = sqrt(top);
    sort(q, q + m, cmp);

    for (int i = 0, L = 1, R = 0, res = 0; i < m; i ++ )
    {
    
        int id = q[i].id, l = q[i].l, r = q[i].r, p = q[i].p;
        while (R < r) add(seq[ ++ R], res);
        while (R > r) add(seq[R -- ], res);
        while (L < l) add(seq[L ++ ], res);
        while (L > l) add(seq[ -- L], res);
        if (p) add(p, res);
        ans[id] = res;
        if (p) add(p, res);
    }

    for (int i = 0; i < m; i ++ ) printf("%d\n", ans[i]);

    return 0;
}

dfs序

记录dfs时出栈和进栈的时间，通过记录下dfs序可以将其转换为dfs序，再利用各种数据结构来进行区间操作。

dfs获得dfs序

int r[maxn],c[maxn];
void dfs(int s,int fa)
{
    
	r[s]=++dfn;
	for(aotu it: v)
	{
    
		if()
	}
	c[s]=dfn;
}

性质：

判断两点是否在同一个根->叶上，即两点的区间是否有交集。

1. 任意子树都是连续的。例如假设有个子树BEFKBEFK，在序列中对应的部分是：BEEFKKFBBEEFKKFB；子树CGHICGHI，在序列中对应的部分是：CGGHHIICCGGHHIIC。
2. 任意点对(a,b)之间的路径，可分为两种情况，首先是令lca是a、ba、b的最近公共祖先：
   1.若lcalca是a、b之一，则a、b之间的in时刻的区间或者out时刻区间就是其路径。例如AK之间的路径就对应区间ABEEFKABEEFK或者KFBCGGHHIICA。
   2.若lca另有其人，a、b之间的路径为In[a]、Out[b]之间的区间或者In[b]、Out[a]之间的区间。另外，还需额外加上lca！！！考虑EK路径，对应为EFK再加上BB。考虑EHEH之间的路径，对应为EFKKFBCGGH再加上A。