Mo Team - Elegant Violence

When encountering a large number of interval queries,If the left and right subscripts of the interval have certain rules,How can we solve？

如：

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

Of course double pointer！Its time complexity is from$n^2$下降到$o(n)$.

Mo team is such an algorithm,query order by preprocessing,来降低时间复杂度,当然,The premise is to be able to preprocess,The problem of forced online will be missed by Mo team.

The preprocessing process is as follows：

• 首先将数据分块,分块大小为size
• 将区间排序,If the left endpoint of the interval falls in the same block,then we sort it by right endpoint size.
• if their left endpoints are not in the same block,Then sort by left endpoint in ascending order.

After we have dealt with the interval order,All that's left is the left and right movement of the double pointer afterwards.,Consider the impact of additions and deletions on the answer,也就结束了.

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;
	}

那么问题来了,How to analyze the time complexity of Mo team's algorithm?？

Consider asking about a single block,We consider the worst case,The left endpoint in the same block jumps again and again,The leftmost end of the block first,Then run to the far right and repeat like this,当然,The right endpoint is ordered,it only moves backwards.Then the time complexity is$o(\sqrt{size}\ast m_i+n)$,其中$m_i$to say againithe number of intervals in the block.

Then the overall time complexity is$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;
	}//排序,The left endpoint is within the same block,According to the ascending order right interval ,Odd-even optimization
	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;//Back to Impact
}
ll del(int x)
{
    
	ll gs = --s[a[x]];
	return gs * (gs - 1) / 2 - gs * (gs + 1) / 2;//Back to Impact
}
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;
}

2021National Day

#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;
}

Mo team advanced–带修莫队

由于需要修改,Therefore, the left and right pointers can no longer be simply moved,One dimensional information should be added(时间维度),

细节:The time hand can go up,也可以往下走,取巧写法,The number to be operated on and the number in the operationswap.

如何排序？

• lThe number of the block where the
• rthe number of
• t

Need to calculate fast size.

yTotal Analysis Method:

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

Then analyze it rationally.

yGeneral advice$O(g3n\ast t)$, 网友建议O(g3 n^2),If neither of these work,Then do the math.

#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;//Find the cube,+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;
}

Team Mo Advanced II–回滚莫队

Roll back the Mo team application：When we found that the insertion of the Mo team was easier o(1),But when deletion is more difficult to maintain, use rollback Mo team

Sorting ditto,当l,rwhen in the same block,Solve using brute force algorithm

Divide what needs to be maintained into two parts, a left part,a right,Left is less than rootn,Therefore, the brute force method is used on the left to reach the right endpoint.,Since the right side will only increase,Therefore, only the insert operation needs to be maintained,Need to record right answer,Can be restored after performing the left part.

#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;//istart from the last of the current block,jStart at the beginning of the next block
        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;

}

Mo team advanced three—树上莫队

use the treedfs序,对dfstraverse in order.

#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序

记录dfstime to pop and push,通过记录下dfsSequence can convert them intodfs序,Reuse various data structures to perform interval operations.

dfs获得dfs序

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

性质：

Determine whether two points in the same root->叶上,If there is a intersection of two interval.

1. Any subtree is contiguous.For example, suppose there is a subtreeBEFKBEFK,The corresponding part in the sequence is：BEEFKKFBBEEFKKFB;子树CGHICGHI,The corresponding part in the sequence is：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.