首页 > 代码库 > codevs 1082 线段树练习3
codevs 1082 线段树练习3
1082 线段树练习 3
时间限制: 3 s 空间限制: 128000 KB 题目等级 : 大师 Master
题目描述 Description
给你N个数，有两种操作：
1：给区间[a,b]的所有数增加X
2：询问区间[a,b]的数的和。
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，
再接下来一个正整数Q，每行表示操作的个数，
如果第一个数是1，后接3个正整数，
表示在区间[a,b]内每个数增加X,如果是2，
表示操作2询问区间[a,b]的和是多少。
pascal选手请不要使用readln读入
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 2 3
样例输出 Sample Output
9
数据范围及提示 Data Size & Hint
数据范围
1<=n<=200000
1<=q<=200000
喜闻乐见的Code
#include<cstdio>using namespace std;#define maxn 200010struct Segment_Tree { int l,r,tag; long long sum; }t[maxn<<2];int readint() { char c=getchar();int x=0,flag=1; for(;c<‘0‘||c>‘9‘;c=getchar()) if(c==‘-‘) flag=-1; for(;c>=‘0‘&&c<=‘9‘;c=getchar()) x=(x<<1)+(x<<3)+c-‘0‘; return x*flag;}long long readll() { char c=getchar();long long x=0,flag=1; for(;c<‘0‘||c>‘9‘;c=getchar()) if(c==‘-‘) flag=-1; for(;c>=‘0‘&&c<=‘9‘;c=getchar()) x=(x<<1)+(x<<3)+c-‘0‘; return x*flag;}void Build_Tree(int now,int L,int R) { t[now].l=L;t[now].r=R; if(L==R) { t[now].sum=readll(); return; } int mid=L+R>>1,lc=now<<1,rc=now<<1|1; Build_Tree(lc,L,mid);Build_Tree(rc,mid+1,R); t[now].sum=t[lc].sum+t[rc].sum; return;}void Push_Down(int now) { int len=t[now].r-t[now].l+1; int lc=now<<1,rc=now<<1|1; t[lc].tag+=t[now].tag; t[rc].tag+=t[now].tag; t[lc].sum+=(len-(len>>1))*t[now].tag; t[rc].sum+=(len>>1)*t[now].tag; t[now].tag=0; return;}void Modify_Single_Node(int now,int pos,int x) { int l=t[now].l,r=t[now].r; if(l==r) { t[now].sum+=x; return; } if(t[now].tag) Push_Down(now); int mid=l+r>>1,lc=now<<1,rc=now<<1|1; if(pos<=mid) Modify_Single_Node(lc,pos,x); else Modify_Single_Node(rc,pos,x); t[now].sum=t[lc].sum+t[rc].sum; return;}void Modify_Interval(int now,int L,int R,int x) { int l=t[now].l,r=t[now].r; if(l==L&&R==r) { t[now].tag+=x; t[now].sum+=(R-L+1)*x; return; } if(t[now].tag) Push_Down(now); int mid=l+r>>1,lc=now<<1,rc=now<<1|1; if(R<=mid) Modify_Interval(lc,L,R,x); else if(L>mid) Modify_Interval(rc,L,R,x); else { Modify_Interval(lc,L,mid,x); Modify_Interval(rc,mid+1,R,x); } t[now].sum=t[lc].sum+t[rc].sum; return;}long long Query_Single_Node(int now,int pos) { int l=t[now].l,r=t[now].r; if(l==r) return t[now].sum; if(t[now].tag) Push_Down(now); int mid=l+r>>1,lc=now<<1,rc=now<<1|1; if(pos<=mid) return Query_Single_Node(lc,pos); else return Query_Single_Node(rc,pos);}long long Query_Interval(int now,int L,int R) { int l=t[now].l,r=t[now].r; if(l==L&&R==r) return t[now].sum; if(t[now].tag)Push_Down(now); int mid=l+r>>1,lc=now<<1,rc=now<<1|1; if(R<=mid) return Query_Interval(lc,L,R); else if(L>mid) return Query_Interval(rc,L,R); else return (Query_Interval(lc,L,mid)+Query_Interval(rc,mid+1,R));}int main() { int n,m; n=readint(); Build_Tree(1,1,n); m=readint(); while(m--) { int op; op=readint(); if(op==1) { int L,R,x; L=readint();R=readint();x=readint(); Modify_Interval(1,L,R,x); } else { int L,R; L=readint();R=readint(); printf("%lld\n",Query_Interval(1,L,R)); } } return 0;}
codevs 1082 线段树练习3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。