本文介绍简单的莫队算法。

        莫队算法是一种优雅的暴力方法，由前国家队队长莫涛提出，故称莫队算法。本文只探讨基本的莫队算法。值得注意的是，莫队算法必须离线，而且最好用来处理查询问题（尽可能不修改）。
        考虑一个问题：给定一个区间，求子区间中互异数的个数。
        最暴力的方法是每一次都遍历一遍子区间，求出互异数，时间复杂度为$O(nm)$，效率很低。莫队算法就是在暴力方法的基础上改进提出的。
        对于不变的序列和m个询问，考虑离线。置两个指针指向某个区间的首末位置，对于每一个询问区间，将两个指针移动到询问区间的两端，移动过程中修改答案数据。这样在指针移动到目标位置时就得到了答案。
        很明显，这样并没有多少效率的提升。指针有可能从头指向尾，再从尾指向头，时间复杂度还是$O(nm)$，效率可能比暴力还低。这时，莫队算法的一个重要思想就体现出来了。
        首先对区间分块，分成t块。通常置每一块的长度为$\sqrt n$，这样t就大致为$\sqrt n$。当最后的序列长度不足组成一个块时，将它们视为一个。比如对于长度为10的序列，可将其分成3+3+3+1四个块。

1
2
int base = static_cast<int>(sqrt(n));
for (int i = 1; i <= n; i++)belong[i] = (i - 1) / base + 1;

        上面的代码可以来完成分块操作。belong存每一个点所处块的位置。
        接下来，对所有询问进行排序。当询问区间的左端点在同一块中时，按右端点升序排列，否则按左端点升序排列。
1
2
3
4
5
bool operator<(Node x) {
    if (belong[l] == belong[x.l])return r < x.r;
    return l < x.l;
}


        上面是结点重载<的形式。
        这样排序有什么好处？下面分析排序后指针移动次数。
        在同一块中时，左指针最大移动$\sqrt n$，右指针只能升序移动，最大移动$n$；当跨块时，左指针最大移动$2\sqrt n$，右指针仍然为$n$。这样来看，对于每一次询问，左指针平均移动$\sqrt n$次；对于每一个块，右指针移动n次，于是时间复杂度为$O((n+m)\sqrt n)$，相比$O(nm)效率得到很大提升$。
        例题：洛谷P1972。
        这道题目就是本文一开始提出的问题，值得注意的是，莫队算法在本题中可得80分左右，但思想很重要，文末介绍本题正解。
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
#include<bits/stdc++.h>

using namespace std;
int belong[500005], n, vis[1000000], op[500005], ans, m;

struct Node {
    int l, r, rk, ans;

    bool operator<(Node x) {
        if (belong[l] == belong[x.l])return r < x.r;
        return l < x.l;
    }
} node[500005];

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();//神奇的读入优化
    return s;
}

bool cmp(Node x, Node y) {
    return x.rk < y.rk;
}

inline void moveL(int &p, int to) {//移动左指针
    if (p < to) {
        do {
            vis[op[p]]--;
            if (vis[op[p]] == 0)ans--;
            p++;
        } while (p < to);
    } else if (p > to) {
        do {
            p--;
            vis[op[p]]++;
            if (vis[op[p]] == 1)ans++;
        } while (p > to);
    }
}

inline void moveR(int &p, int to) {//移动右指针
    if (p < to) {
        do {
            p++;
            vis[op[p]]++;
            if (vis[op[p]] == 1)ans++;
        } while (p < to);
    } else if (p > to) {
        do {
            vis[op[p]]--;
            if (vis[op[p]] == 0)ans--;
            p--;
        } while (p > to);
    }
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++)op[i] = read();
    int base = static_cast<int>(sqrt(n)), l = 1, r = 1;
    for (int i = 1; i <= n; i++)belong[i] = (i - 1) / base + 1;
    m = read();
    for (int i = 1; i <= m; i++)node[i].l = read(), node[i].r = read(), node[i].rk = i;
    sort(node + 1, node + m + 1);
    vis[op[1]] = 1, ans = 1;
    for (int i = 1; i <= m; i++)moveL(l, node[i].l), moveR(r, node[i].r), node[i].ans = ans;
    sort(node + 1, node + m + 1, cmp);
    for (int i = 1; i <= m; i++)cout << node[i].ans << endl;
    return 0;
}

        第二道例题：TJU某ACM冬季训练竞赛最后一题。

