POJ-3468

成段更新的线段树，应该也算比较基础的写法

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
namespace
{
typedef long long ll;
const int MAX_N = (1 << 18) - 1;
int n, N, Q, a, b, c;
ll da[MAX_N], db[MAX_N];
void add(int k, int l, int r)
{
if (a <= l && r <= b)
da[k] += c;
else if (!(b <= l || a >= r))
{
db[k] += (min(r, b) - max(l, a)) * c;
add(k * 2 + 1, l, (l + r) / 2);
add(k * 2 + 2, (l + r) / 2, r);
}
}
ll sum(int k, int l, int r)
{
if (b <= l || a >= r)
return 0;
else if (a <= l && r <= b)
return (r - l) * da[k] + db[k];
else
{
ll res = (min(r, b) - max(l, a)) * da[k];
res += sum(k * 2 + 1, l, (l + r) / 2);
res += sum(k * 2 + 2, (l + r) / 2, r);
return res;
}
}
ll init(int k)
{
if (k >= n - 1)
return db[k];
else
return db[k] = init(2 * k + 1) + init(2 * k + 2);
}
void input()
{
memset(da, 0, sizeof(da));
memset(db, 0, sizeof(db));
scanf("%d %d", &N, &Q);
n = 1;
while (n < N)
n <<= 1;
for (int i = 0; i < N; i++)
scanf("%lld", &db[i + n - 1]);
init(0);
char s[2];
while (Q--)
{
scanf("%s", s);
if (s[0] == 'Q')
{
scanf("%d %d", &a, &b);
a--;
printf("%lldn", sum(0, 0, n));
}
else
{
scanf("%d %d %d", &a, &b, &c);
a--;
add(0, 0, n);
}
}
}
}
int main()
{
input();
return 0;
}

最后

以上就是多情嚓茶为你收集整理的POJ-3468的全部内容，希望文章能够帮你解决POJ-3468所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。