hdu 3473（劃分樹）

劃分樹。

第二次寫劃分樹，累的要死，回頭發現第一次寫的是錯的……-_-||，看來poj2104的資料太弱了……

x取中位數ave，用sum[dep][i]儲存劃分的dep層前i個之和，查詢時通過這個算出比ave小（大）的之和，計算即可。

送出後一直runtime error，無奈，最後還是借鑒了這篇文章：http://www.cnblogs.com/AndreMouche/archive/2011/03/05/1971775.html。

換成隻求小于ave數字之和，大于ave的數字和最後計算，ans = sumR - ave×（rnum - lnum）- sumL。

code：

#include <iostream>

using namespace std;

#define LS(a) ((a)*2)

#define RS(a) ((a)*2+1)

#define LE(a, b) (((a)+(b))/2)

#define RB(a, b) (((a)+(b))/2+1)

int v[100001];

long long s[100001] = {0};//原資料前i個之和

int lef[20][100001] = {0};

long long sum[20][100001] = {0};//劃分層次的累加和

int tt[20][100001];

int n, m, testn, a, b;

long long ans, sumL, sumR;

int lnum, rnum;

void BuildTree(int dep, int sl, int sr)

{

    if (sl == sr) {

        sum[dep][sl] = sum[dep][sl-1]+tt[dep][sl];

        return ;

    }

    int lb=sl, rb=RB(sl,sr);

    int mid = v[LE(sl,sr)];

    int lsame = LE(sl,sr) - sl +1;

    for (int i=sl; i<=sr; i++)

        if (tt[dep][i] < mid) lsame--;

    for (int i=sl; i<=sr; i++){

        sum[dep][i] = sum[dep][i-1] + tt[dep][i];

        lef[dep][i] = (i==sl)?  0 : lef[dep][i-1];

        if (tt[dep][i] == mid){

            if (lsame > 0){

                lef[dep][i]++;

                tt[dep+1][lb++] = tt[dep][i];

                lsame--;

            }else

                tt[dep+1][rb++] = tt[dep][i];

        }else if (tt[dep][i] <mid){

            lef[dep][i]++;

            tt[dep+1][lb++] = tt[dep][i];

        }else

            tt[dep+1][rb++] = tt[dep][i];

    }

    BuildTree(dep+1, sl, LE(sl,sr));

    BuildTree(dep+1, RB(sl,sr), sr);

}

int Query(int k, int b, int e, int d, int sl, int sr)

{

    if (b == e) return tt[d][b];

    int nl = (b==sl)?   lef[d][e] : lef[d][e]-lef[d][b-1];//區間到左兒子個數

    int xx = (b==sl)?   0 : lef[d][b-1];//區間左邊到左兒子個數

    int nr = (e-b+1)- nl;   //區間到右兒子個數

    int yy = (b-sl) - xx;   //區間左邊到右兒子個數

    int ret;

    //計算分在左右的區間斷點

    int lB = sl + xx;

    int lE = lB + nl - 1;

    int rB = RB(sl,sr) + yy;

    int rE = rB + nr - 1;

    if (nl >= k){//去左區間找

        ret = Query(k, lB, lE, d+1, sl, LE(sl,sr));

    }else{//去右區間找

        lnum += nl;

        sumL += sum[d+1][lE] - sum[d+1][lB-1];

        ret = Query(k-nl, rB, rE, d+1, RB(sl,sr), sr);

    }

    return ret;

}

long long Find(int beg, int end)

{

    ans = 0;

    sumL = 0;

    sumR = 0;

    lnum = 0;

    int k = (end-beg)/2 + 1;

    int ave = Query(k, beg, end, 0, 1, n);

    rnum = (end-beg+1) - lnum;

    sumR = s[end] - s[beg-1] - sumL;

    ans = sumR - ave*(rnum-lnum) - sumL;

    return ans;

}

int main()

{

    cin>>testn;

    for (int j=1; j<=testn; j++){

        memset(sum, 0, sizeof(sum));

        memset(lef, 0, sizeof(lef));

        memset(s, 0, sizeof(s));

        scanf("%d", &n);

        for (int i=1; i<=n; i++) {

            scanf("%d", &v[i]);

            tt[0][i] = v[i];

            s[i] = s[i-1] + v[i];

        }

        sort(v+1, v+n+1);

        BuildTree(0, 1, n);

        scanf("%d", &m);

        printf("Case #%d:\n", j);

        for (int i=0; i<m; i++){

            scanf("%d%d", &a, &b);

            printf("%I64d\n", Find(a+1, b+1));

        }

        printf("\n");

    }

    return 0;

}