这道题还是标准的莫队……而且不带修改。
那就很简单啦！其余的莫队操作都没有变，之后对于每次指针的修改，我们相当于增加/减少一个C（x，2）的一个值，这样直接用莫队做即可……
没什么难度的题……不过以后得记住莫队的指针先后顺序啊……
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define bel(x) ((x-1) / B + 1) #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 100005; const int B = sqrt(M)-1; #define pri pair<ll,ll> #define mp make_pair #define fi first #define sc second ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct query { int l,r,id; bool operator < (const query &g) const { if(bel(l) != bel(g.l)) return l < g.l; if(bel(r) != bel(g.r)) return r < g.r; return id < g.id; } }q[M]; ll n,m,c[M],pl = 1,pr,cnt[M],res; pri ans[M]; int gcd(ll x,ll y) { return (!y) ? x : gcd(y,x%y); } ll C(ll x) { if(x <= 1) return 0; else return x * (x-1) / 2; } void add(ll x) { cnt[c[x]]++; res += C(cnt[c[x]]) - C(cnt[c[x]] - 1); } void del(ll x) { cnt[c[x]]--; res -= C(cnt[c[x]] + 1) - C(cnt[c[x]]); } int main() { n = read(),m = read(); rep(i,1,n) c[i] = read(); rep(i,1,m) q[i].l = read(),q[i].r = read(),q[i].id = i; sort(q+1,q+1+m); rep(i,1,m) { if(q[i].l == q[i].r) { ans[q[i].id].fi = 0,ans[q[i].id].sc = 1; continue; } while(pl < q[i].l) del(pl++); while(pl > q[i].l) add(--pl); while(pr > q[i].r) del(pr--); while(pr < q[i].r) add(++pr); ans[q[i].id].fi = res,ans[q[i].id].sc = C(q[i].r - q[i].l + 1); } rep(i,1,m) { ll g = gcd(ans[i].fi,ans[i].sc); ans[i].fi /= g,ans[i].sc /= g; printf("%lld/%lld ",ans[i].fi,ans[i].sc); } return 0; }