[线段树] POJ 3468 - A Simple Problem with Integers

快来打我* 2022-08-08 00:55 40阅读 0赞

线段树成段更新，更新和查询利用延迟标记，不需要更新到叶子结点。

当要更新或查询的路径上遇到了延迟标记，则需要将此标记更新到子结点即可。

\#include <stdio.h>  
\#include <string.h>  
\#define lson rt << 1  
\#define rson rt << 1 | 1  
long long maxn\[100002 << 2\], lazy\[100002 << 2\];  
void build(int l, int r, int rt)  
\{  
if(l == r)  
\{  
scanf("%I64d", &maxn\[rt\]);  
return ;  
\}  
int mid = (l + r) >> 1;  
build(l, mid, lson);  
build(mid + 1, r, rson);  
maxn\[rt\] = maxn\[lson\] + maxn\[rson\];  
\}  
long long query(int l, int r, int rt, int L, int R)  
\{  
if(L <= l && R >= r)  
\{  
return maxn\[rt\];  
\}  
int mid = (l + r) >> 1;  
if(lazy\[rt\])  
\{  
lazy\[lson\] += lazy\[rt\];  
lazy\[rson\] += lazy\[rt\];  
maxn\[lson\] += (long long)(mid - l + 1) \* lazy\[rt\];  
maxn\[rson\] += (long long)(r - mid) \* lazy\[rt\];  
lazy\[rt\] = 0;  
\}  
long long ans = 0;  
if(L <= mid) ans = query(l, mid, lson, L, R);  
if(R > mid) ans += query(mid + 1, r, rson, L, R);  
return ans;  
\}  
void update(int l, int r, int rt, int L, int R, int val)  
\{  
if(L <= l && R >= r)  
\{  
maxn\[rt\] += (long long)(r - l + 1) \* val;  
lazy\[rt\] += val;  
return ;  
\}  
int mid = (l + r) >> 1;  
if(lazy\[rt\])  
\{  
lazy\[lson\] += lazy\[rt\];  
lazy\[rson\] += lazy\[rt\];  
maxn\[lson\] += (long long)(mid - l + 1) \* lazy\[rt\];  
maxn\[rson\] += (long long)(r - mid) \* lazy\[rt\];  
lazy\[rt\] = 0;  
\}  
if(L <= mid) update(l, mid, lson, L, R, val);  
if(R > mid) update(mid + 1, r, rson, L, R, val);  
maxn\[rt\] = maxn\[lson\] + maxn\[rson\];  
\}  
int main()  
\{  
int N, Q;  
char ch\[10\];  
while(~scanf("%d %d", &N, &Q))  
\{  
build(1, N, 1);  
memset(lazy, 0, sizeof(lazy));  
for(int i = 0; i < Q; i++)  
\{  
int x, y, z;  
scanf("%s", ch);  
if(ch\[0\] == 'Q')  
\{  
scanf("%d %d", &x, &y);  
printf("%I64d\\n", query(1, N, 1, x, y));  
\}  
else  
\{  
scanf("%d %d %d", &x, &y, &z);  
update(1, N, 1, x, y, z);  
\}  
\}  
\}  
return 0;  
\}