codeforces86D.Powerfularray(分块)

题意：

给定一个数列： A1，A2，⋯An ，定义 Ks 为区间 （l，r） 中 s 出现的次数。
t 个查询，每个查询 l，r ，对区间内所有 a[i] ，求

∑（K2s⋅a[i]）

思路：

考虑到时间消耗来自于 L,R 指针的移动，如果没有分块的话，直接根据左端点小的排在前面，左端点相同的按右端点小的排在前面！
这样的话，因为左端点有序，所以从左往右 左端点最多移动 n 。而对于右端点，它是完全无序的，所以每一次询问下，它的移动都是O(n)的，所以复杂度为 O(n+n⋅q) ，所以就TLE on test6。

但是如果分块的话，因为对于一个块内，左端点是无序的(因为排序规则： returnx.l<y.l , 并不是 returnx.x<y.x )，所以每一次询问的话，如果移动仅发生在块内，就是 O(n−−√) ，如果移动发生在快外，最多也就 O(2⋅n−−√) ，所以左端点就是 t⋅n−−√ ，细算的话就是： (t−n−−√)⋅n−−√+n−−√⋅n−−√ 。右端点的话，因为在块内的话呢，右端点是有序的额，所以移动的最多 O(n−−√) ，而快与快之间的话，右端点是无序的，就是 O(n) ，所以细算就是 (t−n−−√)⋅n−−√+n⋅n−−√

代码(转载)：

#include 
#include 
#include 
#include 
#include 
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; i1)+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"%d%d", &q[i].x, &q[i].y);
        q[i].l = (q[i].x-1) / block_size;
        q[i].p = i;
    }
    //分块进行排序，保证了同一块内右端点最多移动n
    //同时保证了做端点最多移动sqrt N
    sort(q, q+t, cmp);


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

    res = 0;
    for (int i=0; iq[i].x, q[i].y, i);
        ans[q[i].p] = res;
    }

    for (int i=0; iprintf("%I64d\n", ans[i]);

    return 0;
}