网站开发python,信息技术做网站,关于加强网站建设与管理的通知,wordpress打开太慢责备今天我们把线段树的另一个模板看一下#xff1a; 在这里#xff0c;我们注意到乘的操作#xff0c;因此我们用两个懒标记来分别表示加和乘#xff0c;这时我们面临了一个问题#xff0c;就是当我们把标记往下传时#xff0c;它的儿子怎么知道是先乘还是先加#xff1f; …今天我们把线段树的另一个模板看一下 在这里我们注意到乘的操作因此我们用两个懒标记来分别表示加和乘这时我们面临了一个问题就是当我们把标记往下传时它的儿子怎么知道是先乘还是先加
究其原因其实是括号在作祟因此我们每一次乘的时候出了lazy*num,我们把加法的标记也乘一下这样子我们先乘后加就巧妙地化解了括号的问题。
同时还有一点我们需要注意那就是当标记下移时子节点的加法标记出了加上父节点的加法标记还要*父节点的乘法标记。
举个例子考虑原来的儿子为*23,父亲的懒标记也是*23,当我们下放时应该变成*49而其中的9就是由33*2得到的。
下面是AC代码
#includebits/stdc.h
using namespace std;
#define int long long
int n,a[10001],m,sum[4*10001];
int tree[4*10001];
int lazy1[4*10001];
int lazy2[4*10001];
void pushdown(int p,int l,int r);
int calc(int p,int l,int r,int x,int y,int k);
void build(int p,int l,int r){//建树 lazy2[p]1;if(lr){tree[p]a[l]*a[l];sum[p]a[l];return;}int mid(lr)/2;build(p*2,l,mid);build(p*21,mid1,r);tree[p]tree[p*21]tree[p*2];sum[p]sum[p*21]sum[p*2];return;
}
void pushdown(int p,int l,int r){//lazy标记下移 int mid(lr)/2;lazy1[p*2](lazy2[p])*lazy1[p*2]lazy1[p];lazy1[p*21]lazy1[p*21]*(lazy2[p])lazy1[p];lazy2[p*2]*lazy2[p];lazy2[p*21]*lazy2[p];tree[p*2](lazy2[p])*(lazy2[p])*tree[p*2]2*lazy1[p]*(lazy2[p])*sum[2*p]lazy1[p]*lazy1[p]*(mid-l1);//更新子节点的值 tree[p*21](lazy2[p])*(lazy2[p])*tree[p*21]2*lazy1[p]*(lazy2[p])*sum[2*p1]lazy1[p]*lazy1[p]*(r-mid);sum[p*2]*(lazy2[p]);sum[p*21]*(lazy2[p]);sum[p*2]lazy1[p]*(mid-l1);sum[p*21]lazy1[p]*(r-mid);lazy1[p]0;//自己因为下移清0 lazy2[p]1;
}
void change1(int p,int l,int r,int x,int y,int num){if(xlry){tree[p]2*num*(sum[p])num*num*(r-l1);sum[p]num*(r-l1);lazy1[p]num;return;}if(lazy1[p]!0||lazy2[p]!1){//区间部分修改需要下移 pushdown(p,l,r);}int mid(lr)/2;if(ymid) change1(p*2,l,mid,x,y,num);if(xmid) change1(p*21,mid1,r,x,y,num);if(xmidymid){change1(p*2,l,mid,x,mid,num);change1(p*21,mid1,r,mid1,y,num);}tree[p]tree[2*p]tree[2*p1];sum[p]sum[2*p]sum[2*p1];return;
}
void change2(int p,int l,int r,int x,int y,int num){if(xlry){tree[p]num*num*tree[p];sum[p]*num;lazy2[p]*num;lazy1[p]*num;return;}if(lazy1[p]!0||lazy2[p]!1){//区间部分修改需要下移 pushdown(p,l,r);}int mid(lr)/2;if(ymid) change2(p*2,l,mid,x,y,num);if(xmid) change2(p*21,mid1,r,x,y,num);if(xmidymid){change2(p*2,l,mid,x,mid,num);change2(p*21,mid1,r,mid1,y,num);}tree[p]tree[2*p]tree[2*p1];sum[p]sum[2*p]sum[2*p1];return;
}
int calc(int p,int l,int r,int x,int y,int k){if(lxry){if(k1) return tree[p];else return sum[p];}if(lazy1[p]!0||lazy2[p]!1){pushdown(p,l,r);}int mid(lr)/2;if(ymid) return calc(p*2,l,mid,x,y,k);if(xmid) return calc(p*21,mid1,r,x,y,k);return calc(p*2,l,mid,x,mid,k)calc(p*21,mid1,r,mid1,y,k);
}
signed main(){cinnm;for(int i1;in;i) scanf(%lld,a[i]);build(1,1,n);for(int i1;im;i){int x,y,k,op;scanf(%lld%lld%lld,op,x,y);if(op1){printf(%lld\n,calc(1,1,n,x,y,0));}else if(op2) printf(%lld\n,calc(1,1,n,x,y,1));else if(op3){scanf(%lld,k);change2(1,1,n,x,y,k);}else{scanf(%lld,k);change1(1,1,n,x,y,k);}}
}
