洛谷P2709 小B的询问（莫队）

题目描述

小B 有一个长为 nn 的整数序列 aa，值域为 [1,k][1,k]。
他一共有 mm 个询问，每个询问给定一个区间 [l,r][l,r]，求：

∑i=1kci2i=1∑kci2

其中 cic**i 表示数字 ii 在 [l,r][l,r] 中的出现次数。
小B请你帮助他回答询问。

输入格式

第一行三个整数 n,m,kn,m,k。

第二行 nn 个整数，表示 小B 的序列。

接下来的 mm 行，每行两个整数 l,rl,r。

输出格式

输出 mm 行，每行一个整数，对应一个询问的答案。

输入输出样例

输入 #1复制

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

输出 #1复制

6
9
5
2

莫队板题。一开始读错题了想了半天不知道怎么写2333

直接套P1972的模板即可。注意增加删除答案的时候不要忘记撤销操作。

#include <bits/stdc++.h>
using namespace std;
int n, a[100005], m, k, ans[100005], block;
inline int read() {
    char x;
    while((x = getchar()) > '9' || x < '0') ;
    int u = x - '0';
    while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0';
    return u;
}
int buf[105];  
inline void write(int i) {  
    int p = 0;  
    if(i == 0) p++;  
    else while(i) {  
        buf[p++] = i % 10;  
        i /= 10;  
    }  
    for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]);  
} 
struct node {
	int l, r, id;
} q[100005];

bool cmp(node a, node b) {
	return (a.l / block) ^ (b.l / block)? (a.l / block) < (b.l / block) : (a.l / block) & 1? a.r < b.r: a.r > b.r;
}
int Ans = 0, cnt[100001];
void add(int x) {
    Ans -= cnt[a[x]] * cnt[a[x]];//先减去现在的
    cnt[a[x]]++;
	Ans += cnt[a[x]] * cnt[a[x]];//再加上多删去的
}
void del(int x) {
	Ans -= cnt[a[x]] * cnt[a[x]];
    cnt[a[x]]--;
    Ans += cnt[a[x]] * cnt[a[x]];//多减的要加回来（因为x^2不是线性函数）
}
int main() {
 	n = read(); m = read(); k = read();
 	for (int i = 1; i <= n; i++) {
 		a[i] = read();
 	}
 	block = n / sqrt(m * 2 / 3);
 	for (int i = 1; i <= m; i++) {
 		q[i].l = read(); q[i].r = read(); q[i].id = i;
 	}
 	sort(q + 1, q + m + 1, cmp);
 	int l = 0, r = 0;
 	for(int i = 1; i <= m; i++) {
 		int ql = q[i].l, qr = q[i].r;
 		while(l < ql) del(l++);
 		while(l > ql) add(--l);
 		while(r < qr) add(++r);
 		while(r > qr) del(r--);
 		ans[q[i].id] = Ans - 1;
 	}
 	for(int i = 1; i <= m; i++) {
 		write(ans[i]); putchar('
');
 	}
 	return 0;
 }