莫队

分析：
弄明白那个排列组合和概率就基本模板题惹

AC代码：

#include <bits/stdc++.h>using namespace std;
typedef long long ll;int n, m, len;
int ar[50050];
struct node
{ll l, r, id;
}ask[50050];
struct node1
{ll x, y;
}ans[50050], now;
int pos[50050];
ll cnt[50050];bool cmp(node a, node b)
{if(pos[a.l] == pos[b.l]){if(pos[a.l] & 1) return a.r < b.r;else return a.r > b.r;}else return pos[a.l] < pos[b.l];
}ll gcd(ll x, ll y)
{return !y ? x : gcd(y, x % y);
}void add(int x)
{++cnt[x];if(cnt[x] > 1)now.x = now.x + cnt[x] * (cnt[x] - 1) - (cnt[x] - 1) * (cnt[x] - 2);
}void del(int x)
{--cnt[x];if(cnt[x] > 0)now.x = now.x + cnt[x] * (cnt[x] - 1) - (cnt[x] + 1) * cnt[x];
}void divgcd(ll x, ll y, int id)
{if(!x) x = 0, y = 1;else{ll g = gcd(x, y);x /= g;y /= g;}ans[id].x = x;ans[id].y = y;
}int main()
{scanf("%d%d", &n, &m);len = sqrt(n + 0.5);for(int i = 1; i <= n; ++i){scanf("%d", &ar[i]);pos[i] = (i - 1) / len + 1;}for(int i = 1; i <= m; ++i){scanf("%lld%lld", &ask[i].l, &ask[i].r);ask[i].id = i;}sort(ask + 1, ask + m + 1, cmp);for(int i = ask[1].l; i <= ask[1].r; ++i) add(ar[i]);now.y = (ask[1].r - ask[1].l + 1) * (ask[1].r - ask[1].l);divgcd(now.x, now.y, ask[1].id);int l = ask[1].l, r = ask[1].r;for(int i = 2; i <= m; ++i){while(l < ask[i].l) del(ar[l++]);while(l > ask[i].l) add(ar[--l]);while(r > ask[i].r) del(ar[r--]);while(r < ask[i].r) add(ar[++r]);now.y = (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l);divgcd(now.x, now.y, ask[i].id);}for(int i = 1; i <= m; ++i) printf("%lld/%lld\n", ans[i].x, ans[i].y);return 0;
}

分析：
首先考虑普通的莫队，这个题带了修改，那么我们依旧按照莫队来做，我们需要记录一下当前这次询问经过了几次修改，然后跟上一次比较，那就跟普通莫队一样了，只是4个while要变成6个while了。这是大体方向，然后还有一点点细节
1.分块大小：sz = pow(n, 0.666);
2.排序：第一关键字是区间左界所在的块的序号，第二关键字是区间右界所在的块的序号，第三关键字是这次询问经过了几次修改，均按照从小到大排
3.对于修改，如果碰到某次修改需要操作，那么一定需要做一个交换swap(ar[qr[t].l], qr[t].r);，交换完之后，ar数组得到了修改，然后这次修改指令也得到了修改，因为后面再操作这次修改的时候就是改回来了，所以一个交换解决。另外，需要判断这次修改是不是发生在查询的区间内，是则需要做一些add和del
4.维护的容器，以及作用
cnt[i] : 数字i在当前区间出现的次数
ar[i]; 原数组在位置i应该是的值
qq[i] 表示第i次询问的左右边界已经发生在几次修改之后，id代表修改序号
qr[i] 表示第i次修改是将l位置的数字改成r

AC代码：

#include <bits/stdc++.h>using namespace std;int sum;
int cnt[1000050];
int ar[10050];
int ans[10050];
int cntq, cntr;
int n, m, sz;
char op[5];
int l, r;struct node
{int l, r, t, id;
}qq[10050], qr[10050];//两个数组分解记录每一个询问以及修改的状态inline bool cmp(const node &a, const node &b)
{if(a.l / sz == b.l / sz){if(a.r / sz == b.r / sz) return a.t < b.t;else return a.r < b.r;}else return a.l < b.l;
}inline void add(int x)
{sum += !cnt[x]++;
}inline void del(int x)
{sum -= !--cnt[x];
}inline void upd(int x, int t)//upd是对于时间上的变化所造成变化的维护
{if(qq[x].l <= qr[t].l && qr[t].l <= qq[x].r){del(ar[qr[t].l]);add(qr[t].r);}swap(ar[qr[t].l], qr[t].r);
}int main()
{scanf("%d%d", &n, &m);sz = pow(n, 0.666);for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);for(int i = 1; i <= m; ++i){scanf("%s%d%d", op, &l, &r);if(op[0] == 'Q'){++cntq;qq[cntq].id = cntq;qq[cntq].l = l;qq[cntq].r = r;qq[cntq].t = cntr;}else{++cntr;qr[cntr].l = l;qr[cntr].r = r;}}sort(qq + 1, qq + cntq + 1, cmp);int lcur = 1, rcur = 0, tcur = 0;for(int i = 1; i <= cntq; ++i){while(lcur > qq[i].l) add(ar[--lcur]);while(lcur < qq[i].l) del(ar[lcur++]);while(rcur > qq[i].r) del(ar[rcur--]);while(rcur < qq[i].r) add(ar[++rcur]);while(tcur < qq[i].t) upd(i, ++tcur);while(tcur > qq[i].t) upd(i, tcur--);//增加t轴上的移动ans[qq[i].id] = sum;}for(int i = 1; i <= cntq; ++i) printf("%d\n", ans[i]);return 0;
}