HDU_3437

??? 比較容易證明，x應(yīng)該取區(qū)間的中位數(shù)，于是問題就轉(zhuǎn)化成了求[l,r]區(qū)間內(nèi)大小排第(l+r)/2+1的數(shù)，然后將和計(jì)算出來即可。

??? 求區(qū)間的中位數(shù)可以用劃分樹來實(shí)現(xiàn)，但是和卻不可以在求得中位數(shù)后再利用原序列直接計(jì)算，因?yàn)樵瓍^(qū)間的元素是無序的，我們沒辦法進(jìn)行作差求和。聯(lián)想作差求和的條件，即要明確哪些數(shù)是比中位數(shù)大，哪些數(shù)比中位數(shù)小，而劃分樹恰好左子樹的元素總是比右子樹小，于是如果中位數(shù)在左子樹中，我們自然可以將右子樹中[l,r]區(qū)間內(nèi)的數(shù)與中位數(shù)的差先求出來，如果中位數(shù)在右子樹中，我們就可以先將左子樹中[l,r]區(qū)間內(nèi)的數(shù)與中位數(shù)的差先求出來，求和的過程可以在求得中位數(shù)的具體值后回溯的時(shí)候?qū)崿F(xiàn)。為了實(shí)現(xiàn)快速求和，我們在建劃分樹時(shí)可以額外建一個(gè)數(shù)組A[d][i]，表示在第d層的某節(jié)點(diǎn)上第i個(gè)元素及之前的元素之和。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXK 20
#define MAXD 100010
int N, M, sa[MAXD], a[MAXD], rank[MAXK][MAXD], h[MAXK][MAXD];
long long int A[MAXK][MAXD], ans;
int cmp(const void *_p, const void *_q)
{
int *p = (int *)_p, *q = (int *)_q;
if(a[*p] == a[*q])
return *p - *q;
return a[*p] - a[*q];
}
void init()
{
int i, j, k;
scanf("%d", &N);
for(i = 1; i <= N; i ++)
{
scanf("%d", &a[i]);
sa[i] = i;
}
}
void build(int lx, int rx, int d)
{
if(lx == rx)
{
A[d][lx] = a[sa[rank[d][lx]]];
return ;
}
int i, j, k, p = 0, mid = (lx + rx) / 2;
for(i = lx; i <= rx; i ++)
{
if(rank[d][i] <= mid)
rank[d + 1][lx + p ++] = rank[d][i];
else
rank[d + 1][mid + i - lx + 1 - p] = rank[d][i];
h[d][i] = p;
A[d][i] = a[sa[rank[d][i]]] + (i == lx ? 0 : A[d][i - 1]);
}
build(lx, mid, d + 1);
build(mid + 1, rx, d + 1);
}
int search(int lx, int rx, int x, int y, int k, int d)
{
if(lx == rx)
return sa[rank[d][lx]];
int j, n, m, mid = (lx + rx) / 2, tx, ty;
n = h[d][y], m = x == lx ? 0 : h[d][x - 1];
if(n - m >= k)
{
j = search(lx, mid, lx + m, lx + n - 1, k, d + 1);
tx = mid + 1 + x - lx - m, ty = mid + 1 + y - lx - n;
if(tx <= ty)
ans += A[d + 1][ty] - (tx == mid + 1 ? 0 : A[d + 1][tx - 1]) - (long long int)(ty - tx + 1) * a[j];
}
else
{

j = search(mid + 1, rx, mid + 1 + x - lx - m, mid + 1 + y - lx - n, k - n + m, d + 1);
tx = lx + m, ty = lx + n - 1;
if(tx <= ty)
ans += (long long int)(ty - tx + 1) * a[j] - A[d + 1][ty] + (tx == lx ? 0 : A[d + 1][tx - 1]);
}
return j;
}
void solve()
{
int i, j, k, x, y;
qsort(sa + 1, N, sizeof(sa[0]), cmp);
for(i = 1; i <= N; i ++)
rank[0][sa[i]] = i;
build(1, N, 0);
scanf("%d", &M);
for(i = 0; i < M; i ++)
{
scanf("%d%d", &x, &y);
++ x, ++ y;
k = (y - x) / 2 + 1;
ans = 0;
search(1, N, x, y, k, 0);
printf("%I64d\n", ans);
}
}
int main()
{
int t, tt;
scanf("%d", &t);
for(tt = 0; tt < t; tt ++)
{
init();
printf("Case #%d:\n", tt + 1);
solve();
printf("\n");
}
return 0;
}

總結(jié)

以上是生活随笔為你收集整理的HDU 3473 Minimum Sum的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。