POJ3468 A Simple Problem with Integers(线段树延时标记)

时间:2024-06-01 11:04:50

题目地址http://poj.org/problem?id=3468

题目大意很简单,有两个操作,一个

Q a, b 查询区间[a, b]的和

C a, b, c让区间[a, b] 的每一个数+c

第一次线段树的延时标记,花了好大的功夫才写好==!

很容易看出来使用使用线段树记录区间的和,但是难点在于每次修改的是一个区间而不是一个点

所以采用的方法就是每次做修改操作时,只将区间[a,b]的标记+c,而不是真正意义上的将区间[a, b] 的每一个值+c。

而当我们做查询操作时,就只需要将区间[a, b]在从[1, N]开始查找到查找到时所经过的区间的标记往下传递就可以了(同时记得更新当前节点的值)

POJ3468 A Simple Problem with Integers(线段树延时标记)

 #include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R typedef long long LL;
const double eps = 1e-;
const int MAXN = ;
const int MAXM = ; struct Node { LL sum, add; } tree[MAXN<<];
int a, b, N, Q;
LL c; void updataChild(int k, int L, int R)//将编号为k的标记传到他的子节点去
{
tree[k].sum += (R-L+) * tree[k].add;//先更新它自己的sum值
tree[k<<].add += tree[k].add;//将左右子节点的add值更新
tree[k<<|].add += tree[k].add;
tree[k].add = ;//去掉标记
} void update(int k, int L, int R)//更新区间的值
{
if(R<a || b<L) return ;//不再区间内 if(a<=L && R<=b) { tree[k].add += c; return; }//实际上只更新这个区间的add值 int mid = (L+R)>>; update(lson); update(rson); //往左和往右更新 tree[k].sum = tree[k<<].sum + tree[(k<<)+].sum//更新当前节点的sum
+ (mid-L+)*tree[k<<].add + (R-mid)*tree[k<<|].add;
} LL query(int k, int L, int R)
{
if(R<a || b<L) return ; if(a<=L && R<=b) return tree[k].sum + (R-L+)*tree[k].add;//注意加上当前节点的标记 int mid = (L+R)>>; updataChild(k, L, R);//吧标记传到子节点 return query(lson) + query(rson);
} int main()
{
while(~scanf("%d %d", &N, &Q))
{
mem0(tree); char ch;
for(a=;a<=N;a++)
{
scanf("%lld%*c", &c); b = a;//区间是[a, a]
update(, , N);
}
for(int i=;i<Q;i++)
{
scanf("%c", &ch);
if(ch == 'Q')
{
scanf("%d %d%*c", &a, &b);
printf("%lld\n", query(,,N));
}
else
{
scanf("%d %d %lld%*c", &a, &b, &c);
update(,,N);
}
}
}
return ;
}