段树TLE 40pts求hack或帮调

P1253 扶苏的问题

Little_Cabbage @ 2024-01-22 10:33:13

#include <bits/stdc++.h>
#define int long long
#define ls k * 2
#define rs k * 2 + 1
using namespace std;
const int N = 1e6 + 10;
const int M = 5010;
const int MIN = -1145141919810;
struct SegmentTree {
    int l, r, add;
} SegTree[N * 4];
int n, m, a[N], Max;
void build(int k, int l, int r) {
    SegTree[k].l = l, SegTree[k].r = r;
    if (l == r) {
        SegTree[k].add = a[l];
        return ;
    }
    int mid = (l + r) / 2;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    SegTree[k].add = max(SegTree[ls].add, SegTree[rs].add);
}
void modify_I(int k, int l, int r, int c) {
    if (l > SegTree[k].r || r < SegTree[k].l) return ;
    if (l <= SegTree[k].l && SegTree[k].r <= r && SegTree[k].l == SegTree[k].r) {
        SegTree[k].add = c;
        return ;
    }
    if (SegTree[k].l == SegTree[k].r) return ;
    modify_I(ls, l, r, c);
    modify_I(rs, l, r, c);
    SegTree[k].add = max(SegTree[ls].add, SegTree[rs].add);
}
void modify_II(int k, int l, int r, int c) {
    if (l > SegTree[k].r || r < SegTree[k].l) return ;
    if (l <= SegTree[k].l && SegTree[k].r <= r && SegTree[k].l == SegTree[k].r) {
        SegTree[k].add += c;
        return ;
    }
    if (SegTree[k].l == SegTree[k].r) return ;
    modify_II(ls, l, r, c);
    modify_II(rs, l, r, c);
    SegTree[k].add = max(SegTree[ls].add, SegTree[rs].add);
}
void ask(int k, int l, int r) {
//  if (k == 10 || k == 11) cout << "ok";
    if (l > SegTree[k].r || r < SegTree[k].l) return ;
    if (l <= SegTree[k].l && SegTree[k].r <= r && SegTree[k].l == SegTree[k].r) {
        Max = max(Max, SegTree[k].add);
        return ;
    }
    if(SegTree[k].l == SegTree[k].r) return ;
    ask(ls, l, r);
    ask(rs, l, r);
}
void debug() {
    for (int i = 1; i <= 13; i++)
        cout << i << " : " << SegTree[i].l << " " << SegTree[i].r << " " << SegTree[i].add << endl;
    cout << endl;
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
//  debug();
    while (m--) {
        int opt, l, r, x;
        cin >> opt >> l >> r;
        if (opt == 1) {
            cin >> x;
            modify_I(1, l, r, x);
        } else if (opt == 2) {
            cin >> x;
            modify_II(1, l, r, x);
        } else {
            Max = MIN;
            ask(1, l, r);
            cout << Max << endl;
        }
//      debug();
    }
    return 0;
}

by banned_gutongxing @ 2024-01-22 10:52:55

emmm


by rsy_ @ 2024-01-22 15:41:38

@oier03 哇,好高级的数据结构

段数!!!我从来没有听说过这个数据结构

OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOrz


by Little_Cabbage @ 2024-01-22 16:20:15

@rsy_ 少打了一个字,线段树……


by rsy_ @ 2024-01-22 16:22:51

@oier03 我不会线段树/kel


by nxd_oxm @ 2024-01-22 22:03:39

@oier03 线段树是什么,可以吃吗


|