模板——杂项

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin

模板——杂项

KMP，SG 函数，二进制相关，数位 DP，对抗搜索，神秘康托展开，cout 输出流控制，三分（整数三分，实数三分），upper_bound 相关，CDQ 分治，莫队，sort + unique 离散化。

KMP

kmp[i] 即为 border。长度减去 border 为循环节。

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
#include <bits/stdc++.h>
using namespace std;

string s1, s2;
int n, m;

void solve() {
    //字符串s2是否存在于s1中，如果存在，返回匹配的位置
    cin >> s1 >> s2;
    n = s1.length();
    m = s2.length();
    int kmp[m + 5] = {};
    int x = 0;
    kmp[0] = 0;
    for (int i = 1; i < m; i++) {
        while (x != 0 && s2[i] != s2[x])x = kmp[x - 1];
        if (s2[i] == s2[x]) {
            x++;
            kmp[i] = x;
        }
    }
    int j = 0;
    int flag = 0;
    for (int i = 0; i < n; i++) {
        while (j != 0 && s1[i] != s2[j])j = kmp[j - 1];
        if (s1[i] == s2[j])j++;
        if (j == m) {
            cout << i - m + 2 << endl;//输出位置
            j = kmp[j - 1];
            flag = 1;
        }
    }
    for (int i = 0; i < m; i++) {
        cout << kmp[i] << ' ';
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

SG 函数

把一堆石子分成多堆石子：子游戏取异或和。

一堆石子被取走一些石子：前驱状态取 mex。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
//sg函数

int a[10] = {0, 1, 2, 3, 0, 1, 2, 3, 4, 5};

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    while (n--) {
        int x;
        cin >> x;
        int sgx = a[x % 10]; //打表得出的结论
        ans ^= sgx;
    }
    if (ans == 0) {
        //先手输
        cout << "Vinit";
    } else {
        cout << "Ada";
    }
    return;
}

int f[200], sg[200];

int dfs(int x) {
    //暴力递归 / 记忆dp   dfs可行的方案
    map<int, int> m;
    for (int i = 1; x - f[i] >= 0; i++) {
        //可以取走斐波那契数列个石子
        int nx = x - f[i];
        //if(sg[nx]==-1)dfs(nx);
        m[sg[nx]]++;
    }
    //求mex
    int ans = 0;
    while (m[ans] > 0)
        ans++;
    //sg[x]=ans;
    return ans;
}

signed main() {
    //打表找规律，状态0一定是0（nim游戏）
    f[0] = 0, f[1] = 1; //斐波那契数列
    for (int i = 2; i <= 140; i++)
        f[i] = f[i - 1] + f[i - 2];
    cout << 0 << ' ';
    for (int i = 1; i <= 100; i++) {
        sg[i] = dfs(i);
        cout << sg[i] << ' ';
    }
    //得出sg循环节是0123012345
    int t;
    //    cin >> t;
    t = 1;
    while (t--) {
        solve();
        cout << endl;
    }
    return 0;
}

二进制相关

  • 用数表示集合。数的二进制的第 \(i\) 位的 01 状态可表示一个元素是否在集合中。
  • \(\operatorname{lowbit}(x)\) 表示数 \(x\) 的最低的为 \(1\) 的一位。lowbit(x)=x&(-x)​。
  • 判断 \(x\) 是不是 \(y\) 的子集：x&y==x。
  • \(x\) 和 \(y\) 的交集 x&y，并集 x|y。
  • \(x\) 是 \(y\) 的子集时，\(y-x\)：x^y。
  • 枚举 \(S\) 的子集：for(int i=S;i;i=i-1&S)，其中 \(i\) 是 \(S\) 的子集，复杂度是 \(O(2^k)\)。枚举（全集的）子集的子集的复杂度为 \(O(3^n)\)。
  • 判断 \(s\) 从右边数第 \(i\) 位是否为 \(1\)：s&(1<<(i-1))。
  • 把 \(s\) 从右边数第 \(i\) 位变成 \(1\)：s|(1<<(i-1))。
  • 位运算运算律：
    • \((a \mid b) \mathbin{\&} c = (a \mathbin{\&} c) \mid (b \mathbin{\&} c)，(a \mathbin{\&} b) \mid c = (a \mid c) \mathbin{\&} (b \mid c)\)（与或互相分配）
    • \((a \oplus b) \mathbin{\&} c = (a \mathbin{\&} c) \oplus (b \mathbin{\&} c)\)
    • \(\sim(a \mathbin{\&} b) = (\sim a) \mid (\sim b)，\sim(a \mid b) = (\sim a) \mathbin{\&} (\sim b)\)（德摩根律）
    • \(a \mathbin{\&} (a \mid b) = a，a \mid (a \mathbin{\&} b) = a\)（吸收律）
    • \(a + b = a \oplus b + 2(a \mathbin{\&} b)\) 这本质上是把加法拆成“无进位和（XOR）”与“进位（AND 并左移）”两部分。

数位 DP

合法号码是不含前导零的 \(11\) 位的数字，要出现至少 \(3\) 个相邻的相同数字；号码中不能同时出现 \(8\) 和 \(4\)。

给定 \(l\) 和 \(r\)（不含前导零， \(11\) 位），求 \([l,r]\) 区间的合法号码数量。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l, r, num[20], dp[20][20][20][2][2][2][2];
//各维意义: 第几位 上一位数字 上两位数字 连过? <n? 4? 8?
ll dfs(int step, int pr1, int pr2, bool lkd, bool stn, bool ap4, bool ap8) {
    ll ans = 0, limit;
    if (ap4 && ap8)
        return 0; //不能同时出现 4 和 8
    if (step <= 0)
        return lkd; //搜索到头，返回这个数是否合法。本句相当于同时判断两个条件。实际上，只有这个和前面的那一句条件满足，答案才合法。
    if (dp[step][pr1][pr2][lkd][stn][ap4][ap8])
        return dp[step][pr1][pr2][lkd][stn][ap4][ap8]; //记忆化
    if (stn)
        limit = 9;
    else
        limit = num[step]; //保证枚举的数字<=n
    for (ll i = 0; i <= limit; i++) //枚举算符
        ans += dfs(step - 1, i, pr1,
                   lkd || (pr1 == pr2 && pr1 == i), 
                   stn || (i < num[step]),
                   ap4 || i == 4,
                   ap8 || i == 8);
    return dp[step][pr1][pr2][lkd][stn][ap4][ap8] = ans;
}

ll solve(ll x) {
    ll len = 0, ans = 0;
    if (x < 10000000000)
        return 0;
    memset(dp, 0, sizeof(dp));
    memset(num, 0, sizeof(num));
    while (x)
        num[++len] = x % 10, x /= 10;
    for (ll i = 1; i <= num[len]; i++) //从高位
        ans += dfs(10, i, 0, 0, i < num[len], i == 4, i == 8);
    return ans;
}

int main() {
    scanf("%lld%lld", &l, &r);
    printf("%lld", solve(r) - solve(l - 1));
    return 0;
}

对抗搜索

一个 \(n\times n\)（\(n\ge 2\)）棋盘上有黑白棋子各一枚。游戏者 A 和 B 轮流移动棋子，A 先走。

  • A 的移动规则：只能移动白棋子。可以往上下左右四个方向之一移动一格。
  • B 的移动规则：只能移动黑棋子。可以往上下左右四个方向之一移动一格或者两格。

和通常的“吃子”规则一样，当某游戏者把自己的棋子移动到对方棋子所在的格子时，他就赢了。

两个游戏者都很聪明，当可以获胜时会尽快获胜，只能输掉的时候会尽量拖延时间。告诉你 \(n\) 和黑白棋子的坐标，你的任务是判断谁会赢，需要多少回合。

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
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e8;
int dp[21][21][21][21][61][2]; //距离黑棋吃掉白棋还剩多少步
int a[8] = {-1, 0, 1, 0, -2, 0, 2, 0}; //模拟x轴移动
int b[8] = {0, 1, 0, -1, 0, 2, 0, -2}; //模拟y轴移动
int n, x, y, X, Y;
int dfs(int x1, int y1, int x2, int y2, int step, int op) //op=1轮到黑,op=0轮到白 
{
    if (step > 3 * n)
        return inf;
    if (x1 == x2 && y1 == y2)
        return op * inf;
    //当 op=1 时，说明上一轮白棋选择吃掉黑棋，是不合法的，op*inf刚好赋予正无穷
    //当 op=0 时，说明上一轮黑棋选择吃掉白棋，是目标完成，op*inf刚好为赋值0
    if (dp[x1][y1][x2][y2][step][op])
        return dp[x1][y1][x2][y2][step][op]; //记忆化
    dp[x1][y1][x2][y2][step][op] = op * inf; //同理
    for (int i = 0; i < (op ? 8 : 4); ++i) {
        int xx = x1 + a[i], yy = y1 + b[i];
        if (xx < 1 || xx > n || yy < 1 || yy > n)
            continue;
        if (!op)
            dp[x1][y1][x2][y2][step][op] = 
            max(dp[x1][y1][x2][y2][step][op], dfs(x2, y2, xx, yy, step + 1, 1));
            //如果此时轮到白棋，白棋将会选择最强抵抗
        else
            dp[x1][y1][x2][y2][step][op] =
            min(dp[x1][y1][x2][y2][step][op], dfs(x2, y2, xx, yy, step + 1, 0));
            //如果此时轮到黑棋，黑棋将会选择最快胜利
    }
    return ++dp[x1][y1][x2][y2][step][op]; //移动一次 步数+1
}

int main() {
    cin >> n >> x >> y >> X >> Y;
    if (abs(x - X) + abs(y - Y) == 1)
    {
        cout << "WHITE 1";
        return 0;
    }
    cout << "BLACK " << dfs(x, y, X, Y, 0, 0);
    return 0;
}

神秘康托展开

我们的目标是把全排列转化成一个变进制数，以方便我们进行加法。对于第 \(i\) 根手指，它有 \(n−i+1\) 种选择，根据位值原理，要想让每个数对应一个全排列，就要让这一位数是 \(n−i+1\) 进制的。

那么，整个过程分为三步：

  1. 将火星数变成变进制数；
  2. 将变进制数加上 \(m\)；
  3. 将变进制数变成火星数。

我们来看一个实例： 将 \(1,4,5,2,3\) 变成变进制数：

  • 首位 1 是 5 种选择 \(\{1,2,3,4,5\}\) 的第 1 种，故变为 0（从0开始）
  • 次位 4 是 4 种选择 \(\{2,3,4,5\}\) 的第 3 种，故变为 2
  • …
  • 最后，排列 \(1,4,5,2,3\) 变成了 \((02200)\)

接下来给它加上 3 变成 \((02203)\)，并处理进位：

  • 末位是 1 进制的，进 3 得 \((02230)\)。
  • 次低位是 2 进制的，满 2 进一得 \((02310)\)。
  • 中间位是 3 进制的，满 3 进一得 \((03010)\)。
  • 次位是 4 进制的，\(3<4\)，不进位，得 \((03010)\)。

最后将 \((03010)\) 变回火星数。

  • 首位 0 表示这位应选择 \(\{1,2,3,4,5\}\) 的第 1 种，即 1
  • 次位 3 表示这位应选择 \(\{2,3,4,5\}\) 的第 4 种（1 被选过了），即 5
  • …

所以本题答案为 14523 +3= 15243。

cout 输出流控制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n = 141;
   // 1）分别以十六进制、十进制、八进制先后输出n
   cout << "1)" << hex << n << " " << dec << n << " " << oct << n << endl;
   double x = 1234567.89, y = 12.34567;
   // 2)保留5位有效数字
   cout << "2)" << setprecision(5) << x << " " << y << " " << endl;
   // 3)保留小数点后面5位
   cout << "3)" << fixed << setprecision(5) << x << " " << y << endl;
   // 4)科学计数法输出，且保留小数点后面5位
   cout << "4)" << scientific << setprecision(5) << x << " " << y << endl;
   // 5）非负数显示正号，输出宽度为12字符，宽度不足则用*填补
   cout << "5)" << showpos << fixed << setw(12) << setfill('*') << 12.1 << endl;
   // 6）非负数不显示正号，输出宽度为12字符，宽度不足则右边用填充字符填充
   cout << "6)" << noshowpos << setw(12) << left << 12.1 << endl;
   // 7）输出宽度为12字符，宽度不足则左边用填充字符填充
   cout << "7)" << setw(12) << right << 12.1 << endl;
   // 8）宽度不足时，负号和数值分列左右，中间用填充字符填充
   cout << "8)" << setw(12) << internal << -12.1 << endl;
   cout << "9)" << 12.1 << endl;

三分

三分用于单峰函数（例如二次函数）求最值等问题。

实数三分

求 calc 凹函数的最小值。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PII pair<ll, ll>
const ll mod = 1e9 + 7, N = 1e4 + 10, inf = 1e17;
const ld eps = 1e-9;

ll a[N], b[N], c[N], n;

ld calc(ld x) {
    ld ans = -inf;
    for (ll i = 1; i <= n; i++) {
        ans = max(ans, x * x * a[i] + x * b[i] + c[i]);
    }
    return ans;
}

void solve() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    ld l = 0, r = 1000;
    while (r - l > eps) {//或迭代固定次数
        ld m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
        if (calc(m1) < calc(m2)) {
            r = m2;
        } else {
            l = m1;
        }
    }
    cout << fixed << setprecision(4) << calc(l) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

整数三分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll l, r;//凸函数极大值
while(l < r) {
    ll lmid = l + (r - l) / 3;
    ll rmid = r - (r - l) / 3;
    if(calc(lmid) <= calc(rmid))	l = lmid + 1;
    else r = rmid - 1;
}
printf("%lld\n", max(calc(l), calc(r)));

ll l, r;//凹函数极小值
while(l < r) {
    ll lmid = l + (r - l) / 3;
    ll rmid = r - (r - l) / 3;
    if(calc(rmid) >= calc(lmid))	r = rmid - 1;
    else l = lmid + 1;
}
printf("%lld\n", min(calc(l), calc(r)));

upper_bound 相关

对于元素单调上升的数列：

  • lower_bound：返回第一个大于等于给定数的位置。
  • upper_bound：返回第一个大于给定数的位置。
1
2
3
4
//从小到大排列，找第一个>=
lower_bound(begin(), end(), val, less<int>());
//从大到小排列，找第一个<=
lower_bound(begin(), end(), val, greater<int>());
1
2
3
4
5
6
7
8
9
10
11
// 第一个 >= x 的索引，没有返回 -1
int first_ge(const vector<int>& a, int x) {
    auto it = lower_bound(a.begin(), a.end(), x);
    return it == a.end() ? -1 : int(it - a.begin());
}

// 最后一个 <= x 的索引，没有返回 -1
int last_le(const vector<int>& a, int x) {
    auto it = upper_bound(a.begin(), a.end(), x);
    return it == a.begin() ? -1 : int(prev(it) - a.begin());
}

CDQ 分治

CDQ 分治是一种思想，依原理与写法的不同，大致分为三类：

  • 解决和点对有关的问题。
  • 1D 动态规划的优化与转移。
  • 通过 CDQ 分治，将一些动态问题转化为静态问题。

点对

CDQ 分治解决这类问题的算法流程如下：

找到这个序列的中点 \(mid\)，将 \((1,n)\) 这个序列拆成两个序列 \((1,mid)\) 和 \((mid+1,n)\)，递归地处理包含于这两个区间的点对，设法处理跨越 \(mid\) 的点对。此时，跨越 \(mid\) 的点对相当于消除了一个限制条件，降低维护难度。

例如三维偏序，用分治消除一种偏序，再用树状数组处理二维偏序。

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
void CDQ(ll l, ll r) {
    if (l == r)
        return;

    ll mid = (l + r) >> 1;

    // 先递归左右
    CDQ(l, mid);
    CDQ(mid + 1, r);

    // 此时 e[l..mid] 和 e[mid+1..r] 都已经按 b 有序
    // 下面像归并排序一样合并，同时统计左半对右半的贡献
    ll i = l, j = mid + 1, t = l;
    ll update_i = l - 1; // 记录已经加入树状数组的左半元素位置，用于清空

    while (i <= mid && j <= r) {
        if (e[i].b <= e[j].b) {
            // 左半元素 b 更小，加入树状数组，并放入 tmp
            update(e[i].c, e[i].cnt);
            update_i = i;
            tmp[t++] = e[i++];
        } else {
            // 右半元素 b 更小，此时左半中 b <= e[j].b 的已经全部加入树状数组
            e[j].ans += query(e[j].c);
            tmp[t++] = e[j++];
        }
    }

    // 左半剩余元素直接放入 tmp，不再加入树状数组
    while (i <= mid) {
        tmp[t++] = e[i++];
    }

    // 右半剩余元素：此时所有左半元素都已经加入树状数组，直接查询
    while (j <= r) {
        e[j].ans += query(e[j].c);
        tmp[t++] = e[j++];
    }

    // 清空树状数组：只清空刚才加入过的左半元素
    for (ll p = l; p <= update_i; p++) {
        update(e[p].c, -e[p].cnt);
    }

    // 把归并结果复制回去
    for (ll p = l; p <= r; p++) {
        e[p] = tmp[p];
    }
}

动态规划

1D/1D 动态规划指的是一类特定的 DP 问题，该类题目的特征是 DP 数组是一维的，转移是 \(O(n)\) 的。如果条件良好的话，有时可以通过 CDQ 分治来把它们的时间复杂度由 \(O(n^2)\) 降至 \(O(n\log^2n)\)。

例如转移方程：\(dp_{i}=1+ \max_{j=1}^{i-1}dp_{j}[a_{j} < a_{i}][b_{j} < b_{i}]\)。

我们发现 \(dp_{j}\) 转移到 \(dp_{i}\) 这种转移关系也是一种点对间的关系，所以我们用类似 CDQ 分治处理点对关系的方式来处理它（转移也是需要先后顺序，也相当于偏序关系，变为类三维偏序问题）。

假设现在正在处理的区间是 \((l,r)\)，算法流程大致如下：

  1. 如果 \(l=r\)，说明 \(dp_{r}\) 值的 \(\max\) 部分已经被计算好了，直接令 \(dp_{r} \gets dp_{r} + 1\) 然后返回即可；
  2. 递归使用 solve(l,mid)；处理所有 \(l \leq j \leq mid\)，\(mid+1 \leq i \leq r\) 的转移关系；递归使用 solve(mid+1,r)。

动态转静态

它适用于一些「需要支持做 xxx 修改然后做 xxx 询问」的数据结构题。该类题目有两个特点：

  • 如果把询问离线，所有操作会按照时间自然地排成一个序列。
  • 每一个修改均与之后的询问操作息息相关。而这样的「修改 - 询问」关系一共会有 \(O(n^2)\) 对。

例如：修改颜色，查询区间有几种颜色。

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 2e6 + 10;
const ll ADD = 1, DEL = -1, QUE = 2;

struct Data {
    ll id, pos, type, val, ansid;
} e[N], tmp[N];

struct Opt {
    char type;
    ll x, y;
} op[N];

ll n, m, cnt = 0, a[N], ans[N], bef[N], t[N];
set<ll> col[N];

ll lb(ll x) { return x & -x; }
void update(ll x, ll v) {
    x++;
    for (; x <= N - 10; x += lb(x)) {
        t[x] += v;
    }
}
ll query(ll x) {
    ll ret = 0;
    x++;
    for (; x >= 1; x -= lb(x)) {
        ret += t[x];
    }
    return ret;
}

void CDQ(ll l, ll r) {
    if (l == r)
        return;

    ll mid = (l + r) >> 1;

    CDQ(l, mid);
    CDQ(mid + 1, r);

    // 此时 e[l..mid] 和 e[mid+1..r] 都已经按 pos 有序
    // 下面像归并排序一样合并，同时统计左半对右半的贡献
    ll i = l, j = mid + 1, t = l;
    ll update_i = l - 1; // 记录已经加入树状数组的左半元素位置，用于清空

    while (i <= mid && j <= r) {
        if (e[i].pos <= e[j].pos) {
            // 左半元素 pos 更小，加入树状数组，并放入 tmp
            if (e[i].type != QUE) {
                update(e[i].val, e[i].type);
                update_i = i;
            }
            tmp[t++] = e[i++];
        } else {
            // 右半元素 pos 更小，此时左半中 pos <= e[j].pos
            // 的已经全部加入树状数组
            if (e[j].type == QUE) {
                ans[e[j].ansid] += query(e[j].val);
            }
            tmp[t++] = e[j++];
        }
    }

    // 左半剩余元素直接放入 tmp，不再加入树状数组
    while (i <= mid) {
        tmp[t++] = e[i++];
    }

    // 右半剩余元素：此时所有左半元素都已经加入树状数组，直接查询
    while (j <= r) {
        if (e[j].type == QUE) {
            ans[e[j].ansid] += query(e[j].val);
        }
        tmp[t++] = e[j++];
    }

    // 清空树状数组：只清空刚才加入过的左半元素
    for (ll p = l; p <= update_i; p++) {
        if (e[p].type != QUE) {
            update(e[p].val, -e[p].type);
        }
    }

    // 将归并后的结果复制回 e 数组
    for (ll i = l; i <= r; i++) {
        e[i] = tmp[i];
    }
}

void solve() {
    ll index = 0, ansindex = 0;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (ll i = 1; i <= m; i++) {
        cin >> op[i].type >> op[i].x >> op[i].y;
    }

    vector<ll> vals(a + 1, a + 1 + n);
    for (ll i = 1; i <= m; i++) {
        if (op[i].type == 'R') {
            vals.push_back(op[i].y);
        }
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    auto get_id = [&](int x) {
        return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
    };
    for (int i = 1; i <= n; i++) {
        a[i] = get_id(a[i]);
    }
    for (ll i = 1; i <= m; i++) {
        if (op[i].type == 'R') {
            op[i].y = get_id(op[i].y);
        }
    }

    for (ll i = 1; i <= vals.size(); i++) {
        col[i].insert(0);
        col[i].insert(n + 1);
    }
    for (ll i = 1; i <= n; i++) {
        col[a[i]].insert(i);
    }

    ll tmp[vals.size() + 10] = {};
    for (ll i = 1; i <= n; i++) {
        bef[i] = tmp[a[i]];
        tmp[a[i]] = i;
    }

    for (ll i = 1; i <= n; i++) {
        e[++cnt] = (Data){++index, i, ADD, bef[i], ansindex};
    }
    for (ll i = 1; i <= m; i++) {
        if (op[i].type == 'Q') {
            e[++cnt] = (Data){++index, op[i].y, QUE, op[i].x - 1, ++ansindex};
            ans[ansindex] -= op[i].x - 1;
        } else {
            ll pre, nxt;
            nxt = *next(col[a[op[i].x]].find(op[i].x));
            if (nxt <= n) {
                e[++cnt] = (Data){++index, nxt, DEL, bef[nxt], ansindex};
                bef[nxt] = bef[op[i].x];
                e[++cnt] = (Data){++index, nxt, ADD, bef[nxt], ansindex};
            }
            col[a[op[i].x]].erase(op[i].x);
            e[++cnt] = (Data){++index, op[i].x, DEL, bef[op[i].x], ansindex};
            a[op[i].x] = op[i].y;
            col[a[op[i].x]].insert(op[i].x);
            pre = *prev(col[a[op[i].x]].find(op[i].x));
            nxt = *next(col[a[op[i].x]].find(op[i].x));
            bef[op[i].x] = pre;
            e[++cnt] = (Data){++index, op[i].x, ADD, bef[op[i].x], ansindex};
            if (nxt <= n) {
                e[++cnt] = (Data){++index, nxt, DEL, bef[nxt], ansindex};
                bef[nxt] = op[i].x;
                e[++cnt] = (Data){++index, nxt, ADD, bef[nxt], ansindex};
            }
        }
    }
    CDQ(1, cnt);
    for (ll i = 1; i <= ansindex; i++) {
        cout << ans[i] << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

莫队

普通莫队

对于序列上的区间询问问题（序列长度 \(n\)，询问次数 \(m\)），如果从 \([l,r]\) 的答案能够 \(O(1)\) 扩展到相邻的区间的答案，那么可以在 \(O(n\sqrt{m})\) 的复杂度内求出所有询问的答案。块长 \(S\) 取 \(\displaystyle \frac{n}{\sqrt{m}}\) 是最优的。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 5e4 + 10;

ll n, m, c[N], cnt[N], ans1[N], ans2[N], sum = 0, Unit;

struct Query {
    ll l, r, id;

    bool operator<(const Query &x) const {
        if (l / Unit != x.l / Unit)
            return l < x.l;
        if ((l / Unit) & 1)
            return r < x.r;
        return r > x.r;
    }
} q[N];


void add(ll pos) {
    sum += cnt[pos];
    cnt[pos]++;
}

void del(ll pos) {
    cnt[pos]--;
    sum -= cnt[pos];
}

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

void solve() {
    cin >> n >> m;
    Unit = n / sqrt(m);
    for (ll i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (ll i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m);
    for (ll i = 1, l = 1, r = 0; i <= m; i++) {
        if (q[i].l == q[i].r) { // 题目特判
            ans1[q[i].id] = 0, ans2[q[i].id] = 1;
            continue;
        }
        while (l > q[i].l)
            add(c[--l]);
        while (r < q[i].r)
            add(c[++r]);
        while (l < q[i].l)
            del(c[l++]);
        while (r > q[i].r)
            del(c[r--]);
        ans1[q[i].id] = sum;
        ans2[q[i].id] = (r - l + 1) * (r - l) / 2;
    }
    for (ll i = 1; i <= m; i++) {
        if (ans1[i] != 0) {
            ll g = gcd(ans1[i], ans2[i]);
            ans1[i] /= g, ans2[i] /= g;
        } else {
            ans2[i] = 1;
        }
        cout << ans1[i] << '/' << ans2[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

带修莫队

在原本 struct Query 的基础上，记录时间 t。询问和修改分开，移动当前询问区间后，再把修改的时刻暴力移动到当前询问区间的时刻。\(m\) 次询问，\(t\) 次修改，块长取 \(\dfrac{n^{2/3}t^{1/3}}{m^{1/3}}\) 时最优时间复杂度 \(O\left(n^{2/3}m^{2/3}t^{1/3}\right)\)（同阶时为 \(O\left(n^{5/3}\right)\)），实际操作中还是推荐设定 \(n^{2/3}\) 为块长。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e6 + 10;

ll n, m, c[N], cnt[N], ans[N], sum = 0, Unit;
ll qcnt = 0, mcnt = 0;
PII mod[N];

struct Query {
    ll l, r, t, id;
    bool operator<(const Query &x) const {
        if (l / Unit != x.l / Unit)
            return l < x.l;
        if (r / Unit != x.r / Unit) {
            if ((l / Unit) & 1)
                return r < x.r;
            return r > x.r;
        }
        if ((r / Unit) & 1)
            return t < x.t;
        return t > x.t;
    }
} quy[N];

void add(ll col) {
    if (cnt[col] == 0) {
        sum++;
    }
    cnt[col]++;
}

void del(ll col) {
    cnt[col]--;
    if (cnt[col] == 0) {
        sum--;
    }
}

void apply(ll t, ll l, ll r) {
    if (mod[t].first >= l && mod[t].first <= r) {
        add(mod[t].second);
        del(c[mod[t].first]);
    }
    swap(mod[t].second, c[mod[t].first]);
    // 下次遇到这个修改操作，肯定是回撤
    // 所以使用 swap，下次遇到自动做相反操作
}
void cancel(ll t, ll l, ll r) { // 这道题目 此函数与 apply 函数完全一样
    if (mod[t].first >= l && mod[t].first <= r) {
        add(mod[t].second);
        del(c[mod[t].first]);
    }
    swap(mod[t].second, c[mod[t].first]);
}

void solve() {
    cin >> n >> m;
    Unit = max(1ll, (ll)pow(n, 2.0 / 3.0));
    for (ll i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (ll i = 1; i <= m; i++) {
        char op;
        cin >> op;
        if (op == 'Q') {
            qcnt++;
            cin >> quy[qcnt].l >> quy[qcnt].r;
            quy[qcnt].id = qcnt;
            quy[qcnt].t = mcnt;
        } else {
            mcnt++;
            cin >> mod[mcnt].first >> mod[mcnt].second;
        }
    }
    sort(quy + 1, quy + 1 + qcnt);
    for (ll i = 1, l = 1, r = 0, t = 0; i <= qcnt; i++) {
        while (l > quy[i].l)
            add(c[--l]);
        while (r < quy[i].r)
            add(c[++r]);
        while (l < quy[i].l)
            del(c[l++]);
        while (r > quy[i].r)
            del(c[r--]);
        while (t < quy[i].t)
            apply(++t, l, r);
        while (t > quy[i].t)
            cancel(t--, l, r);
        ans[quy[i].id] = sum;
    }
    for (ll i = 1; i <= qcnt; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

回滚莫队

有时候 add 与 del 其一不好实现（例如查询区间内相同颜色的点的距离最大值不容易 del），采取块内右端点不断拓展，左端点每次拓展后暴力回滚的方法。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 2e5 + 39;

ll n, m, a[N], Unit;
ll lpos[N], rpos[N], ansl = 0, ansr = 0;
ll slpos[N], srpos[N];
ll ans[N];

struct Query {
    ll l, r, id;
    bool operator<(const Query &x) const {
        if (l / Unit != x.l / Unit)
            return l < x.l;
        return r < x.r;
    }
} q[N];

void solve() {
    ll index = 0;
    cin >> n;
    Unit = sqrt(n);
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<ll> vals(a + 1, a + n + 1);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (ll i = 1; i <= n; i++) {
        a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
    }
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m);
    for (ll i = 1, l = 1, r = 0, R = 0, lastBlock = -1; i <= m; i++) {
        if (q[i].l / Unit != lastBlock) { // 进入新块，清空所有维护信息
            for (ll j = 1; j <= n; j++) {
                slpos[a[j]] = lpos[a[j]] = n + 1;
                srpos[a[j]] = rpos[a[j]] = 0;
            }
            R = min(n, (q[i].l / Unit + 1) * Unit - 1);
            l = R + 1; // 把指针设定到本块末尾的位置
            r = R;
            ansl = ansr = 0;
            lastBlock = q[i].l / Unit;
        }
        if (q[i].l / Unit == q[i].r / Unit) { // 右端点与左端点位于同块，直接暴力计算答案
            for (ll j = q[i].l; j <= q[i].r; j++) {
                lpos[a[j]] = min(lpos[a[j]], j);
                rpos[a[j]] = max(rpos[a[j]], j);
                ansl = max(ansl, rpos[a[j]] - lpos[a[j]]);
            }
            ans[q[i].id] = ansl;
            ansl = 0;
            for (ll j = q[i].l; j <= q[i].r; j++) {
                lpos[a[j]] = slpos[a[j]];
                rpos[a[j]] = srpos[a[j]];
            }
            continue;
        }
        while (r < q[i].r) { // 先向右拓展答案
                             // 此时右边的影响是本块内永久的，不会被左指针回滚掉
            r++;
            slpos[a[r]] = lpos[a[r]] = min(lpos[a[r]], r);
            srpos[a[r]] = rpos[a[r]] = max(rpos[a[r]], r);
            ansr = max(ansr, rpos[a[r]] - lpos[a[r]]);
        }
        while (l > q[i].l) { // 临时向左统计答案
            l--;
            lpos[a[l]] = min(lpos[a[l]], l);
            rpos[a[l]] = max(rpos[a[l]], l);
            ansl = max(ansl, rpos[a[l]] - lpos[a[l]]);
        }
        ans[q[i].id] = max(ansl, ansr);
        ansl = 0;
        while (l <= R) { // 回滚掉左边的影响，左指针恢复到块末尾
            lpos[a[l]] = slpos[a[l]];
            rpos[a[l]] = srpos[a[l]];
            l++;
        }
    }
    for (ll i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

sort + unique 离散化

1
2
3
4
5
6
7
// 离散化：sort + unique
    vector<ll> vals(a + 1, a + n + 1);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (ll i = 1; i <= n; i++) {
        a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
    }