codefroce D. Powerful array[初識塊狀數組]

                             codefroce D. Powerful array[初識塊狀數組]

由于是初始是以，僅僅能先用别人的分析。囧。。。

題目：

    給定一個數列：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 <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long LL;
const int V = 200000 + 10;
const int MAXN = 1000000 + 10;

struct node{
   int l,r,id;
}query[V];

int n,t,num[V],L,R,sum[MAXN];
LL ans[MAXN],now;

bool cmp(node a,node b){
    int m = sqrt(1.0*n);    //最好的理論值
    if(a.l / m != b.l / m){
        return a.l < b.l;
    }
    return a.r < b.r;
}

void modify(int l,int r){

    while(L < l){ //左區間不包括
        sum[num[L]]--;
        now -= num[L] * (sum[num[L]] << 1 | 1);
        L++;
    }

    while(R > r){  //右區間不包括
        sum[num[R]]--;
        now -= num[R] * (sum[num[R]] << 1 | 1);
        R--;
    }

    while(L > l){  //上一區間的左區間包括在目前區間裡
        L--;
        now += num[L] * (sum[num[L]] << 1 | 1);
        sum[num[L]]++;

    }

    while(R < r){  //上一區間的右區間包括在目前區間裡
        R++;
        now += num[R] * (sum[num[R]] << 1 | 1);
        sum[num[R]]++;
    }
}

int main()
{
    while(~scanf("%d%d",&n,&t)){
        for(int i = 1;i <= n;++i){
            scanf("%d",&num[i]);
        }

        for(int i = 1;i <= t;++i){
            scanf("%d%d",&query[i].l,&query[i].r);
            query[i].id = i;
        }

        sort(query+1,query + t + 1,cmp);
        now = L = R = 0;
        memset(sum,0,sizeof(sum));

        for(int i = 1;i <= t;++i){
            modify(query[i].l,query[i].r);
            ans[query[i].id] = now;
        }

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