https://www.luogu.com.cn/problem/P3372
如题，已知一个数列，你需要进行下面两种操作：
第一行包含两个整数 n, mn,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：
1 x y k
2 x y
输出包含若干行整数，即为所有操作 2 的结果。
5 51 5 4 2 32 2 41 2 3 22 3 41 1 5 12 1 4
11820
对于 30\%30% 的数据：n le 8n≤8，m le 10m≤10。对于 70\%70% 的数据：n le {10}^3n≤103，m le {10}^4m≤104。对于 100\%100% 的数据：1 le n, m le {10}^51≤n,m≤105。
保证任意时刻数列中任意元素的和在 [-2^{63}, 2^{63})[−263,263) 内。
【样例解释】
#include#include<iostream>#include#include #include using namespace std;typedef long long ll;const int maxn=1e6+10;int a[maxn]; inline int read(){ int x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x;}struct node{ ll l;//l:左节点 r:右节点 ll r;//dat:当前节点的值 laze_tag:懒标记，记录改变的值，递归传值 ll date,laze;}t[maxn];//四倍n void f(ll p,ll k){ t[p].laze+=k;//懒标记传递 t[p].date+=k*(t[p].r-t[p].l+1);//当前值加上所有节点总数*值 }void pushdown(ll p){//传懒标 f(p*2,t[p].laze); f(p*2+1,t[p].laze); //将懒标记的值传给下面的左右儿子节点 t[p].laze=0; //复原懒标记 }void js(ll p,ll l,ll r){//建树 t[p].l=l;//记录左右节点 t[p].r=r; if(l==r){//到达底部返回值 t[p].date=a[l]; return ; } ll mid=(l+r)/2;//中点 js(p*2,l,mid); js(p*2+1,mid+1,r); //递归初始化 t[p].date=t[p*2].date+t[p*2+1].date; //加上左右儿子节点 }void pushs(ll p,ll l,ll r,ll v){//区间加减 if(t[p].l>=l&&t[p].r<=r){//如果区间被包含就修改并打上懒标记 t[p].date+=v*(t[p].r-t[p].l+1);//加上所有值 t[p].laze+=v;//懒标记修改 return ; } pushdown(p);//查询懒标记，因为下面要递归 ll mid=(t[p].l+t[p].r)/2;//取中点 if(l<=mid){ pushs(p*2,l,r,v);//修改左边 } if(r>mid){ pushs(p*2+1,l,r,v);//修改右边 } t[p].date=t[p*2].date+t[p*2+1].date;//回溯时加上左右儿子节点的值 } ll outt(ll p,ll l){//单点查询 if(t[p].l==l&&t[p].r==l){//找到目标点就返回 return t[p].date; } pushdown(p);//先回复懒标记的值再传递，因为下面可能递归（要判断是否到了底部，就是这里出了问题QwQ） ll mid=(t[p].l+t[p].r)/2;//记录中点 if(l<=mid) return outt(p*2,l);//找左边 if(l>mid) return outt(p*2+1,l);//找右边 }ll check(ll p,ll l,ll r,ll x,ll y){ if(l>=x&&r<=y){ return t[p].date; } ll mid=(t[p].l+t[p].r)/2; ll ans=0; pushdown(p); if(x<=mid){ ans+=check(p*2,l,mid,x,y); } if(mid<y){ ans+=check(p*2+1,mid+1,r,x,y); } return ans;} int main(){ int n,m; n=read();m=read();//读入 for(int i=1;i<=n;i++) a[i]=read(); js(1,1,n);//建树 int z; int x,y,w; for(int i=1;i<=m;i++){ z=read(); if(z==1){ x=read(),y=read(),w=read(); pushs(1,x,y,w); } else{ x=read(),y=read(); ll z=check(1,1,n,x,y); printf("%lld",z); } } return 0;//华丽丽的结束，可以A掉树状数组2了！！！ }
京公网安备 11010802041100号