Luogu P7334 [JRKSJ R1] 吊打

题目描述

https://www.luogu.com.cn/problem/P7334

简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次操作，操作有两种，给定 $l,r$ 区间中每个 $a_i$ 变成 $\sqrt{\lfloor a_i\rfloor}$；给定 $l,r$，区间中每个数 $a_i$ 变成 $a_i^2$，在所有操作进行完之后，请输出 $\sum_{i=1}^na_i$

$n,m\le 2\times 10^5$

Solution

注意到平方后再开根相当于没进行平方，而开方后在平方则不行

我们对于线段树上每个点维护平方了多少次，区间开方时，区间内每个点都至少平方了一次，则可以直接做区间减，否则我们暴力进行开方，注意到每个数最多被开 $O(\log\log n)$ 就会变成 $1$

时间复杂度 $O(n\log n\log\log n)$

#include <iostream>
#include <cmath>
#define maxn 200010
#define ll long long
using namespace std;

const int p = 998244353;
const int pp = 998244352;

ll pow_mod(ll x, ll n, int p) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

int n, m, a[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int v, mx, add;
} T[maxn * 4];
inline void maintain(int i) {
    T[i].v = min(T[lc].v, T[rc].v);
    T[i].mx = max(T[lc].mx, T[rc].mx);
}

void build(int i, int l, int r) {
    if (l == r) return T[i] = { 0, a[l] }, void(); 
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i); 
}

inline void Update(int i, int add) {
    T[i].v += add;
    T[i].add += add;
}

inline void pushdown(int i) {
    int &add = T[i].add; if (!add) return ;
    Update(lc, add); Update(rc, add);
    add = 0; 
}

void update_sqrt(int i, int l, int r, int L, int R) {
    if (l > R || r < L || T[i].mx == 1) return ;
    if (L <= l && r <= R && T[i].v >= 1) return Update(i, -1);
    if (l == r) return T[i].mx = sqrt(T[i].mx), void(); 
    int m = l + r >> 1; pushdown(i);
    update_sqrt(lc, l, m, L, R); update_sqrt(rc, m + 1, r, L, R);
    maintain(i); 
}

void update_square(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, 1);
    int m = l + r >> 1; pushdown(i);
    update_square(lc, l, m, L, R); update_square(rc, m + 1, r, L, R);
    maintain(i); 
}

int query(int i, int l, int r) {
    if (l == r) return pow_mod(T[i].mx, pow_mod(2, T[i].v, pp), p);
    int m = l + r >> 1; pushdown(i); 
    return (query(lc, l, m) + query(rc, m + 1, r)) % p; 
}

inline void solve_1() {
    int x, y; cin >> x >> y;
    update_sqrt(1, 1, n, x, y); 
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    update_square(1, 1, n, x, y);
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2();
    } cout << query(1, 1, n) << "\n";
    return 0;
}