题目大意: 维护一个长度为 N 的序列, 支持区间修改, 区间查询两种操作.
代码如下
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn=1e6+10;
- inline int read(){
- int x=0,f=1;char ch;
- do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
- do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
- return f*x;
- }
- int n,q,a[maxn];
- struct node{int lc,rc;long long sum,tag;};
- struct Segment_Tree{
- #define ls t[k].lc
- #define rs t[k].rc
- node t[maxn<<1];
- int tot;
- Segment_Tree():tot(1){}
- inline void pushup(int k){
- t[k].sum=t[ls].sum+t[rs].sum;
- }
- inline void pushdown(int k,int l,int r){
- int mid=l+r>>1;
- t[ls].sum+=t[k].tag*(mid-l+1),t[ls].tag+=t[k].tag;
- t[rs].sum+=t[k].tag*(r-mid),t[rs].tag+=t[k].tag;
- t[k].tag=0;
- }
- void build(int k,int l,int r){
- if(l==r){t[k].sum=a[l];return;}
- int mid=l+r>>1;
- ls=++tot,build(ls,l,mid);
- rs=++tot,build(rs,mid+1,r);
- pushup(k);
- }
- void modify(int k,int l,int r,int x,int y,int val){
- if(l==x&&y==r){t[k].sum+=(r-l+1)*(long long)val,t[k].tag+=val;return;}// 一定不要忘记开 long long
- int mid=l+r>>1;
- pushdown(k,l,r);
- if(y<=mid)modify(ls,l,mid,x,y,val);
- else if(x>mid)modify(rs,mid+1,r,x,y,val);
- else modify(ls,l,mid,x,mid,val),modify(rs,mid+1,r,mid+1,y,val);
- pushup(k);
- }
- long long query(int k,int l,int r,int x,int y){
- if(l==x&&r==y)return t[k].sum;
- int mid=l+r>>1;
- pushdown(k,l,r);
- if(y<=mid)return query(ls,l,mid,x,y);
- else if(x>mid)return query(rs,mid+1,r,x,y);
- else return query(ls,l,mid,x,mid)+query(rs,mid+1,r,mid+1,y);
- }
- }sgt;
- void read_and_parse(){
- n=read(),q=read();
- for(int i=1;i<=n;i++)a[i]=read();
- sgt.build(1,1,n);
- }
- void solve(){
- int opt,l,r,val;
- while(q--){
- opt=read(),l=read(),r=read();
- if(opt==1)val=read(),sgt.modify(1,1,n,l,r,val);
- else printf("%lld\n",sgt.query(1,1,n,l,r));
- }
- }
- int main(){
- read_and_parse();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2851335.html