题解：P7334 [JRKSJ R1] 吊打

yuezhongyan · 2025-11-25 15:25:11 · 题解

solution

模拟赛神人把这题和一个 KMP 题拼了起来，还嘲讽我们做不出来。

考虑线段树，发现开方操作和花神游历各国一样，最后一定是一堆 1，直接暴力做就可以。

平方操作可以记录下一个 laz，在这之后的操作就可以直接在上面加加减减。

最后就是算一堆形似 x^{2^k} 状物，可以用费马小定理划一下，发现直接对 2^k 取模 mod-1 就结束了。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 5, mod = 998244353;
string s;
int nxt[N], a[N], n, q;
inline int qik(int a, int b, int p) {
    int res = 1, ans = 1, now = 2;
    while (b) {
        if (b & 1) ans = ans * now % (p - 1);
        now = now * now % (p - 1);
        b >>= 1;
    }
    while (ans) {
        if (ans & 1) res = res * a % p;
        a = a * a % p;
        ans >>= 1;
    }
    return res;
}
struct node{int l, r, laz2, val, flag;};
struct seg{
    node tr[N << 2];
    void pushup(int u) {
        if (tr[u << 1].laz2 && tr[u << 1 | 1].laz2) {
            int tmp = min(tr[u << 1].laz2, tr[u << 1 | 1].laz2);
            tr[u].laz2 += tmp;
            tr[u << 1].laz2 -= tmp, tr[u << 1 | 1].laz2 -= tmp;
        }
        tr[u].flag = tr[u << 1].flag & tr[u << 1 | 1].flag;
    }
    void pushdown(int u) {
        if (tr[u].laz2) {
            tr[u << 1].laz2 += tr[u].laz2;
            tr[u << 1 | 1].laz2 += tr[u].laz2;
            tr[u].laz2 = 0;
        }
    }
    void build(int u, int l, int r) {
        tr[u] = {l, r};
        if (l == r) {
            tr[u].val = a[l];
            if (tr[u].val == 1) tr[u].flag = 1;
            return ;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
    void modify_1(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) {
            if (tr[u].laz2) {
                tr[u].laz2 -- ;
                return ;
            }
            if (tr[u].flag) return ;
        }
        if (tr[u].l == tr[u].r) {
            tr[u].val = sqrt(tr[u].val);
            if (tr[u].val == 1) tr[u].flag = 1;
            return ;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid) modify_1(u << 1, l, r);
        if (r > mid) modify_1(u << 1 | 1, l, r);
        pushup(u);
    }
    void modify_2(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) {
            tr[u].laz2 ++ ;
            return ;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid) modify_2(u << 1, l, r);
        if (r > mid) modify_2(u << 1 | 1, l, r);
        pushup(u);
    }
    int query(int u, int pos) {
        if (tr[u].l == tr[u].r) {
            if (tr[u].val == 1) return 1;
            else if (tr[u].laz2) return qik(tr[u].val, tr[u].laz2, mod);
            else return tr[u].val;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (pos <= mid) return query(u << 1, pos);
        else return query(u << 1 | 1, pos);
    }
}T;
signed main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    T.build(1, 1, n);
    int ans = 0;
    while (q -- ) {
        int op, l, r; cin >> op >> l >> r;
        if (op == 1) {
            T.modify_1(1, l, r);
        } else {
            T.modify_2(1, l, r);
        }
    }
    for (int i = 1; i <= n; i ++ )
        ans = (ans + T.query(1, i)) % mod;
    cout << ans;
    return 0;
}