Ryuji doesn't want to study 2018 徐州赛区网络预赛

题意:

 1、区间求

  a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r](L is the length of [ l, r ] that equals to r - l + 1)

 2、单点修改

解析:

只有这两个操作 并且区间求得值与前缀和极为相似

  所以嘛 就要想到树状数组

  树状数组能够维护前缀和 所以区间 [ l, r ] 就是r的前缀和减去l的前缀和

 但每个a[i]的系数都不同 求前缀和无用。。所以要想到化简一下  把每个a[i]的系数都化为一样的或者定量

由上面的式子化简一下就变为

(∑ri=la[i]*(n−i+1))−(n−r)*∑ri=la[i]

对于每个a[i]我们合并一下系数 是不是就是上式的系数

所以维护两个前缀和  一个a[i] 和 一个 (n-i+1)*a[i]

输出时 减就可以了

#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = 1e5+, INF = 0x7fffffff;
typedef long long LL;
LL cc[maxn], hh[maxn], A[maxn];
int n, q;
LL lowbit(LL x)
{
return x & -x;
} void add(LL x, LL y, LL yy)
{
for(LL i=x; i<=n; i+=lowbit(i))
cc[i] += y, hh[i] += yy;
} LL get_sum1(LL x)
{
LL res = ;
for(LL i=x; i>; i-=lowbit(i))
res += cc[i];
return res;
}
LL get_sum2(LL x)
{
LL res = ;
for(LL i=x; i>; i-=lowbit(i))
res += hh[i];
return res;
} int main()
{
cin >> n >> q;
for(LL i=; i<=n; i++)
{
cin >> A[i];
add(i, A[i], (n-i+)*A[i]);
}
while(q--)
{
int temp, a, b;
cin>> temp >> a >> b;
if(temp == )
{
LL res1 = get_sum1(b) - get_sum1(a-);
LL res2 = get_sum2(b) - get_sum2(a-);
cout<< res2 - (n-b)*res1 <<endl;
}
else
{
add(a, b-A[a], (n-a+)*(b-A[a]));
A[a] = b;
}
}
return ;
}
上一篇:top命令输出解释以及load average 详解及排查思路


下一篇:[转]基于display:table的CSS布局