题目链接:poj 3468 A Simple Problem with Integers
题目大意:给定一个序列,有Q次操作,询问一段区间的总和,为一段区间的元素统一加上v值。
解题思路:线段树的成段修改。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
const int maxn = 100005;
typedef long long ll;
struct Node {
int l, r;
ll sum, add;
void set (int l, int r, ll sum, ll add) {
this->l = l;
this->r = r;
this->sum = sum;
this->add = add;
}
void maintain (ll v) {
sum += (r - l + 1) * v;
add += v;
}
}nd[maxn * 4];
int N, Q, A[maxn];
void pushup (int u) {
nd[u].sum = nd[lson(u)].sum + nd[rson(u)].sum;
}
void pushdown(int u) {
if (nd[u].add) {
nd[lson(u)].maintain(nd[u].add);
nd[rson(u)].maintain(nd[u].add);
nd[u].add = 0;
}
}
void build (int u, int l, int r) {
nd[u].l = l;
nd[u].r = r;
nd[u].add = 0;
if (l == r) {
nd[u].sum = A[l];
return;
}
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
ll query(int u, int l, int r) {
if (l <= nd[u].l && nd[u].r <= r)
return nd[u].sum;
pushdown(u);
ll ret = 0;
int mid = (nd[u].l + nd[u].r) / 2;
if (l <= mid)
ret += query(lson(u), l, r);
if (r > mid)
ret += query(rson(u), l, r);
pushup(u);
return ret;
}
void modify (int u, int l, int r, int v) {
if (l <= nd[u].l && nd[u].r <= r) {
nd[u].maintain(v);
return;
}
pushdown(u);
int mid = (nd[u].l + nd[u].r) / 2;
if (l <= mid)
modify(lson(u), l, r, v);
if (r > mid)
modify(rson(u), l, r, v);
pushup(u);
}
int main () {
while (scanf("%d%d", &N, &Q) == 2) {
for (int i = 1; i <= N; i++)
scanf("%d", &A[i]);
build(1, 1, N);
int l, r, v;
char order[5];
for (int i = 0; i < Q; i++) {
scanf("%s%d%d", order, &l, &r);
if (order[0] == 'Q')
printf("%lld\n", query(1, l, r));
else {
scanf("%d", &v);
modify(1, l, r, v);
}
}
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1739064
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
POJ3468,线段树处理,注意longlongint
北大POJ1321-Chess Problem POJ1321-Chess Problem
树状数组解决区间操作_高效 对数组的某个区间进行两种操作:1)求和 2)每个数据加常数。要求:时间复杂度低
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739733
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2452 Sticks Problem.md
北大POJ2996-Help Me with the Game 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
poj 2763 程序 线段树 LCA 2000MS AC
POJ题解 个人写法 线段树每个人都不一样
poj 3757 Simple Distributed storage system.md
POJ2601 solution 题解 递推 POJ2601