【排队接水】有n个小朋友需要接水，其中第i个小朋友接水需要ai分钟。
由于水龙头有限，小Hi需要知道如果为第l个到第r个小朋友分配一个水龙头，如何安排他们的接水顺序才能使得他们等待加接水的时间总和最小。
小Hi总共会有m次询问，你能帮助他解决这个问题吗？
假设3个小朋友接水的时间分别是2，3，4。如果他们依次接水，第一位小朋友等待加接水的时间是2，第二位小朋友是5，第三位小朋友是9。时间总和是16。

        贪心策略很容易知道将这些结点排序，求前缀和相加就是答案。本题用莫队算法可以比较容易地解决。一个难点是如何在指针移动时更新答案，这个过程需要维护两个树状数组。

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

using namespace std;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 3) + (s << 1) + (e & 15), e = getchar();
    return s;
}

int n, m, op[20005], belong[20005], l, r;
long long tree[20005], tree2[20005], ans;

struct Node {
    int l, r, rk;
    long long ans;

    bool operator<(Node x) {
        if (belong[l] == belong[x.l])return r < x.r;
        return l < x.l;
    }
} node[20005];

inline void add(int x, int y, long long *tr) {
    for (; x <= n; x += (x & -x))tr[x] += y;
}

inline long long sum(int x, const long long *tr) {
    long long s = 0;
    for (; x >= 1; x -= (x & -x))s += tr[x];
    return s;
}

inline void moveL(int &at, int to) {
    long long p, s = r - l + 1;
    if (at < to) {
        do {
            p = sum(op[at], tree), ans -= sum(op[at], tree2) + (s - p) * op[at];
            add(op[at], -1, tree), add(op[at], -op[at], tree2), at++, s--;
        } while (at < to);
    } else if (at > to) {
        do {
            at--, p = sum(op[at], tree), ans += (s - p) * op[at] + sum(op[at], tree2) + op[at];
            add(op[at], 1, tree), add(op[at], op[at], tree2), s++;
        } while (at > to);
    }
}

inline void moveR(int &at, int to) {
    long long p, s = r - l + 1;
    if (at < to) {
        do {
            at++, p = sum(op[at], tree), ans += (s - p) * op[at] + sum(op[at], tree2) + op[at];
            add(op[at], 1, tree), add(op[at], op[at], tree2), s++;
        } while (at < to);
    } else if (at > to) {
        do {
            p = sum(op[at], tree), ans -= sum(op[at], tree2) + (s - p) * op[at];
            add(op[at], -1, tree), add(op[at], -op[at], tree2), at--, s--;
        } while (at > to);
    }
}

bool cmp(Node x, Node y) {
    return x.rk < y.rk;
}

int main() {
    int t = read();
    while (t--) {
        n = read(), m = read();
        int base = static_cast<int>(sqrt(n));
        for (int i = 1; i <= n; i++)op[i] = read(), tree2[i] = tree[i] = 0, belong[i] = (i - 1) / base + 1;
        for (int i = 1; i <= m; i++)node[i].l = read(), node[i].r = read(), node[i].rk = i;
        sort(node + 1, node + m + 1);
        l = r = 1, ans = op[1], add(op[1], 1, tree), add(op[1], op[1], tree2);
        for (int i = 1; i <= m; i++)moveL(l, node[i].l), moveR(r, node[i].r), node[i].ans = ans;
        sort(node + 1, node + m + 1, cmp);
        for (int i = 1; i <= m; i++)cout << node[i].ans << endl;
    }
    return 0;
}

        入门经典：小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
