存一下写到一般的线段树

呃呃

1008-数据结构_2021秋季算法入门班第十一章习题：线段树、树状数组 (nowcoder.com)

#include <bits/stdc++.h>#define int long longusing namespace std;const int mxn=1e5+10;
const int mxe=1e5+10;
const int mod=1e9+7;
const int Inf=1e18;struct info{int sum;
};info operator+(const info &l,const info &r){info res;res.sum=l.sum+r.sum;return res;
}struct tag{int add,mul;
};struct Segtree{info val;tag t;
}tree[mxe<<2][3];
//1为区间和,2为区间平方和int N,M,op,l,r,x;
int a[mxn];void pushup(int rt){tree[rt][1].val=tree[rt<<1][1].val+tree[rt<<1|1][1].val;tree[rt][2].val=tree[rt<<1][2].val+tree[rt<<1|1][2].val;
}
void settag1(int rt,int tot){}
void settag2(int rt,int tot){}
void pushdown(int rt,int tot){for(int i=1;i<=2;i++){if(tree[rt][i].t.add!=0||tree[rt][i].t.mul!=1){if(i==1){settag1(rt<<1,tot-tot/2);settag1(rt<<1|1,tot/2);}else{settag2(rt<<1,tot-tot/2);settag2(rt<<1|1,tot/2);}tree[rt][i].t.add=0;tree[rt][i].t.mul=1;return;}}
}
void build(int rt,int l,int r){if(l==r){//tagtree[rt][1].t.add=tree[rt][2].t.add=0;tree[rt][1].t.mul=tree[rt][2].t.mul=1;//valtree[rt][1].val.sum=a[l];tree[rt][2].val.sum=a[l]*a[l];return;}int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt);
}
void modify(int rt,int l,int r,int x,int y,int k,int mode){if(x<=l&&r<=y){if(mode==1){//区间加settag1(rt,r-l+1);//1tree[rt][1].val.sum+=k*(r-l+1);//2tree[rt][2].val.sum=tree[rt][2].val.sum+2*k*tree[rt][1].val.sum+(r-l+1)*k*k;}else{//区间乘settag2(rt,r-l+1);//1tree[rt][1].val.sum*=k;//2tree[rt][2].val.sum*=k*k;}return;}pushdown(rt,r-l+1);int mid=l+r>>1;if(x<=mid) modify(rt<<1,l,mid,x,y,k,mode);if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k,mode);pushup(rt);
}
info query(int rt,int l,int r,int x,int y,int mode){if(x<=l&&r<=y){if(mode==1){return tree[rt][1].val;}else{return tree[rt][2].val;}}pushdown(rt,r-l+1);int mid=l+r>>1;if(x>mid) return query(rt<<1|1,mid+1,y,x,y,mode);else if(y<=mid) return query(rt<<1,l,mid,x,y,mode);else{return query(rt<<1,l,mid,x,y,mode)+query(rt<<1|1,mid+1,r,x,y,mode);}
}
void solve(){cin>>N>>M;for(int i=1;i<=N;i++) cin>>a[i];build(1,1,N);while(M--){cin>>op;if(op==1){cin>>l>>r;cout<<query(1,1,N,l,r,1).sum<<'\n';}else if(op==2){cin>>l>>r;cout<<query(1,1,N,l,r,2).sum<<'\n';}else if(op==3){cin>>l>>r>>x;modify(1,1,N,l,r,x,2);}else{cin>>l>>r>>x;modify(1,1,N,l,r,x,1);}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;while(__--)solve();return 0;
}