CF 86D Powerful array 【分块算法,n*sqrt(n)】

时间:2021-07-03 20:02:41

给定一个数列:A1, A2,……,An,定义Ks为区间(l,r)中s出现的次数。

t个查询,每个查询l,r,对区间内所有a[i],求sigma(K^2*a[i])


离线+分块

将n个数分成sqrt(n)块。

对所有询问进行排序,排序标准:

      1. Q[i].left /block_size < Q[j].left / block_size (块号优先排序)

      2. 如果1相同,则 Q[i].right < Q[j].right (按照查询的右边界排序)


问题求解:

从上一个查询后的结果推出当前查询的结果。(这个看程序中query的部分)

如果一个数已经出现了x次,那么需要累加(2*x+1)*a[i],因为(x+1)^2*a[i] = (x^2 +2*x + 1)*a[i],x^2*a[i]是出现x次的结果,(x+1)^2 * a[i]是出现x+1次的结果。




时间复杂度分析:

排完序后,对于相邻的两个查询,left值之间的差最大为sqrt(n),则相邻两个查询左端点移动的次数<=sqrt(n),总共有t个查询,则复杂度为O(t*sqrt(n))。

又对于相同块内的查询,right端点单调上升,每一块所有操作,右端点最多移动O(n)次,总块数位sqrt(n),则复杂度为O(sqrt(n)*n)。

right和left的复杂度是独立的,因此总的时间复杂度为O(t*sqrt(n)  +  n*sqrt(n))。




#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define N 200100
typedef long long ll;
ll a[N], cnt[N*5], ans[N], res;
int L, R;

struct node {
    int x, y, l, p;
} q[N];
bool cmp(const node &x, const node &y) {
    if (x.l == y.l) return x.y < y.y;
    return x.l < y.l;
}
void query(int x, int y, int flag) {
    if (flag) {
        for (int i=x; i<L; i++) {
            res += ((cnt[a[i]]<<1)+1)*a[i];
            cnt[a[i]]++;
        }
        for (int i=L; i<x; i++) {
            cnt[a[i]]--;
            res -= ((cnt[a[i]]<<1)+1)*a[i];
        }
        for (int i=y+1; i<=R; i++) {
            cnt[a[i]]--;
            res -= ((cnt[a[i]]<<1)+1)*a[i];
        }
        for (int i=R+1; i<=y; i++) {
            res += ((cnt[a[i]]<<1)+1)*a[i];
            cnt[a[i]]++;
        }

    } else {
        for (int i=x; i<=y; i++) {
            res += ((cnt[a[i]]<<1)+1)*a[i];
            cnt[a[i]]++;
        }
    }
    L = x, R = y;
}
int main() {
    int n, t;

    scanf("%d%d", &n, &t);
    for (int i=1; i<=n; i++) scanf("%I64d", &a[i]);
    int block_size = sqrt(n);

    for (int i=0; i<t; i++) {
        scanf("%d%d", &q[i].x, &q[i].y);
        q[i].l = q[i].x / block_size;
        q[i].p = i;
    }

    sort(q, q+t, cmp);


    memset(cnt, 0, sizeof(cnt));

    res = 0;
    for (int i=0; i<t; i++) {
        query(q[i].x, q[i].y, i);
        ans[q[i].p] = res;
    }

    for (int i=0; i<t; i++) printf("%I64d\n", ans[i]);

    return 0;
}