莫队的应用

Posted on | In , ,

参考博客

本文总结一下莫队算法这种神奇的分块算法的一些常用技巧。

离线不修改的序列上的莫队

题目情景

在序列上有若干次询问，询问的东西一般可以快速做单点修改或者维护答案。询问时询问区间的答案。

做法

莫队是一种优美的暴力。
首先对所有询问分块，每个块大小，一共块，按照询问的右端点找大块，同一块内部的询问根据左端点排序，在两个询问间转移的时候直接暴力转移更新答案。

复杂度

对于右端点，每一个块里面$R$是乱序的，移动最多是的，所以总共是。
对于左端点，同一个块里面是有序的。最多往回走次，所以复杂度也是的。

小Z的袜子

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
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
typedef long long ll;
ll sum[N];
int n;
/*
int lowbit(int x)
{
	return x & (-x);
}

void update(int x, ll val)
{
	while (x <= n)
	{
		sum[x] += val;
		x += lowbit(x);
	}
}
ll get_sum(int x)
{
	ll ans = 0;
	while (x)
	{
		ans += sum[x];
		x -= lowbit(x);
	}
	return ans;
}
*/
int sqr;
struct query
{
	int id, bel, l, r;
	ll ans;
	bool operator < (const query& x) const
	{
		if (bel == x.bel)
			return r < x.r;
		return bel < x.bel;
	}
}q[N];
int m;
int a[N], cnt[N];
ll ans = 0;

bool cmp (query a, query b)
{
	return a.id < b.id;
}

int main()
{
	scanf("%d%d", &n, &m);
	sqr = (int)sqrt(m * 1.0);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i, q[i].bel = q[i].l / sqr;
	}
	sort(q + 1, q + 1 + m);
	int cl = 1, cr = 0;
	for (int i = 1; i <= m; i++)
	{
		while (cr < q[i].r)
		{
			cr++;
			ans += cnt[a[cr]];
			cnt[a[cr]]++;
		}
		while (cr > q[i].r)
		{
			cnt[a[cr]]--;
			ans -= cnt[a[cr]];
			cr--;
		}
		while (cl < q[i].l)
		{
			cnt[a[cl]]--;
			ans -= cnt[a[cl]];
			cl++;
		}
		while (cl > q[i].l)
		{
			cl--;
			ans += cnt[a[cl]];
			cnt[a[cl]]++;
		}
		q[i].ans = ans;
	}
	sort(q + 1, q + m + 1, cmp);
	for (int i = 1; i <= m; i++)
	{
		ll len = q[i].r - q[i].l + 1;
		ll home = len * (len - 1) / 2;
		ll gg = __gcd(q[i].ans, home);
		printf("%lld/%lld\n", q[i].ans / gg, home / gg);
	}
	return 0;
}

离线带修改的莫队

题目情景

和之前的莫队不一样，我们现在要求有修改。

做法

同样还是分块之后暴力，这一次，排序的方式是：以为一块，一共将序列分为块。排序第一关键字是左端点所在块编号，第二关键字是右端点所在块编号，第三关键字是时间（其实这个好像无所谓，因为修改和查询是单独存储的，而查询之间互不影响。
每次回答询问时，先从上一个询问的时间“穿越”到当前询问的时间：如果当前询问的时间更靠后，则顺序执行所有修改，直到达到当前询问时间；如果当前询问的时间更靠前，则“时光倒流”，还原所有多余的修改。进行推移时间的操作时，如果涉及到当前区间内的位置的修改，要对答案进行相应的维护。

复杂度

复杂度不太会证明，参考一下上面的博客链接。

