Description

作为一个生活散漫的人, 小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿. 终于有一天, 小 Z 再也无法忍受这恼人的找袜子过程, 于是他决定听天由命......

具体来说, 小 Z 把这 \(n\) 只袜子从 \(1\) 到 \(n\) 编号, 然后从编号 \(L\) 到 \(R\) (尽管小 Z 并不在意两只袜子是不是完整的一双, 甚至不在意两只袜子是否一左一右, 他却很在意袜子的 颜色, 毕竟穿两只不同色的袜子会很尴尬.

你的任务便是告诉小 Z, 他有多大的概率抽到两只颜色相同的袜子. 当然, 小 Z 希望这个概率 尽量高, 所以他可能会询问多个 \((L, R)\) 以方便自己选择.

Input

输入文件第一行包含两个正整数 \(n, m\).\(n\) 为袜子的数量,\(m\) 为小 Z 所提的询问的数量. 接下来一行包含 \(n\) 个正整数 \(C_i\), 其中 \(C_i\) 表示第 \(i\) 只袜子的颜色, 相同的颜色用相同的数字表示. 再接下来 \(m\) 行, 每行两个正整数 \(L, R\) 表示一个询问.

Output

包含 \(m\) 行, 对于每个询问在一行中输出分数 A/B 表示从该询问的区间 \([L, R]\) 中随机抽出两只袜子颜色相同的概率. 若该概率为 \(0\) 则输出 \(0/1\), 否则输出的 \(A/B\) 必须为最简分数.

Sample Input

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Sample Output

2/5
0/1
1/1
4/15

Data Range

30% 的数据中 \(n, m \leq 5000\); 60% 的数据中 \(n, m \leq 25000\); 100% 的数据中 \(n, m \leq 50000, 1 \leq L \lt R \leq n, C_i \leq n\).

Explanation

这道题就是莫队算法的莫涛出的 orz

记得以前写过莫队算法, 因为强行离线太 2333 了所以就不太喜欢写, 而且反正也没有几个人考...... 但是其实以前有一次 Codeforces 上面出过一道莫队的题的;

题解懒得写了, 黄学长写得还算比较清楚, 就粘过来了, 具体意思就是说, 同一个分块中 起点变化不会太大, 而终点变化比较小, 而且是单向的, 所以就直接错来错去就可以搞定了. 由于在每一块里左端点最远错 \(\sqrt{n}\), 所以总共错的距离不会超过 \(n \sqrt{n}\), 加在一起总复杂度就是 \(n \sqrt{n} + m \log m\), 是不是很玄学~

原文链接:http://hzwer.com/2782.html

如果我们已知 \([l, r]\) 的答案, 能在 \(O(1)\) 时间得到 \([l+1, r]\) 的答案以及 \([l,r-1]\) 的答案, 即可使用莫队算法. 时间复杂度为 \(O(n \sqrt{n})\). 如果只能在 \(\log n\) 的时间移动区间, 则时间复杂度是 \(O(n \sqrt{n} \cdot log n)\).

其实就是找一个数据结构支持插入、删除时维护当前答案.

这道题的话我们很容易用数组来实现, 做到 \(O(1)\) 的从 \([l, r]\) 转移到 \([l,r+1]\) 与 \([l+1,r]\).

那么莫队算法怎么做呢? 以下都是在转移为 \(O(1)\) 的基础下讨论的时间复杂度. 另外由于 \(n\) 与 \(m\) 同阶, 就统一写 \(n\).

如果已知 \([l, r]\) 的答案, 要求 \([\mathop{{l}'}, \mathop{{r}'}]\) 的答案, 我们很容易通过 \(|l - \mathop{{l}'}| + |r - \mathop{{r}'}|\) 次转移内求得.

将 \(n\) 个数分成 \(\sqrt{n}\) 块.

按区间排序, 以左端点所在块内为第一关键字, 右端点为第二关键字, 进行排序, 也就是以 \((pos[l], r)\) 排序

然后按这个排序直接暴力, 复杂度分析是这样的:

  1. \(i\) 与 \(i + 1\) 在同一块内,\(r\) 单调递增, 所以 \(r\) 是 \(O(n)\) 的. 由于有 \(\sqrt{n}\) 块, 所以这一部分时间复杂度是 \(n \sqrt{n}\).
  2. \(i\) 与 \(i + 1\) 跨越一块,\(r\) 最多变化 \(n\), 由于有 \(\sqrt{n}\) 块, 所以这一部分 时间复杂度是 \(n \sqrt{n}\)
  3. \(i\) 与 \(i + 1\) 在同一块内时 \(l\) 变化不超过 \(\sqrt{n}\), 跨越一块也不会超过 \(\sqrt{n}\), 忽略 \(\times 2\). 由于有 \(m\) 次询问 (和 \(n\) 同级), 所以时间复杂度是 \(\sqrt{n}\)

于是就是 \(O(n \sqrt{n})\) 了

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>

#define sqr(__x) ((__x)*(__x))
using namespace std;
typedef long long lli;
const int maxn = 50010;

int n, m, blk;
int C[maxn], bid[maxn];
lli sum[maxn];

struct query {
    int l, r, id;
    lli a, b; }; // a/b
bool cmp(query a, query b) {
    if (bid[a.l] == bid[b.l]) return a.r < b.r;
    return a.l < b.l; }
bool cmp_id(query a, query b) {
    return a.id < b.id; }
query q[maxn];

void update(lli& res, int pos, int val)
{
    res -= sqr(sum[C[pos]]);
    sum[C[pos]] += val;
    res += sqr(sum[C[pos]]);
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &C[i]);
    blk = sqrt(n);
    for (int i = 1; i <= n; i++)
        bid[i] = (i-1) / blk + 1;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q+1, q+m+1, cmp);
    // Processing queries according to blocks
    lli res = 0;
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
        // Shifting values
        for (; r < q[i].r; r++) update(res, r+1, 1);
        for (; r > q[i].r; r--) update(res, r, -1);
        for (; l < q[i].l; l++) update(res, l, -1);
        for (; l > q[i].l; l--) update(res, l-1, 1);
        // Defaultly zero...
        if (q[i].l == q[i].r) {
            q[i].a = 0, q[i].b = 1;
            continue;
        }
        // Otherwise a particular ratio
        q[i].a = res - (q[i].r-q[i].l+1);
        q[i].b = (lli)(q[i].r-q[i].l+1) * (q[i].r-q[i].l);
        lli gc = __gcd(q[i].a, q[i].b);
        q[i].a /= gc, q[i].b /= gc;
    }
    // Revert to original stati and output results
    sort(q+1, q+m+1, cmp_id);
    for (int i = 1; i <= m; i++)
        printf("%lld/%lld\n", q[i].a, q[i].b);
    return 0;
}