不带修改莫队（模板）

终于会模板了，感觉好暴力。
解题思路：
假设我们知道区间 $[l, r]$ 内的答案ans，将区间添加或删除一个元素x，只要求ans’与ans的关系即可。

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

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

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

然而数据中有L=R的情况，请特判这种情况，输出0/1。

输入格式
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。

输出格式
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）

输入输出样例
输入

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

输出 #1复制

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

$n u m [x]$ 记录颜色x出现过的次数
$C_{n + 1}^{2} = C_{n}^{2} + n$
$C_{n - 1}^{2} = C_{n}^{2} - (n - 1)$
如果颜色x添加一个， $a n s + = n u m [x]; + + n u m [x];$
如果颜色x减少一个， $- - n u m [x]; a n s - = n u m [x];$

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+8;
typedef long long ll;
ll n,m,c[MAXN],num[MAXN],id[MAXN];
ll ans[MAXN],mu[MAXN],sum;
struct Q{
    ll l,r,i;
}q[MAXN];
bool cmpid(const Q&a,const Q&b){
    if(id[a.l]^id[b.l])return a.l<b.l;
    if(id[a.l]&1)return a.r<b.r;//奇偶化排序
    return a.r>b.r;
}
inline void add(ll x){
     sum+=num[x];
     ++num[x];
}
inline void del(ll x){
    --num[x];
    sum-=num[x];
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){
    scanf("%lld%lld",&n,&m);
    ll block=n/sqrt(m);
    for(ll i=1;i<=n;++i){
        scanf("%lld",c+i);
        id[i]=i/block;
    }
    for(ll i=0;i<m;++i){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        mu[i]=(q[i].r-q[i].l+1)*(q[i].r-q[i].l)/2;
        q[i].i=i;
    }
    sort(q,q+m,cmpid);
    ll l=q[0].l,r=q[0].l-1;
    for(ll i=0;i<m;++i){
        ll ql=q[i].l,qr=q[i].r;
        while(l<ql)del(c[l++]);
        while(l>ql)add(c[--l]);
        while(r<qr)add(c[++r]);
        while(r>qr)del(c[r--]);
        ans[q[i].i]=sum;
    }
    ll g;
    for(ll i=0;i<m;++i){
        g=gcd(ans[i],mu[i]);
        if(g)printf("%lld/%lld\n",ans[i]/g,mu[i]/g);
        else printf("0/1\n");
    }
    return 0;
}

区间求和

小sun最近突然对区间来了兴趣，现在他有这样一个问题想问问你：
给你n个数，每个数为 $a_{i}$ ，现在有m个询问，每个询问 $l, r$ ，需要求出：
$\sum_{i = l}^{r} a_{i} * n u m (a_{i})$
$n u m (a_{i})$ 代表 $a_{i}$ 在这个区间中出现的次数。
你能帮帮他吗？
输入描述:
第一行，两个整数n,m
第二行，总共n个数，代表这个数列
接下来m行，每行两个整数l,r，代表一个询问
输出描述:
输出总共m行，对于每个询问，输出这个询问对应的答案
输入

10 5
1 3 2 4 5 6 4 5 6 7
1 5
2 5
3 4
1 10
3 7

输出

在区间 $[l, r]$ 内，数字x的全部贡献为： $x * n u m (x)^{2}$
$x * (n u m + 1)^{2} = x * n u m^{2} + x * (2 * n u m + 1)$

ans+=x*(num[x]*2+1);++num[x];//如果数字x增加一个：

--num[x];ans-=x*(num[x]*2+1);//如果数字x减少一个

#include<bits/stdc++.h>
using namespace std;
#define gc getchar
template<typename T>
inline void read(T&x) {x=0;char ch=gc();
    while (ch<'0'||ch>'9')ch=gc();
    while (ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-48,ch=gc();}
template <class T>
inline void print(T x) {
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int MAXN=1e5+8;
typedef long long ll;
ll num[MAXN],sum,ans[MAXN];
int id[MAXN],n,m,a[MAXN];
struct qq{
    int l,r,i;
    bool operator<(const qq&o)const{
        if(id[l]^id[o.l])return l<o.l;
        if(id[l]&1)return r>o.r;
        return r<o.r;
    }
}q[MAXN];
inline void add(int x){sum+=x*(num[x]<<1|1);++num[x];}
inline void del(int x){--num[x];sum-=x*(num[x]<<1|1);}
int main(){
    read(n),read(m);
    int blk=n/sqrt(m);
    for(int i=1;i<=n;++i){read(a[i]);id[i]=i/blk;}
    for(int i=0;i<m;++i){
        read(q[i].l);read(q[i].r);
        q[i].i=i;
    }
    sort(q,q+m);
    int l=q[0].l,r=q[0].l-1;
    for(int i=0;i<m;++i){
        int ql=q[i].l,qr=q[i].r;
        while(l<ql)del(a[l++]);
        while(l>ql)add(a[--l]);
        while(r<qr)add(a[++r]);
        while(r>qr)del(a[r--]);
        ans[q[i].i]=sum;
    }
    for(int i=0;i<m;++i){print(ans[i]);putchar('\n');}
    return 0;
}