#include<bits/stdc++.h>

using namespace std;
#define N 50005

inline int read() {
    int s = 0;
    char e = getchar();
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

long long gcd(long long x, long long y) {
    return y == 0 ? x : gcd(y, x % y);
}

long long n, m, op[N], vis[N], belong[N], ans, sum;

struct Node {
    long long l, r, ans1, ans2, rk;
} node[N];

bool cmp(Node x, Node y) {
    return x.rk < y.rk;
}

bool cmp1(Node x, Node y) {
    if (belong[x.l] == belong[y.l])return x.r < y.r;
    return x.l < y.l;
}

inline void moveL(long long &from, long long to) {
    if (from > to) {
        --from;
        while (from >= to)ans += vis[op[from]], ++vis[op[from]], --from;
    } else if (from < to) {
        while (from < to)ans -= vis[op[from]] - 1, --vis[op[from]], ++from;
    }
    from = to;
}

inline void moveR(long long &from, long long to) {
    if (from > to) {
        while (from > to)ans -= vis[op[from]] - 1, --vis[op[from]], --from;
    } else if (from < to) {
        ++from;
        while (from <= to)ans += vis[op[from]], ++vis[op[from]], ++from;
    }
    from = to;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++)op[i] = read();
    long long base = sqrt(n), l = 1, r = 1, d;
    for (int i = 1; i <= n; i++)belong[i] = (i - 1) / base + 1;
    for (int i = 1; i <= m; i++)node[i].l = read(), node[i].r = read(), node[i].rk = i;
    sort(node + 1, node + m + 1, cmp1), vis[op[1]] = 1;
    for (int i = 1; i <= m; i++) {
        if (node[i].l == node[i].r) {
            node[i].ans1 = 0, node[i].ans2 = 1;
            continue;
        }
        sum = node[i].r - node[i].l + 1, sum = static_cast<int>(1ll * sum * (sum - 1) / 2);
        moveR(r, node[i].r), moveL(l, node[i].l), d = gcd(ans, sum);
        node[i].ans1 = ans / d, node[i].ans2 = sum / d;
    }
    sort(node + 1, node + m + 1, cmp);
    for (int i = 1; i <= m; i++)printf("%lld/%lld\n", node[i].ans1, node[i].ans2);
    return 0;
}

带修莫队

        朴素莫队算法不支持修改，如果需要修改就需要带修莫队算法。模板题。
        模板题也是记录区间互异数的数目的，不过加入了单点修改。这时我们需要将查询和修改两个操作分开，并在查询中加入指标time表示这是在那一次修改后进行的查询，然后排序：

