麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁 > 學院 > 開發設計 > 正文

poj 3468 線段樹lazy

2019-11-10 20:14:56
字體:
來源:轉載
供稿:網友
題目:

A Simple PRoblem with Integers
Time Limit: 5000MS Memory Limit: 131072K
Total Submissions: 102981 Accepted: 32160
Case Time Limit: 2000MS

Description

You have N integers, A1A2, ... , AN. You need to deal with two kinds of Operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.The second line contains N numbers, the initial values of A1A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.Each of the next Q lines represents an operation."C a b c" means adding c to each of AaAa+1, ... , Ab. -10000 ≤ c ≤ 10000."Q a b" means querying the sum of AaAa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4

Sample Output

455915

Hint

The sums may exceed the range of 32-bit integers.

代碼:

pushdown的時候要向下累加。

#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<ctype.h>    //tower()#include<set>  #include<map>  #include<iomanip>// cout<<setprecision(1)<<fixed<<a;#include<vector>   #include<cmath>	#include<algorithm>#include<bitset>#include<limits.h>#include<stack>#include<queue>using namespace std;const __int64 maxn=100010;const __int64 inf=0x7fffffff;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1__int64 add[maxn<<2];//維護當前lazy值 __int64 sum[maxn<<2];//線段樹維護當前區間和 void pushup(__int64 rt){//當前結點信息更新到父結點	sum[rt]=sum[rt<<1]+sum[rt<<1|1]; }void pushdown(__int64 rt,__int64 num){	if(add[rt]){		add[rt<<1]+=add[rt];				//+=  not  =		add[rt<<1|1]+=add[rt];		sum[rt<<1]+=add[rt]*(num-(num>>1));		sum[rt<<1|1]+=add[rt]*(num>>1);		add[rt]=0;	}}void build(__int64 l,__int64 r,__int64 rt){	add[rt]=0;	if(l==r){		scanf("%I64d",&sum[rt]);		return;	}	__int64 mid=(l+r)>>1;	build(lson);	build(rson);	pushup(rt);}void update(__int64 a,__int64 b,__int64 c,__int64 l,__int64 r,__int64 rt){	if(a<=l&&b>=r){		add[rt]+=c;				//+=  not  =		sum[rt]+=c*(r-l+1);		return;	}	pushdown(rt,r-l+1);	__int64 mid=(l+r)>>1;	if(a<=mid) update(a,b,c,lson);	if(b>mid) update(a,b,c,rson);	pushup(rt);}__int64 query(__int64 a,__int64 b,__int64 l,__int64 r,__int64 rt){	if(a<=l&&b>=r) return sum[rt];	pushdown(rt,r-l+1);	__int64 mid=(l+r)>>1;	__int64 s=0;	if(a<=mid) s+=query(a,b,lson);	if(b>mid) s+=query(a,b,rson);	return s;}int main(){//G++:5888K	2985MS    C++:5360K	2000MS    __int64 n,m,a,b,c;    char s[2];    while(scanf("%I64d%I64d",&n,&m)==2){    	memset(sum,0,sizeof(sum));        build(1,n,1);        while(m--){            scanf("%s",s);            if(s[0]=='Q'){//查詢                scanf("%I64d%I64d",&a,&b);                printf("%I64d/n",query(a,b,1,n,1));            }            else{//染色                 scanf("%I64d%I64d%I64d",&a,&b,&c);                update(a,b,c,1,n,1);            }        }    }    return 0;}


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 在线中文字幕亚洲 | 久久免费视频5 | 俄罗斯16一20sex牲色另类 | 美国黄色毛片女人性生活片 | www.精品一区| 亚洲国产精品500在线观看 | 色中色激情影院 | 久久99综合久久爱伊人 | 91麻豆精品国产91久久久更新资源速度超快 | 国产成人在线看 | 男女羞羞在线观看 | 久久精品久久精品国产大片 | 国产免费观看一区二区三区 | 激情久久一区二区 | 91社 | 色诱亚洲精品久久久久久 | 欧美性激情视频 | 国产一区二区视频网站 | 激情影院在线观看 | 免费国产之a视频 | 97视频一二区 | 91丨九色丨国产在线观看 | 欧美日韩国产成人在线 | 老子午夜影院 | 得得啪在线 | 国产在线精品一区二区三区不卡 | 毛片视频播放 | 黄色免费播放网站 | 北京一级毛片 | 国产亚洲福利 | 日本爽快片100色毛片视频 | 国产精品一区二区三区在线看 | 免费毛片a线观看 | 欧美一级黄色免费看 | 精品一区二区久久久 | 欧美亚洲啪啪 | 嫩草91在线 | 免费一级在线观看 | 黄色片网站免费 | 黄视频免费在线 | 欧美日韩亚洲成人 |