莫队

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=50010;
typedef long long ll;
int n,m,ks,c[maxn];
struct node{
    int l,r,id;
    friend bool operator <(const node&A,const node&B){
      if(A.l/ks!=B.l/ks) return A.l/ks<B.l/ks;
      else return A.r<B.r;
    }
}q[maxn];
ll a[maxn],sum,fz[maxn],fm[maxn];
ll pf(int x) {return (ll)x*(ll)x;} 
void work(){
 int l=1,r=0;
 for(int i=1;i<=m;i++){
   while(r<q[i].r){
     r++;
     sum-=pf(c[a[r]]);
     c[a[r]]++;
     sum+=pf(c[a[r]]);
   }
   while(r>q[i].r){
    sum-=pf(c[a[r]]);
    c[a[r]]--;
    sum+=pf(c[a[r]]);
    r--;
   }
   while(l>q[i].l){
    l--;
    sum-=pf(c[a[l]]);
    c[a[l]]++;
    sum+=pf(c[a[l]]);
   }
   while(l<q[i].l){
    sum-=pf(c[a[l]]);
    c[a[l]]--;
    sum+=pf(c[a[l]]);
    l++;
   }
   int o=q[i].id ;
   fz[o]=sum-(r-l+1);
   fm[o]=(ll)(r-l+1)*(r-l);
 }
}
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
int main()
{
   scanf("%d%d",&n,&m);
   ks=sqrt(n); if(n%ks) ks++;
   for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
   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);
   work();
   for(int i=1;i<=m;i++){
     if(!fz[i]){
     cout<<"0/1"<<endl;
     continue;
     }
     ll g=gcd(fz[i],fm[i]);
     printf("%lld/%lld
",fz[i]/g,fm[i]/g);
   }
   return 0;
}

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=10000+29;
using namespace std;
int sum,n,m,a[maxn],c[maxn],ans[maxn],kk,tot,tt,ll,rr,now=0;
char s[5];
struct node{
    int l,r,id,bh,pre;
    friend bool operator <(const node&a,const node&b){
        return a.l/kk==b.l/kk?((a.l/kk)%2==0?a.r/kk<b.r/kk:a.r/kk>b.r/kk):a.l/kk<b.l/kk;
    }
}q[maxn],xg[maxn];
void change(int pos,int k){
    if(ll>pos||rr<pos) {a[pos]=k;return;}
    if(c[a[pos]]==1) sum--;
    c[a[pos]]--;
    if(!c[k]) sum++;
    c[k]++;
    a[pos]=k;
}
void del(int x){
    if(c[a[x]]==1) sum--;
    c[a[x]]--; 
}
void ins(int x){
    if(!c[a[x]]) sum++;
    c[a[x]]++;
}
void cul(int l,int r){
    while(rr<r) {ins(++rr);}
    while(rr>r) {del(rr--);}
    while(ll<l) {del(ll++);}
    while(ll>l) {ins(--ll);}
}
int main()
{
    scanf("%d%d",&n,&m);
    kk=sqrt(n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%s%d%d",s,&ll,&rr);
        if(s[0]=='Q') {
            q[++tot].l=ll;
            q[tot].r=rr;
            q[tot].id=i;
            q[tot].bh=tot;
        }
        else{
            xg[++tt].l=ll;
            xg[tt].r=rr;
            xg[tt].id=i;
        };
    }
    sort(q+1,q+tot+1);
    ll=0;rr=0;
    for(int i=1;i<=tot;i++){
        while(now+1<=tt&&xg[now+1].id<q[i].id){
          now++;
          xg[now].pre=a[xg[now].l];
          change(xg[now].l,xg[now].r);
        }
        while(xg[now].id>q[i].id){
          change(xg[now].l,xg[now].pre);
          now--;
        }
        cul(q[i].l,q[i].r); 
        ans[q[i].bh]=sum;
    }
    for(int i=1;i<=tot;i++)
    printf("%d
",ans[i]);
    return 0;
}