luogu4827 夢美的線段樹

夢美的線段樹 題解

寫完被出題人噴代碼醜了嗚嗚嗚

題目連結點這

這題有點毒瘤啊，

__int128

才能過，建議食用洛谷ide

介于前面三篇的都比較玄學（代碼都比較醜）,打算自己寫一發

自己寫的線段樹常數應該比其他幾篇大一點，為了友善了解吧

首先數學期望

E = ∑ P i ∗ s u m i = 一 通 操 作 = ∑ s u m i 2 s u m r t E = \sum P_i * sum_i = 一通操作 = \frac{\sum sum_i^2}{sum_{rt}} E=∑Pi​∗sumi​=一通操作=sumrt​∑sumi2​​

這一步應該比較好計算，同時相信大部分人都死在了這裡比如我

然後想到這題不是線段樹維護期望，而是維護區間平方和

對于一個節點

struct node{
    int sum, tag; // 正常都區間和 & 标記
    int len; 也很好了解
    
    // 然後就有些奇怪都東西了
    int len_2, len_sum, con;
};
           

con

: contribution, 即為該節點對答案分子的貢獻， c o n r t = ∑ s u m i 2 con_rt = \sum sum_i^2 conr​t=∑sumi2​

因為con比較難以一步計算出來，是以考慮一個比較容易想到(放屁)的區間平方和

s u m 2 sum^2 sum2更新時， s u m n e w 2 = ( s u m o l d + t a g ∗ l e n ) 2 = s u m o l d 2 + 2 ∗ l e n ∗ t a g ∗ s u m o l d + l e n 2 ∗ t a g 2 sum_{new}^2 = (sum_{old} + tag * len)^2 = sum_{old}^2 + 2*len * tag * sum_{old} + len^2 * tag^2 sumnew2​=(sumold​+tag∗len)2=sumold2​+2∗len∗tag∗sumold​+len2∗tag2

即

sum +=

2 ∗ l e n ∗ t a g ∗ s u m o l d + l e n 2 ∗ t a g 2 2*len*tag*sum_{old} + len^2*tag^2 2∗len∗tag∗sumold​+len2∗tag2

包含上子節點的話就是， ∑ s u m 2 \sum sum^2 ∑sum2，也就是

con

了

KaTeX parse error: No such environment: align* at position 7: \begin{̲a̲l̲i̲g̲n̲*̲}̲ con & += \…

對于難以統計的 ∑ ( ( l e n ∗ s u m ) ) \sum ((len*sum)) ∑((len∗sum)) 和 ∑ ( l e n 2 ) \sum (len^2 ) ∑(len2) 這裡變可以單獨維護，這裡便是

Node

結構體裡奇怪的

len_sum, len_2

，注釋裡标注了

include child nodes

，都是包含其子節點的。

那麼考慮這兩個奇怪的東西，

• ∑ ( l e n i 2 ) \sum (len_i^2 ) ∑(leni2​)簡單，建樹的時候直接構造就好了
• 對于 ∑ ( l e n i ∗ s u m i ) \sum (len_i*sum_i) ∑(leni​∗sumi​)

• $ \begin{align*}

  \sum (len_isum_i)_{new} & = \sum(len_i * (sum_i + len_itag)) \

  &= \sum(len_i * sum_i + len_i^2tag) \

  &= \sum(len_isum_i)_{old} + tag * \sum len_i^2

  \end{align*} $

又回到了

len_2

是以這裡代碼裡對應的：

• len_2

  : ∑ l e n i 2 \sum len_i^2 ∑leni2​

• len_sum

  : ∑ ( l e n i ∗ s u m i ) \sum(len_i*sum_i) ∑(leni​∗sumi​)

• con

  : ∑ s u m 2 \sum sum^2 ∑sum2,答案的分子在

  con[root]

  裡

這麼一來，線段樹部分就很清晰了，自認為自己的數學功底很差，是以推公式的時候慢慢推，讓像我一樣的弱智都能看得懂

本來想交一發

long long

先來個90分的，然後發現，前90分也要

__int128

，這便是這題毒瘤的地方了。代碼量到這裡已經可以了，何必再爆

long long

,資料結構配高精有意思嗎？有意思嗎？有意思嗎？據觀察大家都用的

__int128

過的。

不過聽郭黑康說最後一個點q是MOD的倍數（題目不是保證不是倍數的嗎？？？），沒遇到這個坑，也不知道是不是我寫法的原因，

int128

之後

CE

了幾發就過了

最後輸出答案的時候，

gcd

