题目链接
P1494 小Z的袜子
题目分析
标准的莫队模板题。
有关莫队的知识点可以看个人笔记「ACM学习笔记：莫队算法……」
则分析这道题的具体移动操作。
对于当前状态$[l,r]$区间，记：
- $cnt[i]$为当前某颜色的出现次数，
- $ans$为当前答案（抽到两只颜色相同的袜子的情况总数）。
当扩展区间(l--,r++)时，记增加的颜色为$c$，
那么其跟当前区间$[l,r]$中，颜色相同的袜子都能配对。
也就是说，其贡献的满足情况数为$cnt[c]$，
即ans += cnt[c]。
e.g.
当前区间为$[1,6]$，袜子颜色分别为$A,A,B,B,B,C$【为了更好区分，将颜色用字母暂时代替】，
则答案$ans$为$4$。若向右扩展区间，新增加的$7$号袜子颜色为$A$，
袜子变为$A,A,B,B,B,C,A$。则其跟之前的$2$个颜色为$A$的袜子均能配对，
所以贡献答案为$cnt[A]$为$2$，$ans += 2$，
则新的$ans$等于$6$。
然后cnt[c]++。
当缩短区间(l++,r--)时，记删去的颜色为$c$，
那么其跟当前区间$[l,r]$中，颜色相同的其他袜子都不能再配对。
也就是说，其损失的满足情况数为$cnt[c]-1$，
即ans -= cnt[c] - 1。
然后cnt[c]--。
再次优化（压行），则可得出最终的两个move操作函数。
扩展函数：
inline void add(const int &color, LL &ans) { ans += cnt[color]++; }
缩短函数：
inline void dec(const int &color, LL &ans) { ans -= --cnt[color]; }
最后在重点注意一下move时：++和--的前后位置（是l++还是++l），
在草稿本上自己模拟走一遍就能知道了。
以及再注意下约分的问题，
无了。
个人代码
//P1494 [小Z的袜子](https://www.luogu.com.cn/problem/P1494)
#include <bits/stdc++.h>
#define ALL(NAME_i, BEGIN, TO) \
int NAME_i = BEGIN; \
NAME_i <= TO; \
NAME_i++
#define ALL_invert(NAME_i, BEGIN, TO) \
int NAME_i = BEGIN; \
NAME_i >= TO; \
NAME_i--
typedef long long LL;
using namespace std;
#define MAX_N 50000
#define MAX_M 50000
int color[MAX_N + 5], cnt[MAX_M + 5], BLOCK_SIZE; //cnt-当前状态各颜色出现了多少次
LL nume[MAX_M + 5], deno[MAX_M + 5]; //nume-分子，deno-分母
struct queryType
{
int l, r, id;
//bool operator<(const queryType &a) const { return l == a.l ? r < a.r : l < a.l; } //直接排序
//bool operator<(const queryType &a) const { return l / BLOCK_SIZE == a.l / BLOCK_SIZE ? r < a.r : l < a.l; } //分块排序
bool operator<(const queryType &a) const { return l / BLOCK_SIZE == a.l / BLOCK_SIZE ? (r == a.r ? 0 : (l / BLOCK_SIZE & 1) ^ (r < a.r)) : l < a.l; } //分块排序+奇偶性优化
} query[MAX_M + 5];
inline LL C(const int &n, const int &m) //组合数计算函数
{
LL ans = 1;
for (int i = n; i >= n - m + 1; i--)
ans *= i;
for (int i = 2; i <= m; i++)
ans /= i;
return ans;
}
inline LL GCD(const LL &a, const LL &b) { return b ? GCD(b, a % b) : a; }
inline int intRead()
{
int f = 1, num = 0;
char t = getchar();
while (t < '0' || t > '9')
f = t == '-' ? -1 : f, t = getchar();
while (t >= '0' && t <= '9')
num = num * 10 + t - '0', t = getchar();
return f * num;
}
inline void add(const int &color, LL &ans) { ans += cnt[color]++; } //增加某一颜色的move操作
inline void dec(const int &color, LL &ans) { ans -= --cnt[color]; } //减少某一颜色的move操作
int main()
{
int n = intRead(), m = intRead();
BLOCK_SIZE = sqrt(n);
for (ALL(i, 1, n))
color[i] = intRead();
for (ALL(i, 1, m))
query[i].l = intRead(), query[i].r = intRead(), query[i].id = i;
sort(query + 1, query + m + 1);
int now_l = 1, now_r = 0; //这里初值l=1,r=0，可以想想为什么。
LL now_nume = 0;
#define L query[i].l
#define R query[i].r
#define ID query[i].id
for (ALL(i, 1, m))
if (L == R) //L==R情况的特判
nume[ID] = 0, deno[ID] = 1;
else
{
while (now_l > L)
add(color[--now_l], now_nume);
while (now_r < R)
add(color[++now_r], now_nume);
while (now_l < L)
dec(color[now_l++], now_nume);
while (now_r > R)
dec(color[now_r--], now_nume);
//注意这里++和--的前后位置！
nume[ID] = now_nume;
if (now_nume)
{
deno[ID] = C(R - L + 1, 2);
LL gcd = GCD(nume[ID], deno[ID]);
nume[ID] /= gcd, deno[ID] /= gcd; //约分操作
}
else
deno[ID] = 1; //如果计算出ans是0，需要特判，否则求GCD会出错
}
for (ALL(i, 1, m))
printf("%lld/%lld\n", nume[i], deno[i]);
}