正在了解懒标记,~~然而不懂~~
by 面壁者4号 @ 2019-08-07 22:36:04
@[Del_Your_Heart](/space/show?uid=62246) 楼主加了`cin`和`cout`优化,比`scanf`和`printf`以及普通快读还要快
by 樱初音斗橡皮 @ 2019-08-07 22:38:46
@[樱初音斗橡皮](/space/show?uid=66287) 噢,谢谢
by Del_Your_Heart @ 2019-08-07 22:41:31
**$zkw$线段树**
$zkw$一入深似海,从此递归是友人
```cpp
#include<bits/stdc++.h>
#define ri register int
#define int long long
using namespace std;
const int maxn=1e6+5;
int n,q,d=1,x,y,z,op,zkw[maxn<<1],lazy[maxn<<1];
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
inline void update(int l,int r,int k) {
int lid=0,rid=0,nid=1;
for(l=d+l-1,r=d+r+1;l^r^1;l>>=1,r>>=1,nid<<=1){
zkw[l]+=k*lid,zkw[r]+=k*rid;
if(~l&1)
lazy[l^1]+=k,zkw[l^1]+=k*nid,lid+=nid;
if(r&1)
lazy[r^1]+=k,zkw[r^1]+=k*nid,rid+=nid;
}
for(;l;l>>=1,r>>=1)
zkw[l]+=k*lid,zkw[r]+=k*rid;
}
inline int query(int l, int r){
int lid=0,rid=0,nid=1,ans=0;
for(l=d+l-1,r=d+r+1;l^r^1;l>>=1,r>>=1,nid<<=1){
if(lazy[l])
ans+=lazy[l]*lid;
if(lazy[r])
ans+=lazy[r]*rid;
if(~l&1)
ans+=zkw[l^1],lid+=nid;
if(r&1)
ans+=zkw[r^1],rid+=nid;
}
for(;l;l>>=1,r>>=1)
ans+=lazy[l]*lid+lazy[r]*rid;
return ans;
}
signed main(){
n=read();q=read();
while(d<=n+1)
d<<=1;
for(ri i=d+1;i<=d+n;++i)
zkw[i]=read();
for(ri i=d-1;i;--i)
zkw[i]=zkw[i<<1]+zkw[i<<1|1];
while(q--){
op=read();x=read();y=read();
if(op==1)
z=read(),update(x,y,z);
else
printf("%lld\n",query(x,y));
}
return 0;
}
```
by Del_Your_Heart @ 2019-08-07 22:43:52
谢谢巨佬们,我现在A了
by 面壁者4号 @ 2019-08-07 23:06:13
@[Del_Your_Heart](/space/show?uid=62246) ~~zkw这么牛逼,去A线段2啊(滑稽)~~
by 樱初音斗橡皮 @ 2019-08-07 23:08:57
@[樱初音斗橡皮](/space/show?uid=66287)
$zkw$:什么?优先级?我溜了。。。
by Del_Your_Heart @ 2019-08-07 23:11:34