POJ_3468(1)

? ? 在消化了PPT上思想之后，又重新做了一下這個題目。

? ? 不妨將原數組的元素記作a[i]，然后我們用堆建立兩棵線段樹，一棵的原數組為x[i](x[i]=a[i]-a[i-1]，即原數組的差分數組)，另一棵的原數組為ix[i](ix[i] = i*x[i])。

? ? 為什么要這么做呢？原因如下。

? ? 如果我們記S[i]為x[i]的前綴和，我們會發現S[i]實際上就是a[i]，也就是說差分的前綴和就等于原數組中的對應元素（因而才說差分是前綴和的逆運算）。我們不妨設SS[i]為S[i]的前綴和，在求區間和時用SS[b]–SS[a-1]自然是很方便的，然而對于修改操作，無論是維護S[i]還是SS[i]都會很麻煩，但恰恰是維護x[i]很簡單，只需要修改兩個值，x[a]和x[b+1]。

? ? 那么能不能將兩個方便之處統一到一起呢？當然可以，因為SS[n] = (n+1)*(x[1]+x[2]+…+x[n])-(1*x[1]+2*x[2]+…+n*x[n])，而i*x[i]自然就是前面提的ix[i]咯，于是我們只要維護x[i]和ix[i]即可，這樣在修改的時候每次只需各修改兩個值，并修改相應的祖先即可，于是把區間修改的復雜度降成了元素修改的復雜度。

? ? 查詢區間和的時候只需要用線段樹求x[i]與ix[i]的前綴和并做一定運算即可。

#include<stdio.h>
#include<string.h>
#define MAXD 100010
int N, Q, M;
long long int a[MAXD], x[4 * MAXD], ix[4 * MAXD];
char op[5];
void init()
{
int i, j;
for(M = 1; M < N + 2; M <<= 1);
a[0] = 0;
for(i = 1; i <= N; i ++)
scanf("%lld", &a[i]);
for(i = N; i >= 1; i --)
a[i] -= a[i - 1];
memset(x, 0, sizeof(x));
memset(ix, 0, sizeof(ix));
for(i = 1, j = M + 1; i <= N; i ++, j ++)
{
x[j] = a[i];
ix[j] = i * a[i];
}
for(i = M - 1; i > 0; i --)
{
x[i] = x[i * 2] + x[i * 2 + 1];
ix[i] = ix[i * 2] + ix[i * 2 + 1];
}
}
void solve()
{
int i, j, a, b, c;
scanf("%s", op);
if(op[0] == 'C')
{
scanf("%d%d%d", &a, &b, &c);
a = a + M;
x[a] += c, ix[a] += (a - M) * c;
for(; a ^ 1; a >>= 1)
{
x[a >> 1] = x[a] + x[a ^ 1];
ix[a >> 1] = ix[a] + ix[a ^ 1];
}
b = b + M + 1;
x[b] -= c, ix[b] -= (b - M) * c;
for(; b ^ 1; b >>= 1)
{
x[b >> 1] = x[b] + x[b ^ 1];
ix[b >> 1] = ix[b] + ix[b ^ 1];
}
}
else
{
scanf("%d%d", &a, &b);
int s, t;
long long int sum1, sum2, res;
sum1 = sum2 = 0;
s = M, t = a + M;
for(; s ^ t ^ 1; s >>= 1, t >>= 1)
{
if(~s & 1)
sum1 += x[s ^ 1], sum2 += ix[s ^ 1];
if(t & 1)
sum1 += x[t ^ 1], sum2 += ix[t ^ 1];
}
res = - a * sum1 + sum2;
sum1 = sum2 = 0;
s = M, t = b + M + 1;
for(; s ^ t ^ 1; s >>= 1, t >>= 1)
{
if(~s & 1)
sum1 += x[s ^ 1], sum2 += ix[s ^ 1];
if(t & 1)
sum1 += x[t ^ 1], sum2 += ix[t ^ 1];
}
res += (b + 1) * sum1 - sum2;
printf("%lld\n", res);
}
}
int main()
{
while(scanf("%d%d", &N, &Q) == 2)
{
init();
for(int i = 0; i < Q; i ++)
solve();
}
return 0;
}

轉載于:https://www.cnblogs.com/staginner/archive/2011/11/01/2231563.html

總結

以上是生活随笔為你收集整理的POJ 3468 A Simple Problem with Integers (1)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。