透彻血堂

Posted on In

题目大意：动态维护区间最大子段和

看到区间，考虑线段树，ST表，差分一系列的数据结构

然后看到最大子段和筛选出用线段树

我们维护多个变量分别如下：

tag :区间标记，1退房0开房

lmax:紧靠左侧的最大子段和

rmax:紧靠右侧的最大子段和

dat:整个区间的最大子段和

len:区间长度

其实线段树最主要的就是考虑up，down

考场上就是卡在了不知道怎么维护l，rmax上

出了组数据把自己hack了发现区间的lmax为什么不仅仅是左儿子的lmax还有右儿子的lmax考场上当时第一题没写出来心里很**

所以就弃疗了

现在想想也没什么，再手跑一下其实就出来了

然后还有一个很精彩的地方就是求最大子段和的左端点，不同于正常的线段树

直接分为左儿子，右儿子，中间三部分

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5e4 + 66;

int n, m;

struct SEGMENTTREE
{
    int lmax, rmax, dat, tag, len;
}tree[N << 2];

inline void up(int p)
{
    int l = p << 1, r = (p << 1) | 1;
    tree[p].lmax = (tree[l].lmax == tree[l].len) ? tree[l].lmax + tree[r].lmax : tree[l].lmax;
    tree[p].rmax = (tree[r].rmax == tree[r].len) ? tree[r].rmax + tree[l].rmax : tree[r].rmax;
    return (void)(tree[p].dat = max(max(tree[l].dat, tree[r].dat), tree[l].rmax + tree[r].lmax));
}

inline void down(int p)
{
    if (! tree[p].tag) return;
    int l = p << 1, r = (p << 1) | 1, c = tree[p].tag;
    tree[l].tag = tree[r].tag = c;
    tree[l].dat = tree[l].lmax = tree[l].rmax = (c == 1) ? tree[l].len : 0;
    tree[r].dat = tree[r].lmax = tree[r].rmax = (c == 1) ? tree[r].len : 0;
    return (void)(tree[p].tag = 0);
}

inline void build(int p, int l, int r)
{
    tree[p].dat = tree[p].lmax = tree[p].rmax = tree[p].len = r - l + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    return (void)(up(p));
}

inline void updata(int p, int l, int r, int nl, int nr, int c)
{
    if (nl <= l && nr >= r)
    {
        tree[p].dat = tree[p].lmax = tree[p].rmax = (c == 1) ? tree[p].len : 0;
        return (void)(tree[p].tag = c);
    }
    down(p);
    int mid = (l + r) >> 1;
    if (nl <= mid) updata(p << 1, l, mid, nl, nr, c);
    if (nr > mid) updata((p << 1) | 1, mid + 1, r, nl, nr, c);
    return (void)(up(p));
}

inline int query(int p, int l, int r, int c)
{
    if (l == r) return l;
    down(p);
    int mid = (l + r) >> 1;
    if (tree[p << 1].dat >= c) return query(p << 1, l, mid, c);
    if (tree[p << 1].rmax + tree[(p << 1) | 1].lmax >= c) return mid - tree[p << 1].rmax + 1;
    return query((p << 1) | 1, mid + 1, r, c);
}

signed main()
{
    int i, x, y, opt;
    n = read(), m = read();
    build(1, 1, n);

    for (i = 1; i <= m; ++ i)
    {
        opt = read(), x = read();
        if (opt == 1)
        {
            if (tree[1].dat < x) put(0);
            else 
            {
                int id = query(1, 1, n, x);
                updata(1, 1, n, id, id + x - 1, 2);
                put(id);
            }
        }
        if (opt == 2) y = read(), updata(1, 1, n, x, x + y - 1, 1);
    }

    return 0;
}