题解：AT_abc255_h [ABC255Ex] Range Harvest Query

Left_i_Forever · 2025-12-15 21:29:06 · 题解

调了若干时间，大脑不够清晰吧，最开始逻辑都有问题，吃了 11 发罚时（本题请勿 #define int long long）。

线段树维护一下内容： ::::info[node of segment_tree]{open}

• ::::

可以放到线段树上做。每次询问前，给根节点打上懒标记，加上从上次询问到现在，树又长了多少天。然后开始查询。

查询正常查，到返回的区间时打上标记，把这个区间清空，回去的时候也要 pushup。

#include <bits/stdc++.h>
// #define int long long
#define x first
#define y second
#define ls(u) tr[u].ls 
#define rs(u) tr[u].rs 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 2e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
const int mod = 998244353, v2 = 499122177;//逆元
struct node
{
    int ls, rs;
    int val, tag;
    bool tag0;
} tr[N * 200];//没具体算，但是得开大点
int idx = 1, root = 1;
ll sum(ll l, ll r, ll k)
{return ((l + r) % mod) * ((r - l + 1) % mod) % mod * v2 % mod * (k % mod) % mod;}//等差数列求和公式

void pushdown(int u, ll l, ll r)
{
    int& tag = tr[u].tag;
    bool& tag0 = tr[u].tag0;
    if (!ls (u)) ls (u) = ++idx;
    if (!rs (u)) rs (u) = ++idx;
    if (tag0)
    {
        tr[ls (u)].tag0 = tr[rs (u)].tag0 = true;
        tr[ls (u)].val = tr[rs (u)].val = 0;
        tr[ls (u)].tag = tr[rs (u)].tag = 0;
        tag0 = false;
    }
    if (!tag) return;
    ll mid = l + r >> 1;
    tr[ls (u)].val += sum (l, mid, tag); tr[ls (u)].val %= mod;
    tr[rs (u)].val += sum (mid + 1, r, tag); tr[rs (u)].val %= mod;
    tr[ls (u)].tag += tag; tr[ls (u)].tag %= mod;
    tr[rs (u)].tag += tag; tr[rs (u)].tag %= mod;
    tag = 0;
}
int query(int u, ll L, ll R, ll l, ll r)
{
    // if (R - L + 1 <= 8)
    //     cout << " " << L << " " << R << " " << tr[u].val << "\n";
    if (l <= L && R <= r)
    {
        int val = tr[u].val;
        tr[u].val = tr[u].tag = 0;
        tr[u].tag0 = true;
        return val % mod;
    }
    pushdown (u, L, R);
    ll mid = L + R >> 1, ans = 0;
    if (l <= mid) ans += query (ls (u), L, mid, l, r);
    if (r > mid) ans += query (rs (u), mid + 1, R, l, r);
    tr[u].val = (tr[ls (u)].val + tr[rs (u)].val) % mod;
    return ans % mod;
}
signed main()
{
    cin.tie (0);
    ios::sync_with_stdio (false);
    ll n, q;
    cin >> n >> q;
    ll last = 0;
    while (q--)
    {
        ll l, r, k;
        cin >> k >> l >> r;
        tr[root].val += sum (1, n, (k - last) % mod);
        tr[root].val %= mod;
        tr[root].tag += (k - last) % mod;
        tr[root].tag %= mod;
        cout << (query (root, 1, n, l, r) + mod) % mod << "\n";
        last = k;
    }
    return 0;
}
// void change(int& u, int L, int R, int l, int r, int k)
// {
//     // if (R - L + 1 <= 8)
//     //     cout << "-" << L << " " << R << " " << tr[u].val << "\n";
//     if (!u) u = ++idx;
//     if (l <= L && R <= r)
//     {
//         tr[u].val += sum (L, R, k);
//         tr[u].tag += k;
//         return;
//     }
//     pushdown (u, L, R);
//     int mid = L + R >> 1;
//     if (l <= mid) change (ls (u), L, mid, l, r, k);
//     if (r > mid) change (rs (u), mid + 1, R, l, r, k);
//     tr[u].val = (tr[ls (u)].val + tr[rs (u)].val) % mod;
// }