2019牛客多校Game

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int MXN = 1e5 + 5;
const int MXE = 3e6 + 6;
int n, m;
ll ANS[MXN], ans;
int bel[MXN];
struct lp {
    int l, r, id, tim;
}cw[MXN];
struct lh {
    int x, oldx, newx;
}tim[MXN];
int vis[MXE], ar[MXN], res[MXN], ret[MXN];
ll L, R;
bool cmp(const lp&a, const lp&b) {
    if(bel[a.l] != bel[b.l]) return a.l < b.l;
    if(bel[a.r] != bel[b.r]) {
        if(bel[a.l] & 1) return a.r < b.r;
        return a.r > b.r;
    }
    return a.tim < b.tim;
}
inline void up(int p) {
    ++ vis[res[p]];
    ans += vis[res[p]] - 1;
}
inline void down(int p) {
    -- vis[res[p]];
    ans -= vis[res[p]];
}
inline void upT(int t) {
    res[tim[t].x] = tim[t].newx;
    if(L <= tim[t].x && tim[t].x <= R) {
        ++ vis[tim[t].newx];
//        debug(tim[t].oldx, tim[t].newx)
        ans += vis[tim[t].newx] - 1;
        -- vis[tim[t].oldx];
        ans -= vis[tim[t].oldx];
    }
}
inline void downT(int t) {
    res[tim[t].x] = tim[t].oldx;
    if(L <= tim[t].x && tim[t].x <= R) {
        -- vis[tim[t].newx];
        ans -= vis[tim[t].newx];
        ++ vis[tim[t].oldx];
        ans += vis[tim[t].oldx] - 1;
    }
}

template<class T>
void read(T& ret)
{
	ret = 0;
	char c;
	while ((c = getchar()) > '9' || c < '0');
	while (c >= '0' && c <= '9')
	{
		ret = ret * 10 + c - '0';
		c = getchar();
	}
}

template<class T>
void write(T ret)
{
	if (ret < 10)
	{
		putchar('0' + ret);
		return;
	}
	write(ret / 10);
	putchar('0' + ret % 10);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);
    //freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);
#endif
//    int Tim = read();
    while(~scanf("%d%d", &n, &m)) {
        int block = (int)pow(n, 2. / 3);//标程和10取了max，不知道为啥
        int Max = 0;
        for(int i = 1; i <= n; ++i) {
            read(ar[i]);
            bel[i] = (i-1)/block + 1;
            res[i] = res[i-1] ^ ar[i];
            ret[i] = res[i];
            Max = max(Max, max(ar[i], res[i]));
        }
        int change = 0, cnt1 = 1, cnt2 = 0;
        for(int i = 1, a; i <= m; ++i) {
            read(a);
            if(a == 1) {
                read(cw[cnt1].l), read(cw[cnt1].r);
                cw[cnt1].tim = change;
                cw[cnt1].id = cnt1;
                ++ cnt1;
            }else {
                read(tim[cnt2].x);
                tim[cnt2].oldx = res[tim[cnt2].x];
                tim[cnt2].newx = (res[tim[cnt2].x + 1] ^ ar[tim[cnt2].x]);
                res[tim[cnt2].x] = tim[cnt2].newx;
                Max = max(Max, tim[cnt2].newx);
                swap(ar[tim[cnt2].x], ar[tim[cnt2].x + 1]);
//                debug(cnt2, tim[cnt2].oldx, tim[cnt2].newx)
                ++ change; ++ cnt2;
            }
        }
        for(int i = 0; i <= Max; ++i) vis[i] = 0;
        sort(cw + 1, cw + cnt1, cmp);
        L = R = ans = 0;
        up(0);
        for(int i = 0; i <= n; ++i) res[i] = ret[i];
        for(int i = 1, t = 0, f = 1; i < cnt1; ++i) {
            while(R < cw[i].r) up(++ R);
            while(R > cw[i].r) down(R --);
            while(L < cw[i].l - 1) down(L ++);
            while(L >= cw[i].l) up(-- L);
//            for(int j = 0; j <= 7; ++j) printf("%d ", res[j]); printf("\n");
//            for(int j = 0; j <= 16; ++j) printf("%d ", vis[j]); printf("\n");
            for(;t < cw[i].tim; ++ t) upT(t);
            for(;t > cw[i].tim; -- t) downT(t-1);
//            for(int j = 0; j <= 7; ++j) printf("%d ", res[j]); printf("\n");
//            for(int j = 0; j <= 16; ++j) printf("%d ", vis[j]); printf("\n");
//            printf("*%lld %d %d %d\n", ans, L, R, cw[i].tim);
            ANS[cw[i].id] = (R - L + 1)*(R - L)/2 - ans;
        }
        for(int i = 1; i < cnt1; ++i) write(ANS[i]), putchar('\n');
    }
    return 0;
}

树上莫队

（对不起我还没学会）

0%