2020牛客NOIP赛前集训营-提高组（第四场）

~~要是早点写这题就能赛时调过了，就能Rank2了(痛哭~~

看到题目先来化一波式子：

$\sum_{T \subseteq S} [fib(\sum_{x \subseteq T} x)]^2$

$= \frac{1}{5} \sum_{T \subseteq S} [\frac{(1 + \sqrt 5)}{2}^{\sum_{x \subseteq T} x} - \frac{(1 - \sqrt 5)}{2}^{\sum_{x \subseteq T} x}]^2$

为了简化式子，令 $\phi = \frac{(1 + \sqrt 5)}{2}$ ， $\hat{\phi} = \frac{(1 - \sqrt 5)}{2}$ ，

$= \frac{1}{5} \sum_{T \subseteq S} (\phi ^ {2 \times \sum_{x \subseteq T} x} - 2 \times \phi ^{\sum_{x \subseteq T} x} \times \hat{\phi} ^{\sum_{x \subseteq T} x} + \hat{\phi} ^ {2 \times \sum_{x \subseteq T} x})$

$= \frac{1}{5} (\sum_{T \subseteq S} \phi ^ {2 \times \sum_{x \subseteq T} x} - 2 \times \sum_{T \subseteq S} \phi ^{\sum_{x \subseteq T} x} \times \hat{\phi} ^{\sum_{x \subseteq T} x} + \sum_{T \subseteq S} \hat{\phi} ^ {2 \times \sum_{x \subseteq T} x})$

发现长得都很像，所以其实只要求出形如 $\sum_{T \subseteq S} \phi ^ {\sum_{x \subseteq T} x}$ 的东西就行了。

考虑每个位置的权值对这个式子上面的指数的贡献，我们可以得知这个式子就等于 $\prod (\phi ^ x + 1) - 1$ 。

组合意义是每个位置选或者不选的所有情况，最后再减去空集。

发现这个就很好拿线段树维护了。

具体的，线段树上每个节点维护区间所有前缀积的和 $pre$ ，区间所有后缀积的和 $suf$ ，区间所有数的乘积 $s$ ，区间以及所有子区间的答案 $ans$ 。

那么 $pushup$ 的时候，有

$s_k = s_{lson} \times s_{rson}$

$ans_k = ans_{lson} + ans_{rson} + suf_{lson} \times pre_{rson}$

$pre_k = pre_{lson} + s_{lson} \times pre_{rson}$

$suf_k = suf_{rson} + s_{rson} \times suf_{lson}$

然后就是一开始线段树上每个位置的初值如何处理，开个结构体代表某个数是 $a \times \sqrt 5 + b$ 的形式，重载运算符 $\times$ 和 $+$ 就行。

根据 $fib$ 数的运算规则，最后 $\sqrt 5$ 的系数一定为 $0$ 。

其实不需要算三遍，由于 $\phi$ 和 $\hat{\phi}$ 是共轭的所以对答案贡献一样。

由于 $a_i$ 和 $v$ 的值域极小只有 $1e5$ ，所以预处理一下用数组存起来就行了。

/* 
    _______                       ________                        _______ 
   / _____ \                     / ______ \                      / _____ \ 
  / /     \_\  _     __     _   / /      \ \   _     __     _   / /     \_\ 
 | |          | |   |  |   | | | |        | | | |   |  |   | | | | 
 | |          | |   |  |   | | | |     __ | | | |   |  |   | | | | 
 | |       __ \  \  |  |  /  / | |     \ \| | \  \  |  |  /  / | |       __
  \ \_____/ /  \  \/ /\ \/  /   \ \_____\  /   \  \/ /\ \/  /   \ \_____/ / 
   \_______/    \___/  \___/     \______/\__\   \___/  \___/     \_______/ 
*/ 
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100000;
const int MOD = 998244353;
const int div2 = 499122177;
const int div5 = 598946612;

int a[N + 50], n, q;

void Read(int &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st < '0' || st > '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? - x : x;
    return;
}

struct Tmp
{
    int a, b;
    Tmp operator * (const Tmp &rhs) const
    {
        return (Tmp){(int)(1LL * b * rhs.a % MOD + 1LL * a * rhs.b % MOD) % MOD, (int)((1LL * a * rhs.a % MOD) * 5 % MOD + 1LL * b * rhs.b % MOD) % MOD};    
    }
    Tmp operator + (const Tmp &rhs) const
    {
        return (Tmp){(a + rhs.a) % MOD, (b + rhs.b) % MOD};
    }
} prework[N + 50][3];

struct Tmpp
{
    Tmp s0, s1, pre0, pre1, suf0, suf1, ans0, ans1;
};

void Prework()
{
    Tmp work0 = (Tmp){ div2, 1LL * 3 * div2 % MOD}, work1 = (Tmp){0, -1};
    prework[1][0] = work0;
    prework[1][1] = work1;
    for (int i = 2; i <= N; i++) 
        prework[i][0] = prework[i - 1][0] * work0,
        prework[i][1] = prework[i - 1][1] * work1;
    return;
}

struct SegmentTree
{
    Tmp s[(N << 2) + 50][2], pre[(N << 2) + 50][2], suf[(N << 2) + 50][2], ans[(N << 2) + 50][2];

    void Pushup(int k, int l, int r)
    {
        for (int i = 0; i <= 1; i++)
            s[k][i] = s[l][i] * s[r][i], 
            pre[k][i] = s[l][i] * pre[r][i] + pre[l][i],
            suf[k][i] = suf[l][i] * s[r][i] + suf[r][i],
            ans[k][i] = ans[l][i] + ans[r][i] + suf[l][i] * pre[r][i]; 
        return;
    }

    void Build(int k, int l, int r)
    {
        if (l == r)
        {
            for (int i = 0; i <= 1; i++) s[k][i] = pre[k][i] = suf[k][i] = ans[k][i] = (Tmp){prework[a[l]][i].a, (prework[a[l]][i].b + 1) % MOD};
            return;
        }
        int mid = (l + r) >> 1;
        Build(k << 1, l, mid); Build(k << 1 | 1, mid + 1, r);
        Pushup(k, k << 1, k << 1 | 1);
        return;
    }

    void Update(int k, int l, int r, int pos, int zhi)
    {
        if (l == r)
        {
            for (int i = 0; i <= 1; i++) s[k][i] = pre[k][i] = suf[k][i] = ans[k][i] = (Tmp){prework[zhi][i].a, (prework[zhi][i].b + 1) % MOD};
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) Update(k << 1, l, mid, pos, zhi);
        else Update(k << 1 | 1, mid + 1, r, pos, zhi);
        Pushup(k, k << 1, k << 1 | 1);
        return;
    } 

    Tmpp Query(int k, int l, int r, int x, int y)
    {
        if (x <= l && r <= y) return (Tmpp){s[k][0], s[k][1], pre[k][0], pre[k][1], suf[k][0], suf[k][1], ans[k][0], ans[k][1]};
        int mid = (l + r) >> 1;
        if (y <= mid) return Query(k << 1, l, mid, x, y);
        else if (x > mid) return Query(k << 1 | 1, mid + 1, r, x, y);
        else
        {
            Tmpp ql = Query(k << 1, l, mid, x, y), qr = Query(k << 1 | 1, mid + 1, r, x, y), tmpp;

            tmpp.s0 = ql.s0 * qr.s0,
            tmpp.pre0 = ql.s0 * qr.pre0 + ql.pre0,
            tmpp.suf0 = ql.suf0 * qr.s0 + qr.suf0;
            tmpp.ans0 = ql.ans0 + qr.ans0 + ql.suf0 * qr.pre0;

            tmpp.s1 = ql.s1 * qr.s1,
            tmpp.pre1 = ql.s1 * qr.pre1 + ql.pre1,
            tmpp.suf1 = ql.suf1 * qr.s1 + qr.suf1;
            tmpp.ans1 = ql.ans1 + qr.ans1 + ql.suf1 * qr.pre1;
            return tmpp;
        }
    }
} tr;

int main()
{
    Prework();
    Read(n); Read(q);
    for (int i = 1; i <= n; i++) Read(a[i]);
    tr.Build(1, 1, n);
    for (int i = 1, opt, l, r; i <= q; i++)
    {
        Read(opt); Read(l); Read(r);
        if (opt == 1) tr.Update(1, 1, n, l, r);
        else
        {
            Tmpp tmp = tr.Query(1, 1, n, l, r);
            int ans = 0;
            ans = (ans + 1LL * tmp.ans0.b * 2 % MOD - 2) % MOD;
            ans = (ans - 1LL * 2 * (tmp.ans1.b - 1) % MOD + MOD) % MOD;
            ans = 1LL * ans * div5 % MOD;
            printf("%d\n", ans);
        }
    }
    return 0;
}