NEFU 1266 (线段树区间更新)

本文主要是介绍NEFU 1266 (线段树区间更新)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

快乐的雨季

Problem:1266

Time Limit:5000ms

Memory Limit:65535K

Description

六月到来，长江流域进入了雨季，在长江流域有一个小镇，这个小镇上的百姓都住在一条直线上，共有n户人家，编号为1~n，在直线上按编号依次坐落。进入雨季来，这个小镇共下了q次雨，每次下雨覆盖范围是一个连续的区间（L,R），表示编号为L至R的家庭位于降雨区，降雨量为x。镇长非常关心雨后受灾问题，于是每场雨后他想知道该场雨降雨区的家庭自进入雨季以来总的降水量，你能帮帮他吗？

Input

多组数据输入。
每组数据的第一行n，q（1<=n,q<=1e5）表示该小镇共有n户人家，共下了q场雨。
接下来q行，每行3个整数L,R,x (1<=L<=R<=n,1<=x<=10000)表示该场雨覆盖范围和降雨量。

Output

每场雨后输出降雨区总的降水量（自进入雨季来总的降水量，包括该场雨）。

Sample Input

6 4
2 5 10
3 6 7
1 6 102
4 5 57

Sample Output

40
58
680
352

Hint

Source

CJJ

 

题意：中文题。

思路：线段树区间更新的裸题。

代码：

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100005;
long long tr[maxn*4];
long long add[maxn*4];
void pushup(int i)
{tr[i]=tr[i*2]+tr[i*2+1];
}
void pushdown(int i,int len)
{if(add[i]>0){add[i*2]+=add[i];add[i*2+1]+=add[i];tr[i*2]+=add[i]*(len-len/2);tr[i*2+1]+=add[i]*(len/2);add[i]=0;}
}
void update(int i,int x,int y,int l,int r,int c)
{if(x<=l&&r<=y){add[i]+=c;tr[i]+=(long long)((r-l+1)*c);return;}pushdown(i,r-l+1);int mid=(l+r)/2;if(x<=mid) update(i*2,x,y,l,mid,c);if(y>mid) update(i*2+1,x,y,mid+1,r,c);pushup(i);
}
long long query(int i,int x,int y,int l,int r)
{long long sum=0;if(x<=l&&r<=y){sum+=tr[i];return sum;}pushdown(i,r-l+1);int mid=(l+r)/2;if(x<=mid) sum+=query(i*2,x,y,l,mid);if(y>mid) sum+=query(i*2+1,x,y,mid+1,r);pushup(i);return sum;
}
int main()
{int n,q;while(~scanf("%d%d",&n,&q)){memset(tr,0,sizeof(tr));memset(add,0,sizeof(add));int l,r,x;for(int i=1;i<=q;i++){scanf("%d%d%d",&l,&r,&x);update(1,l,r,1,n,x);printf("%lld\n",query(1,l,r,1,n));}}return 0;
}

 

 

 

 

 

这篇关于NEFU 1266 (线段树区间更新)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---