1
2
3
4
5
bool cmp1(Node x, Node y) {
    if (belong[x.l] != belong[y.l])return belong[x.l] < belong[y.l];
    if (belong[x.r] != belong[y.r])return belong[x.r] < belong[y.r];
    return x.t < y.t;
}

        容易发现先按照左端点分块处理，再按照右端点，最后考虑时间。这样引入了第三个指针：time指针，在指针移动时需要移动time指针，更新答案。下面是时间复杂度分析。
        假设一个块的大小是base，一共有m次修改，s次询问。左端点在一个块中时，左指针移动距离不大于base，右指针一直向右移，移动n次（n为序列长度），但对于时间指针的移动，最坏可能移动m次。这样总移动次数为$O(s*base+(\frac {n} {base})^2m+\frac {n^2} {base}+s*base)$，在$base=n^{\frac {2} {3}}$时可以达到$O(n^{\frac {5} {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
#include<bits/stdc++.h>

#define N 50005
using namespace std;

int op[N], vis[1000005], tmp[N], belong[N];
struct Node {
    int l, r, t, rk, ans;
} node[N];
struct Change {
    int pos, from, to;
} change[N];
int n, m, m1, m2, l, r, ans, t;

bool cmp1(Node x, Node y) {
    if (belong[x.l] != belong[y.l])return belong[x.l] < belong[y.l];
    if (belong[x.r] != belong[y.r])return belong[x.r] < belong[y.r];
    return x.t < y.t;
}

bool cmp2(Node x, Node y) {
    return x.rk < y.rk;
}

inline void moveT(int &from, int to) {//移动时间指针
    if (from > to) {
        while (from > to) {
            op[change[from].pos] = change[from].from;
            if (l <= change[from].pos && r >= change[from].pos) {
                --vis[change[from].to], ++vis[change[from].from];
                if (vis[change[from].to] == 0)--ans;
                if (vis[change[from].from] == 1)++ans;
            }
            --from;
        }
    } else if (from < to) {
        ++from;
        while (from <= to) {
            op[change[from].pos] = change[from].to;
            if (l <= change[from].pos && r >= change[from].pos) {
                ++vis[change[from].to], --vis[change[from].from];
                if (vis[change[from].to] == 1)++ans;
                if (vis[change[from].from] == 0)--ans;
            }
            ++from;
        }
    }
    from = to;
}

inline void moveR(int &from, int to) {//移动右指针
    if (from < to) {
        ++from;
        while (from <= to) {
            if (vis[op[from]] == 0)++ans;
            ++vis[op[from]], ++from;
        }
    } else if (from > to) {
        while (from > to) {
            if (vis[op[from]] == 1)--ans;
            --vis[op[from]], --from;
        }
    }
    from = to;
}

inline void moveL(int &from, int to) {//移动左指针
    if (from < to) {
        while (from < to) {
            if (vis[op[from]] == 1)--ans;
            --vis[op[from]], ++from;
        }
    } else if (from > to) {
        --from;
        while (from >= to) {
            if (vis[op[from]] == 0)++ans;
            ++vis[op[from]], --from;
        }
    }
    from = to;
}

int main() {
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= n; i++)scanf("%d", op + i), tmp[i] = op[i];
    for (register int i = 1; i <= m; i++) {
        register char e;
        register int l, r;
        scanf(" %c%d%d", &e, &l, &r);
        if (e == 'Q')node[++m1].l = l, node[m1].r = r, node[m1].t = m2, node[m1].rk = i;
        else if (tmp[l] != r)change[++m2].pos = l, change[m2].from = tmp[l], change[m2].to = r, tmp[l] = r;
    }
    register int base = pow(n, 0.66666666);
    for (register int i = 1; i <= n; i++)belong[i] = (i - 1) / base + 1;
    sort(node + 1, node + m1 + 1, cmp1);
    l = r = 1, vis[op[1]] = 1, ans = 1;
    for (register int i = 1; i <= m1; i++)
        moveT(t, node[i].t), moveR(r, node[i].r), moveL(l, node[i].l), node[i].ans = ans;
    sort(node + 1, node + m1 + 1, cmp2);
    for (register int i = 1; i <= m1; i++)printf("%d\n", node[i].ans);
    return 0;
}

树上莫队

        树上莫队算法顾名思义就是将莫队算法搬到树上来，如果有树链剖分的基础，就可以知道其实树上路径可以化归为区间序列。如果需要统计子树上的信息，直接DFS序划分就可以将树上的问题转化为区间上的问题，直接上莫队算法即可。
        如果需要在路径上统计呢？我们很难将一条路径上的点都化到一个连续的区间中，只能另辟蹊径。这里需要引入欧拉序的概念。
        对树进行一遍DFS，进入某结点时记录一次编号，出该结点时再记录一次，这样每一个结点在遍历得到的序列中分别出现两次，这种序列称为欧拉序。若记$st[x]$表示结点x第一次出现在欧拉序中的位置，$ed[x]$表示第二次出现的位置，那么对于两个结点a、b，在欧拉序中有如下结论（假设$st[a]<st[b]$）：

  • 若a与b的lca是a，则序列$[st[a], st[b]]$中仅出现一次的结点为a到b路径上的结点。
  • 若lca不是a，则序列$[ed[a], st[b]]$中仅出现一次的结点以及lca为a到b路径上的结点。

        注意第二条中需要对lca特殊处理。
        通过欧拉序就可以将树上的问题转化为连续区间上的问题，于是就可以用莫队算法了，模板题。
        在移动指针时，需要同时记录每一个结点出现过的次数，出现过两次的结点是无效的。lca可以通过在线的倍增法或者离线的tarjan算法求解，下面代码采用前者。

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>

#define N 50005
using namespace std;

inline int read() {//读优
    char e = getchar();
    int s = 0, g = 0;
    while (e < '-')e = getchar();
    if (e == '-')g = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return g ? -s : s;
}

struct Edge {
    int to, next;
} edge[N << 1];
struct Node {
    int l, r, ans, rk, lca;
} node[100005];
int head[N], n, m, op[N], tmp[N], depth[N], grand[N][19], op2[N << 1], ct = 1, vis[N], be[N << 1];
int st[N], ed[N], num[N], ans;

bool cmp1(Node x, Node y) {
    return be[x.l] == be[y.l] ? x.r < y.r : be[x.l] < be[y.l];
}

bool cmp2(Node x, Node y) {
    return x.rk < y.rk;
}

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

void DFS(int x) {
    st[x] = ct, op2[ct++] = x;
    for (int i = head[x]; i; i = edge[i].next) {
        if (depth[edge[i].to] == 0) {
            depth[edge[i].to] = depth[x] + 1, grand[edge[i].to][0] = x;
            for (int j = 1; j <= 18; j++)grand[edge[i].to][j] = grand[grand[edge[i].to][j - 1]][j - 1];
            DFS(edge[i].to);
        }
    }
    ed[x] = ct, op2[ct++] = x;
}

inline int LCA(int x, int y) {//倍增LCA
    if (depth[x] > depth[y])swap(x, y);//认为y更深
    for (int i = 18; i >= 0; i--)if (depth[grand[y][i]] >= depth[x])y = grand[y][i];
    if (x == y)return x;
    for (int i = 18; i >= 0; i--)if (grand[x][i] != grand[y][i])x = grand[x][i], y = grand[y][i];
    return grand[x][0];
}

inline void moveR(int &from, int to) {
    if (from < to) {
        ++from;
        while (from <= to) {
            if (num[op2[from]]) {
                if (vis[op[op2[from]]] == 1)--ans;
                --vis[op[op2[from]]];
            } else {
                if (vis[op[op2[from]]] == 0)++ans;
                ++vis[op[op2[from]]];
            }
            ++num[op2[from]], ++from;
        }
    } else if (from > to) {
        while (from > to) {
            if (num[op2[from]] == 2) {
                if (vis[op[op2[from]]] == 0)++ans;
                ++vis[op[op2[from]]];
            } else if (num[op2[from]] == 1) {
                if (vis[op[op2[from]]] == 1)--ans;
                --vis[op[op2[from]]];
            }
            --num[op2[from]], --from;
        }
    }
    from = to;
}

inline void moveL(int &from, int to) {
    if (from < to) {
        while (from < to) {
            if (num[op2[from]] == 2) {
                if (vis[op[op2[from]]] == 0)++ans;
                ++vis[op[op2[from]]];
            } else if (num[op2[from]] == 1) {
                if (vis[op[op2[from]]] == 1)--ans;
                --vis[op[op2[from]]];
            }
            --num[op2[from]], ++from;
        }
    } else if (from > to) {
        --from;
        while (from >= to) {
            if (num[op2[from]]) {
                if (vis[op[op2[from]]] == 1)--ans;
                --vis[op[op2[from]]];
            } else {
                if (vis[op[op2[from]]] == 0)++ans;
                ++vis[op[op2[from]]];
            }
            ++num[op2[from]], --from;
        }
    }
    from = to;
}

map<int, int> mmp;

int main() {
    int ID = 1;
    n = read(), m = read();
    for (int i = 1; i <= n; i++)tmp[i] = op[i] = read();
    sort(tmp + 1, tmp + n + 1);
    for (int i = 1; i <= n; i++)if (mmp.count(tmp[i]) == 0)mmp[tmp[i]] = ID++;//离散化
    for (int i = 1; i <= n; i++)op[i] = mmp[op[i]];
    for (int i = 1; i < n; i++) {//建树
        int x = read(), y = read();
        add(x, y), add(y, x);
    }
    depth[1] = 1, DFS(1);//形成欧拉序并且预处理倍增LCA
    for (int i = 1; i <= m; i++) {//处理查询信息
        int a = read(), b = read(), lca = LCA(a, b);
        if (st[a] > st[b])swap(a, b);
        if (lca == a)node[i].l = st[a], node[i].r = st[b], node[i].lca = 0;//分类处理
        else node[i].l = ed[a], node[i].r = st[b], node[i].lca = lca;
        node[i].rk = i;
    }
    int base = sqrt(2.0 * n), l = 1, r = 1;
    ans = vis[op[op2[1]]] = num[op2[1]] = 1;
    for (int i = 1; i <= (n << 1); i++)be[i] = (i - 1) / base + 1;//分块
    sort(node + 1, node + m + 1, cmp1);//莫队离线处理
    for (int i = 1; i <= m; i++) {
        moveR(r, node[i].r), moveL(l, node[i].l);//莫队算法主体
        if (node[i].lca && vis[op[node[i].lca]] == 0)node[i].ans = ans + 1;//对lca特殊处理
        else node[i].ans = ans;
    }
    sort(node + 1, node + m + 1, cmp2);
    for (int i = 1; i <= m; i++)printf("%d\n", node[i].ans);
    return 0;
}

一些处理方式

        莫队算法在移动指针时可以更新答案，但是有时候必须移动完才可以更新答案。为了不TLE，我们需要在$O(\sqrt n)$的复杂度下更新完答案，这样总的时间复杂度为$O(m\sqrt n)$。
        问题链接：这里。
        每一次k都不一样，需要移动完指针再更新答案。这里我们的更新策略是：记录出现次数小于$\sqrt n$的数有多少种，而对于大于或等于$\sqrt n$的暴力计数。这样做的好处是前者数量显然不超过$\sqrt 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
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
#include<bits/stdc++.h>

#define MOD 1000000007
#define N 100005
using namespace std;

inline int read() {
    char e = getchar();
    int s = 0, g = 0;
    while (e < '-')e = getchar();
    if (e == '-')g = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return g ? -s : s;
}

struct Query {
    int l, r, k, rk;
    long long ans;
} q[N];
int n, op[N], tmp[N], m, be[N], vis[N], poi[N][101], vis2[N], base;
long long ans, ans0[N];
unordered_set<int> ssp;//集合存出现次数大于根号n的数

bool cmp1(Query a, Query b) {
    return be[a.l] != be[b.l] ? be[a.l] < be[b.l] : be[a.r] < be[b.r];
}

bool cmp2(Query a, Query b) {
    return a.rk < b.rk;
}

inline void moveR(int &from, int to) {
    if (from < to) {
        ++from;
        while (from <= to) {
            --vis2[vis[op[from]]], ++vis2[++vis[op[from]]];
            if (vis[op[from]] == base)ssp.insert(op[from]);
            ++from;
        }
    } else if (from > to) {
        while (from > to) {
            if (vis[op[from]] == base)ssp.erase(op[from]);
            --vis2[vis[op[from]]], ++vis2[--vis[op[from]]], --from;
        }
    }
    from = to;
}

inline void moveL(int &from, int to) {
    if (from < to) {
        while (from < to) {
            if (vis[op[from]] == base)ssp.erase(op[from]);
            --vis2[vis[op[from]]], ++vis2[--vis[op[from]]], ++from;
        }
    } else if (from > to) {
        --from;
        while (from >= to) {
            --vis2[vis[op[from]]], ++vis2[++vis[op[from]]];
            if (vis[op[from]] == base)ssp.insert(op[from]);
            --from;
        }
    }
    from = to;
}

int main() {
    for (register int i = 1; i <= 100000; i++) {
        poi[i][0] = 1;
        for (register int j = 1; j <= 100; j++)poi[i][j] = 1ll * poi[i][j - 1] * i % MOD;
    }
    int qt = read();
    while (qt--) {
        n = read(), m = read(), ssp.clear();
        memset(vis, 0, sizeof(vis)), memset(vis2, 0, sizeof(vis2));
        for (int i = 1; i <= n; i++)tmp[i] = op[i] = read();
        int sb;
        sort(tmp + 1, tmp + n + 1), sb = unique(tmp + 1, tmp + n + 1) - tmp - 1;
        for (int i = 1; i <= n; i++)op[i] = lower_bound(tmp + 1, tmp + sb + 1, op[i]) - tmp;
        for (register int i = 1; i <= m; i++)q[i].l = read(), q[i].r = read(), q[i].k = read(), q[i].rk = i;
        base = sqrt(n);
        for (register int i = 1; i <= n; i++)be[i] = (i - 1) / base + 1;
        sort(q + 1, q + m + 1, cmp1);
        int l = 1, r = 1;
        vis[op[1]] = 1, vis2[1] = 1;
        for (register int i = 1; i <= m; i++) {
            moveR(r, q[i].r), moveL(l, q[i].l), ans = 0;
            for (int j = 1; j < base; j++)ans = (ans + vis2[j] * 1ll * poi[j][q[i].k]) % MOD;
            for (int sp:ssp)ans = (ans + poi[vis[sp]][q[i].k]) % MOD;
            ans0[q[i].rk] = ans;
        }
        for (register int i = 1; i <= m; i++)printf("%lld\n", (ans0[i] % MOD + MOD) % MOD);
    }
    return 0;
}

        文末补充洛谷P1972正解。
        方法仍然是离线。将所有询问按右结点升序排列，用树状数组维护最右侧某个数出现的第一个位置，使该位置+1，答案就是树状数组的区间和。

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

#define N 500005
using namespace std;
int last[1000005];
int tree[N], n, m, op[N];

struct Node {
    int l, r, rk, ans;

    bool operator<(Node x) {
        return r < x.r;
    }
} node[N];

bool cmp(Node x, Node y) {
    return x.rk < y.rk;
}

inline void add(int x, int y) {
    for (int i = x; i <= n; i += (i & -i))tree[i] += y;
}

inline int sum(int x) {
    int s = 0;
    for (int i = x; i >= 1; i -= (i & -i))s += tree[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> op[i];
        last[op[i]] = -1;
    }
    cin >> m;
    for (int i = 1; i <= m; i++)cin >> node[i].l >> node[i].r, node[i].rk = i;
    sort(node + 1, node + m + 1);
    for (int i = node[1].r; i >= 1; i--)if (last[op[i]] == -1)last[op[i]] = i, add(i, 1);
    node[1].ans = sum(node[1].r) - sum(node[1].l - 1);
    for (int i = 2; i <= m; i++) {
        for (int j = node[i].r; j > node[i - 1].r; j--) {
            if (last[op[j]] == -1)last[op[j]] = j, add(j, 1);
            else if (last[op[j]] <= node[i - 1].r)add(last[op[j]], -1), last[op[j]] = j, add(j, 1);
        }
        node[i].ans = sum(node[i].r) - sum(node[i].l - 1);
    }
    sort(node + 1, node + m + 1, cmp);
    for (int i = 1; i <= m; i++)cout << node[i].ans << endl;
    return 0;
}