特辑：莫队

题目按难易度为关键字升序排列。

Problem L:小B的询问

莫队板子题，秒了

#include <bits/stdc++.h>

int n, m, k, a[50005], pos[50005], cnt[50005];
long long ans[50005], tmp;

inline int R() {
    int a = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
    return a;
}

struct Block {
    int l, r, id;
    friend bool operator <(Block a, Block b) {
        if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
        if (pos[a.l] & 1) return a.r < b.r;
        else return a.r > b.r;
    }
} ask[50005];

inline void Add(int x) {
    tmp += 2 * cnt[a[x]] + 1, ++cnt[a[x]];
}

inline void Del(int x) {
    tmp += -2 * cnt[a[x]] + 1, --cnt[a[x]];
}

signed main() {
    n = R(), m = R(), k = R();
    for (int i = 1; i <= n; i++) a[i] = R();
    int blk = pow(n, 0.55);
    for (int i = 1; i <= n; i++)
        pos[i] = (i - 1) / blk + 1;
    for (int i = 1; i <= m; i++) ask[i].l = R(), ask[i].r = R(), ask[i].id = i;
    std::sort(ask + 1, ask + 1 + m);
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
        while (l > ask[i].l) Add(--l);
        while (l < ask[i].l) Del(l++);
        while (r < ask[i].r) Add(++r);
        while (r > ask[i].r) Del(r--);
        ans[ask[i].id] = tmp;
    }
    for (int i = 1; i <= m; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

Problem M: 小Z的袜子

分母部分为选两只袜子总方案数 $ C_{R-L+1} ^ 2 $.

分子部分为每种颜色袜子选两次方案数 \(\sum C_{cnt_i}^2\).

所以答案为 \(\frac{\sum C_{cnt_i}^2}{C_{R-L+1} ^ 2} = \frac{\sum cnt_i^2 - \sum cnt_i}{(R-L+1)(R-L)}\)

转移显然了，懒得写

Add:

#include <bits/stdc++.h>
#define ll long long

const int N = 50000 + 233;
int n, m;
ll pos[N], block, cnt[N], ans[N], c[N], above[N], below[N], tmp;
bool zero[N];

struct Node {
    int l, r, id;
    friend bool operator <(Node a, Node b) {
        if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
        else if (pos[a.l] & 1) return a.r < b.r;
        else return a.r > b.r;
    }
} nd[N];

inline ll R() {
    int a = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
    return a;
}

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

inline void Add(ll x) {
    tmp += 2 * cnt[c[x]] + 1, ++cnt[c[x]];
}

inline void Del(ll x) {
    tmp -= 2 * cnt[c[x]] - 1, --cnt[c[x]];
}

void print(ll x, ll y) {
    x -= y, y = y * (y - 1);
    ll g = gcd(x, y);
    printf("%lld/%lld\n", x / g, y / g);
}

signed main() {
    n = R(), m = R();
    for (int i = 1; i <= n; i++) 
        c[i] = R();
    for (int i = 1; i <= m; i++)
        nd[i].l = R(), nd[i].r = R(), nd[i].id = i;
    block = pow(n, 0.55);
    for (int i = 1; i <= n; i++)
        pos[i] = (i - 1) / block + 1;
    std::sort(nd + 1, nd + 1 + m);
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
        int L = nd[i].l, R = nd[i].r, id = nd[i].id;
        if (L == R) {
            zero[id] = 1;
            continue;
        }
        while (l > L) Add(--l);
        while (l < L) Del(l++);
        while (r < R) Add(++r);
        while (r > R) Del(r--);
        above[id] = tmp, below[nd[i].id] = R - L + 1;
    }
    for (int i = 1; i <= m; i++) {
        if (zero[i]) puts("0/1");
        else print(above[i], below[i]);
    }
    return 0;
}

Problem K: 作业

直接莫队把每种数的出现次数和种类维护了。

难点在统计，很多人写了树状数组，其实复杂度多了个log，是不对的，放在时限小的OJ（比如Luogu）就直接凉了

正解应该对值域分块，\(O(N \sqrt N)\)解决。

如果你会CDQ分治那不是更好吗

数组开小WA了4次，丢人（

#include <bits/stdc++.h>

const int N = 2000000 + 233;
int n, m, a[N], block, pos[N], cnt[N], ans_1[N], ans_2[N], L[N], f[N], g[N];

struct Node {
    int l, r, a, b, id;
    friend bool operator <(Node a, Node b) {
        if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
        else if (pos[a.l] & 1) return a.r < b.r;
        else return a.r > b.r;
    } 
} nd[N];

inline int R() {
    int a = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
    return a;
}

inline void Add(int x) {
    f[pos[x]]++;
    if (++cnt[x] == 1) g[pos[x]]++;
}

inline void Del(int x) {
    f[pos[x]]--;
    if (--cnt[x] == 0) g[pos[x]]--;
}

inline void Ask(int x) {
    int l = nd[x].a, r = nd[x].b, id = nd[x].id;
    if (pos[r] - pos[l] < 2) {
        for (int i = l; i <= r; i++)
            if (cnt[i]) ans_1[id] += cnt[i], ans_2[id]++;
        return;
    }
    for (int i = l; i < L[pos[l] + 1]; i++)
        if (cnt[i]) ans_1[id] += cnt[i], ans_2[id]++;
    for (int i = L[pos[r]]; i <= r; i++)
        if (cnt[i]) ans_1[id] += cnt[i], ans_2[id]++;
    for (int i = pos[l] + 1; i < pos[r]; i++)
        ans_1[id] += f[i], ans_2[id] += g[i];
}

signed main() {
    n = R(), m = R();
    for (int i = 1; i <= n; i++) 
        a[i] = R();
    for (int i = 1; i <= m; i++)
        nd[i].l = R(), nd[i].r = R(), nd[i].a = R(), nd[i].b = R(), nd[i].id = i;
    block = sqrt(n);
    for (int i = 1; i <= n; i++) {
        pos[i] = (i - 1) / block + 1;
        if (pos[i] != pos[i - 1]) L[pos[i]] = i;
    }
    L[pos[n + 1] = pos[n] + 1] = n + 1;
    std::sort(nd + 1, nd + 1 + m);
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
        while (l < nd[i].l) Del(a[l++]);
        while (l > nd[i].l) Add(a[--l]);
        while (r < nd[i].r) Add(a[++r]);
        while (r > nd[i].r) Del(a[r--]);
        Ask(i);
    }
    for (int i = 1; i <= m; i++)
        printf("%d %d\n", ans_1[i], ans_2[i]);
    return 0;
}

Problem N: Permu

不会，咕着

特辑：莫队

原文：https://www.cnblogs.com/gekoo/p/11238961.html