这题主要就是多了一个平方和的操作。
我们维护平方和的值的时候。
需要注意在下放的时候，要先把乘法之后的sum1算出来，这对算sum1最终的值没有影响。
但是对sum2的值有影响。因为我们在计算中就在更新adtag的值，所以这个adtag它的sum1应该最终化。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> pii; const int N = 1e4+5; const int M = 1e6+5; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; LL a[N]; struct Node{LL L,r,adtag,mutag,sum1,sum2;}node[N << 2]; void Pushup(int idx) { node[idx].sum1 = node[idx << 1].sum1 + node[idx << 1 | 1].sum1; node[idx].sum2 = node[idx << 1].sum2 + node[idx << 1 | 1].sum2; } void Pushdown(int idx) { LL mutag = node[idx].mutag,adtag = node[idx].adtag; LL lslen = node[idx << 1].r - node[idx << 1].L + 1; LL rslen = node[idx << 1 | 1].r - node[idx << 1 | 1].L + 1; node[idx << 1].sum1 *= mutag; node[idx << 1].sum2 *= mutag * mutag; node[idx << 1 | 1].sum1 *= mutag; node[idx << 1 | 1].sum2 *= mutag * mutag; node[idx << 1].sum2 += 2 * adtag * node[idx << 1].sum1 + adtag * adtag * lslen; node[idx << 1 | 1].sum2 += 2 * adtag * node[idx << 1 | 1].sum1 + adtag * adtag * rslen; node[idx << 1].sum1 += adtag * lslen; node[idx << 1 | 1].sum1 += adtag * rslen; node[idx << 1].adtag *= mutag,node[idx << 1].adtag += adtag,node[idx << 1].mutag *= mutag; node[idx << 1 | 1].adtag *= mutag,node[idx << 1 | 1].adtag += adtag,node[idx << 1 | 1].mutag *= mutag; node[idx].mutag = 1,node[idx].adtag = 0; } void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r,node[idx].sum1 = node[idx].sum2 = 0; node[idx].adtag = 0,node[idx].mutag = 1; if(L == r) { node[idx].sum1 = a[L]; node[idx].sum2 = a[L] * a[L]; return ; } int mid = (L + r) >> 1; build(L,mid,idx << 1); build(mid + 1,r,idx << 1 | 1); Pushup(idx); } void tree_mul(int L,int r,int idx,LL val) { if(node[idx].L >= L && node[idx].r <= r) { node[idx].sum1 *= val; node[idx].sum2 *= val * val; node[idx].adtag *= val; node[idx].mutag *= val; return ; } int mid = (node[idx].L + node[idx].r) >> 1; Pushdown(idx); if(mid >= L) tree_mul(L,r,idx << 1,val); if(mid < r) tree_mul(L,r,idx << 1 | 1,val); Pushup(idx); } void tree_add(int L,int r,int idx,LL val) { if(node[idx].L >= L && node[idx].r <= r) { node[idx].adtag += val; node[idx].sum2 += node[idx].sum1 * val * 2 + (node[idx].r - node[idx].L + 1) * val * val; node[idx].sum1 += (node[idx].r - node[idx].L + 1) * val; return ; } int mid = (node[idx].L + node[idx].r) >> 1; Pushdown(idx); if(mid >= L) tree_add(L,r,idx << 1,val); if(mid < r) tree_add(L,r,idx << 1 | 1,val); Pushup(idx); } LL query(int L,int r,int idx,int id) { if(node[idx].L >= L && node[idx].r <= r) { if(id == 1) return node[idx].sum1; else return node[idx].sum2; } int mid = (node[idx].L + node[idx].r) >> 1; LL ans = 0; Pushdown(idx); if(mid >= L) ans += query(L,r,idx << 1,id); if(mid < r) ans += query(L,r,idx << 1 | 1,id); return ans; } int main() { int n,m;n = read(),m = read(); for(int i = 1;i <= n;++i) a[i] = read(); build(1,n,1); while(m--) { int op,x,y;op = read(),x = read(),y = read(); if(op == 1) printf("%lld ",query(x,y,1,1)); else if(op == 2) printf("%lld ",query(x,y,1,2)); else if(op == 3) { LL k;k = read(); tree_mul(x,y,1,k); } else { LL k;k = read(); tree_add(x,y,1,k); } } return 0; }