为了解决这样的问题，我们需要关于一个整型数组A[1..N]的数据结构，它支持这样的操作，起初，数组中的元素都是0，而且这样的数据结构支持下面两种操作：
1.更新A[pos] = A[pos] + value (其中value,pos是任意给定的，且可能为负值）
2.计算sum(A, l, r) = A[l]+A[l+1]+A[l+2]+...+A[r-1]+A[r] (其中l, r是任意给定的)
我们需要这样的操作都在O(log N)的时间内完成。能够实现这样操作的数据结构是 Binary Idexed Trees (BIT)。
在我们的解决方案中我们需要两个树状数组(BIT), 下标从1..L。其中第一个叫做cnt, cnt[i] 是当前种在i这个位置中树的个数（我们增加将所有树的下标增加1，使得所有的下标在1..L内）。第二个数组叫做dst, dst[i] = cnt[i]*i。换句话说，dst[i]是所有种在位置i的树的距离和。
假设我们要在x[i]处种一棵树， 并且想要尽快计算出他的price。我们有CL＝sum(cnt, 1, x[i]-1) 棵树在x[i]的左边。每个种在x0处的树距离第i棵树的距离是x[i]-x0。所以左边所有树到第i棵树的距离和就是 CL*x[i]-sum（all x0) = CL*x[i]-sum(dst, 1, x[i]-1)。同样的有CR=sum(cnt, x[i]+1, L)棵树在第i棵树的右边，他们到第i棵树的距离和是 sum(dst, x[i]+1, L)-CR*x[i]。所以总的price 可以由下式计算：
price = x[i] * (sum(cnt, 1, x[i]-1) - sum(cnt, x[i]+1, L)) +
sum(dst, x[i]+1, L) - sum(dst, 1, x[i]-1
计算好price后我们只需要更新cnt, dst数组， cnt[x[i]]=cnt[x[i]]+1, dst[x[i]]=dst[x[i]]+x[i]。
class ProductOfPrices {
public:
int product(int, int, int, int, int);
};
int L;
int64 cnt[200001], dst[200001];
int64 x[200001];
void add(int64 a[], int64 i, int64 x)
{
while (i <= L)
{
a[i] += x;
i |= i-1;
i++;
}
}
int64 getSum(int64 a[], int64 i)
{
int64 res = 0;
while (i > 0)
{
res += a[i];
i &=i-1;
}
return res;
}
int64 getSum(int64 a[], int64 i, int64 j)
{
if (j >= i)
return getSum(a, j) - getSum(a, i-1);
else
return 0;
}
int ProductOfPrices::product(int N, int l, int X0, int A, int B)
{
L = l;
x[0] = X0%L;
for (int i = 1; i < N; i++)
x[i] = ((int64(x[i-1])*int64(A))+int64(B)) % int64(L);
memset(cnt, 0, sizeof(cnt));
memset(dst, 0, sizeof(dst));
add(cnt, x[0]+1, 1);
add(dst, x[0]+1, x[0]+1);
int64 res = 1;
for (int i = 1; i < N; i++)
{
int64 price = (x[i]+1) * getSum(cnt, 1, x[i]) - getSum(dst, 1, x[i])
+ getSum(dst, x[i]+1, L) - getSum(cnt, x[i]+1, L) * (x[i]+1);
price %= 1000000007;
res = (res * price) % 1000000007;
add(cnt, x[i]+1, 1);
add(dst, x[i]+1, x[i]+1);
}return (int)res;
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。