BZOJ_3781_小B的询问_莫队

BZOJ_3781_小B的询问_莫队

Description

小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

Input

第一行，三个整数N、M、K。

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

接下来的M行，每行两个整数L、R。

Output

M行，每行一个整数，其中第i行的整数表示第i个询问的答案。

 

Sample Input

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

Sample Output

6
9
5
2

---

莫队水题，只是当时忘了在BZ上交....

早期代码欣赏？

 

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define N 50050
#define LL long long
int n, q, c[N], h[N], maxn ,block, pos[N];
LL now;
struct A {
    int s, t, id;
    LL ans;
}a[N];
bool cmp1(const A &x,const A &y) {
    if(pos[x.s] == pos[y.s]) return x.t < y.t;
    return pos[x.s] < pos[y.s];
}
bool cmp2(const A &x,const A &y) {return x.id < y.id; }
void update(int x,int sig) {
    now -= 1ll * h[c[x]] * h[c[x]];
    h[c[x]] += sig;
    now += 1ll * h[c[x]] * h[c[x]];
}
int main() {
    scanf("%d%d%d",&n,&q,&maxn);
    int i, j, block = sqrt(n), l, r = 0;
    for(i = 1;i <= n; ++ i) scanf("%d", &c[i]);
    for(i = 1;i <=block; ++ i) {
        l = r + 1;
        r = i * block;
        for(j = l;j <= r; ++ j) {
            pos[j] = i;
        }
    }
    if(r != n) {
        ++ block;
        l = r + 1;
        r = n;
        for(i = l;i <= r; ++ i) pos[i] = block;
    }
    for(i = 1;i <= q; ++ i) scanf("%d%d",&a[i].s,&a[i].t),a[i].id = i;
    sort(a + 1, a + q + 1, cmp1);
    for(l = 1, r = 0, i = 1;i <= q; ++ i) {
        while(l < a[i].s) update(l, -1), ++ l;
        while(l > a[i].s) update(l - 1, 1), -- l;
        while(r < a[i].t) update(r + 1, 1), ++ r;
        while(r > a[i].t) update(r, -1), -- r; 
        a[i].ans = now;
    }
    sort(a + 1, a + q + 1, cmp2);
    for(i = 1;i <= q; ++ i) printf("%d
",a[i].ans);
}