莫队--优雅的暴力

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

如：

$[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;
	}
1
2
3
4
5
6
7
8
9
10

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

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

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

洛谷P1494

#include
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 <
		cout<<  ans[i] / g << '/' << gs * (gs - 1) / 2 / g << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

codeforces

#include
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<
	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<
		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<
			r++;
			
		}
		while(r>q[i].r)
		{	
			
			cnt-=buc1[a[r]^k];
		//	if(buc1[a[r]^k]>0)cout<
			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<
			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<
			l--;
			buc1[a[l-1]]++;
		}
		ans[q[i].pos]=cnt;
	}
	for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

2021牛客国庆

#include
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<
        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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

莫队进阶–带修莫队

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

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

如何排序？

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

需要计算快的大小。

y总分析方法:

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

然后理性分析一下。

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

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

莫队进阶二–回滚莫队

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

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

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

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

莫队进阶三—树上莫队

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

#include 
#include 
#include 
#include 
#include 
#include 

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

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
2
3
4
5
6
7
8
9
10

性质：

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

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。