傳送門
支持區間加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（线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
