题解 | #E线段树#

<E-线段树>这题一开始看别人的代码，基本都是暴力维护，一个维护区间的和，一个维护的是答案要给出的，但是仔细思考之后并没有这么的麻烦

$ans=\sum_{i=1}^{n}\sum_{j=i+1}^{n}a[i]a[j]$
经过把玩样例和理解题意可得我们要求的ans即为上述的式子，通过基础和式变换可转化成

$\frac{1}{2}((sum_{i=1}^{n}a[i])^2-sum_{i=1}^{n}a[i]^2)$
也就是区间和的平方减去区间平方和乘以二分之一，这应该就是此题的正解，用线段树维护区间和以及区间平方和即可，可以直接把上一题代码搬过来加取模就行，不过注意取模很ex，我因为取模被卡了好久好久qwq

下面给出代码!!!

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <set>

using namespace std;
#define int long long
#define endl '\n'
const int maxn = 100005;
const int maxm = maxn << 1;
int p;
#define lson node << 1
#define rson node << 1 | 1
struct node{
    int val,pf,add,mul;
}t[maxn << 2];
int n,m;
int a[maxn];
void pushup(int node){
    t[node].val = (t[lson].val + t[rson].val) % p;
    t[node].pf = (t[lson].pf + t[rson].pf) % p;
}
void spread(int l,int r,int node){
    int &k = t[node].mul;
    t[lson].mul = t[lson].mul * k % p;
    t[rson].mul = t[rson].mul * k % p;
    t[lson].add = t[lson].add * k % p;
    t[rson].add = t[rson].add * k % p;
    t[lson].val = t[lson].val * k % p;
    t[rson].val = t[rson].val * k % p;
    t[lson].pf = t[lson].pf * k % p * k % p;
    t[rson].pf = t[rson].pf * k % p * k % p;
    k = 1;
    int mid = l + r >> 1;
    int &x = t[node].add;
    t[lson].add = (t[lson].add + x) % p;
    t[rson].add = (t[rson].add + x) % p;
    t[lson].pf = (t[lson].pf + 2 * t[lson].val % p * x % p + x * x % p * (mid - l + 1) % p) % p;
    t[rson].pf = (t[rson].pf + 2 * t[rson].val % p * x % p + x * x % p * (r - mid) % p) % p;
    t[lson].val = (t[lson].val + (mid - l + 1) * x % p) % p;
    t[rson].val = (t[rson].val + (r - mid) * x % p) % p;
    x = 0;
}
void build(int l,int r,int node){
    t[node].mul = 1;
    t[node].add = 0;
    if (l == r) {
        t[node].val = a[l] % p;
        t[node].pf = a[l] * a[l] % p;
        return;
    }
    int mid = l + r >> 1;
    build(l,mid,lson);
    build(mid+1,r,rson);
    pushup(node);
}
void add(int l,int r,int x,int y,int node,int k){
    if (x <= l && r <= y){
        t[node].pf = (t[node].pf + 2 * t[node].val % p * k % p + k * k % p * (r - l + 1)) % p;
        t[node].val = (t[node].val + k * (r - l + 1) % p) % p;
        t[node].add = (t[node].add + k) % p;
        return;
    }
    spread(l,r,node);
    int mid = l + r >> 1;
    if (x <= mid) add(l,mid,x,y,lson,k);
    if (y > mid) add(mid+1,r,x,y,rson,k);
    pushup(node);
}
void mul(int l,int r,int x,int y,int node,int k){
    if (x <= l && r <= y){
        t[node].val = t[node].val * k % p;
        t[node].pf = t[node].pf * k % p * k % p;
        t[node].add = t[node].add * k % p;
        t[node].mul = t[node].mul * k % p;
        return;
    }
    spread(l,r,node);
    int mid = l + r >> 1;
    if (x <= mid) mul(l,mid,x,y,lson,k);
    if (y > mid) mul(mid+1,r,x,y,rson,k);
    pushup(node);
}
int queryval(int l,int r,int x,int y,int node){
    if (x <= l && r <= y){
        return t[node].val;
    }
    spread(l,r,node);
    int mid = l + r >> 1;
    int ans = 0;
    if (x <= mid)   ans = (ans + queryval(l,mid,x,y,lson)) % p;
    if (y > mid)    ans = (ans + queryval(mid+1,r,x,y,rson)) % p;
    return ans % p;
}
int querypf(int l,int r,int x,int y,int node){
    if (x <= l && r <= y){
        return t[node].pf;
    }
    spread(l,r,node);
    int mid = l + r >> 1;
    int ans = 0;
    if (x <= mid)   ans += querypf(l,mid,x,y,lson);
    if (y > mid)    ans += querypf(mid+1,r,x,y,rson);
    return ans % p;
}
int quick(int n,int q){
    int ans = 1;
    while (q){
        if (q & 1) ans = ans * n % p;
        q >>= 1;
        n = n * n % p;
    }
    return ans;
}
void solve(){
    cin >> n >> m >> p;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1,n,1);
    while (m --){
        int op,x,l,r;
        cin >> op >> l >> r ;
        if (op == 3){
            int val = queryval(1,n,l,r,1);
            int pf = querypf(1,n,l,r,1);
            cout << (val * val % p - pf + p) % p * quick(2,p - 2) % p << endl;
        }
        if (op == 2){
            cin >> x;
            mul(1,n,l,r,1,x);
        }
        if (op == 1){
            cin >> x;
            add(1,n,l,r,1,x);
        }
    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}