传送门
支持区间加w(i−ql+1)2w(i−ql+1)2，将这个式子直接展开变成区间加wi2+w(ql−1)2+2w(1−ql)iwi2+w(ql−1)2+2w(1−ql)i，再选i做主元，会变成wi2+(2w−2w∗ql)i+w(ql−1)2wi2+(2w−2w∗ql)i+w(ql−1)2，发现就是区间加了一个二次函数，分别对二次函数每一项维护一个区间和就行了。
代码：
using namespace std;
inline ull read(){ull ans=
0,w=
1;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<
3)+(ans<<
1)+(ch^
48),ch=getchar();
return ans;
}
int n,m;
ull ans=
0,cal[N][
2];
struct Node{int l,r;ull sum[
3],add[
3];}
T[N<<
2];
inline void build(int p,int l,int r){
T[p].l=l,
T[p].r=r;
if(l==r)
return;build(lc,l,mid),build(rc,mid+
1,r);
}
inline void pushup(int p){
T[p].sum[
0]=
T[lc].sum[
0]+
T[rc].sum[
0];
T[p].sum[
1]=
T[lc].sum[
1]+
T[rc].sum[
1];
T[p].sum[
2]=
T[lc].sum[
2]+
T[rc].sum[
2];
}
inline void pushnow(int p,ull w1,ull w2,ull w3){
T[p].sum[
0]+=(
T[p].r-
T[p].l+
1)*w1;
T[p].sum[
1]+=(cal[
T[p].r][
0]-cal[
T[p].l-
1][
0])*w2;
T[p].sum[
2]+=(cal[
T[p].r][
1]-cal[
T[p].l-
1][
1])*w3;
T[p].add[
0]+=w1,
T[p].add[
1]+=w2,
T[p].add[
2]+=w3;
}
inline void pushdown(int p){pushnow(lc,
T[p].add[
0],
T[p].add[
1],
T[p].add[
2]);pushnow(rc,
T[p].add[
0],
T[p].add[
1],
T[p].add[
2]);
T[p].add[
0]=
T[p].add[
1]=
T[p].add[
2]=
0;
}
inline void update(int p,int ql,int qr,ull pos,ull v){
if(ql>
T[p].r||qr<
T[p].l)
return;
if(ql<=
T[p].l&&
T[p].r<=qr)
return pushnow(p,(ull)(pos-
1)*(pos-
1)*v,(ull)
2*(
1-pos)*v,(ull)v);pushdown(p);
if(qr<=mid)update(lc,ql,qr,pos,v);
else if(ql>mid)update(rc,ql,qr,pos,v);
else update(lc,ql,mid,pos,v),update(rc,mid+
1,qr,pos,v);pushup(p);
}
inline ull query(int p,int ql,int qr){
if(ql>
T[p].r||qr<
T[p].l)
return 0;
if(ql<=
T[p].l&&
T[p].r<=qr)
return T[p].sum[
0]+
T[p].sum[
1]+
T[p].sum[
2];pushdown(p);
if(qr<=mid)
return query(lc,ql,qr);
if(ql>mid)
return query(rc,ql,qr);
return query(lc,ql,mid)+query(rc,mid+
1,qr);
}
int main(){freopen(
"rneaty.in",
"r",stdin);freopen(
"rneaty.out",
"w",stdout);n=read(),m=read();
for(ull i=
1;i<=n;++i)cal[i][
0]=cal[i-
1][
0]+i,cal[i][
1]=cal[i-
1][
1]+i*i;build(
1,
1,n);
while(m--){int op=read(),L=read(),R=read();
if(op==
1){ull v=read();update(
1,L,R,(ull)L,v);}
else ans^=query(
1,L,R);}printf(
"%llu",ans);
return 0;
}
转载于:https://www.cnblogs.com/ldxcaicai/p/9738397.html
总结
以上是生活随笔为你收集整理的2018.08.04 cogs2633. [HZOI 2016]数列操作e（线段树）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