,

power

啥的，就不說了，老生常談了

#include <bits/stdc++.h>
using namespace std;
typedef __int128 LL;
const int N = (1e5 + 7) << 2;
const LL MOD = 998244353;

LL sqr(LL x){return x*x;}
LL gcd(LL x, LL y){
	if (y) while((x %= y) && (y %= x));
	return x + y;
}
LL power(LL a, LL x){
    LL ans = 1;
    for (; x; x >>= 1){
        if (x & 1) ans = (ans * a) % MOD;
        a = (a * a) % MOD;
    }
    return ans % MOD;
}
//------------head & math-------------

int arr[N];

struct SegTree{
    #define lc (rt << 1)
    #define rc (rt << 1 | 1)
    #define lson rt<<1, l, mid
    #define rson rt<<1|1, mid+1, r

    int n;
    // for one Node
    LL sum[N], len[N], tag[N];
    LL len_2[N], len_sum[N];  // include child nodes
    LL con[N]; // contribution, also include child nodes

    // commonly pushUp
    void pushUp(const LL &rt) {
        sum[rt] = sum[lc] + sum[rc];
        len_sum[rt] = len[rt]*sum[rt] + len_sum[lc] + len_sum[rc];
        con[rt] = sqr(sum[rt]) + con[lc] + con[rc];
    }

    void Tag(const LL &rt, const LL &l, const LL &r, const LL &v){
        sum[rt] += v * (r-l+1);
        tag[rt] += v;
        con[rt] += 2*v*len_sum[rt] + sqr(v)*len_2[rt];
        len_sum[rt] += v * len_2[rt];
    }

    void pushDown(const LL &rt, const LL &l, const LL &r){
        if (!tag[rt]) return;
        LL mid = (l+r) >> 1;
        Tag(lson, tag[rt]);
        Tag(rson, tag[rt]);
        tag[rt] = 0;
    }

    void build(const LL &rt, const LL &l, const LL &r) {
        if (l == r) {
            sum[rt] = len_sum[rt] = (LL)arr[l];
            len[rt] = len_2[rt] = 1;
            tag[rt] = 0;
            con[rt] = sqr(sum[rt]);
            return;
        }
        LL mid = (l + r) >> 1;
        build(lson);
        build(rson);
        len[rt] = len[lc] + len[rc];
        len_2[rt] = sqr(len[rt]) + len_2[lc] + len_2[rc];
        tag[rt] = 0;
        pushUp(rt);
    }

    void update(const LL &rt, const LL &l, const LL &r, const LL &L, const LL &R, const LL &v) {
        if (L <= l && r <= R) {
            Tag(rt, l, r, v);
            return;
        }
        LL mid = (l + r) >> 1;
        pushDown(rt, l, r);
        if (L <= mid) update(lson, L, R, v);
        if (mid <  R) update(rson, L, R, v);
        pushUp(rt);
    }

    void query(){ // print ans;
        LL p = con[1], q = sum[1], gd = gcd(p, q);
        p /= gd, q /= gd;
        //printf("%d, %d: ", p, q);
        LL ans = ((p%MOD) * power(q, MOD-2)) % MOD;
        printf("%lld\n", ans);
    }

    void print(LL rt, LL l, LL r){ // prLL tree, debug
        printf("%d: [%d, %d], len = %d, len_2 = %d, sum = %d, len_sum = %d, tag = %d, con = %d\n", 
            rt, l, r, len[rt], len_2[rt], sum[rt], len_sum[rt], tag[rt], con[rt]);
        if (l == r) return;
        LL mid = (l + r) >> 1;
        print(rt<<1, l, mid);
        print(rt<<1|1, mid+1, r);
    }
} T;


int main(){
    //freopen("in.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    for (LL i = 1; i <= n; i++){
        scanf("%d", &arr[i]);
    }
    T.build(1, 1, n);
    //T.print(1, 1, n);

    for (int op, l, r, v; m--;){
        scanf("%d", &op);
        if (op==2) T.query();
        else{ // update
            scanf("%d%d%d", &l, &r, &v);
            T.update(1, 1, n, l, r, v);
        }
    }
    return 0;
}

           

最後再扯點啥呢，自己寫結構體都是把結構體當成

class

來用的，就當是全是

public

的

class

吧

define lson, rson

也是一個令人愉悅的點，跟kuangbing學的

還有哪裡看不懂歡迎私戳我提問或者

[email protected]

附件：

• 可能炸的公式1

  

• 可能炸的公式1

  

• 可能炸的公式2