51NOD 1287 加农炮（不水的线段树）

》》点击进入原题测试《《

Input示例

Output示例

思路：刚开始以为结点存最大值就行了，然后大于左子树的最大值就能进入右子树；然后发现样例都过不了；后面发现，并不是这个样子，假如这个数小于等于右孩子最左边那个数的话，也不能进入有孩子，所以结点还得保存右孩子最左边的那个值；同时更新一个最大值，当输入值咸鱼等于a[0]或者大于最大值时跳过。

#include<climits>

#include<iostream>

#include<algorithm>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ll long long

const int maxn = 5e4 + ;

ll tree[maxn << ], mtree[maxn << ], a[maxn];

ll ma = INT_MIN;

void build(int l, int r, int rt)

{

    if (l == r){

        tree[rt] = a[l];

        mtree[rt] = a[l];

        return;

    }

    int m = (l + r) >> ;

    build(lson);

    build(rson);

    tree[rt] = max(tree[rt << ], tree[rt <<  | ]);

    mtree[rt] = mtree[rt << ];

}

void update(int x, int l, int r, int rt)

{

    if (l == r){

        a[l] += ;

        tree[rt] += ;

        mtree[rt] += ;

        if (a[l] > ma)ma = a[l];

        return;

    }

    int m = (l + r) >> ;

    if (tree[rt << ] < x&&x>mtree[rt <<  | ])

        update(x, rson);

    else update(x, lson);

    tree[rt] = max(tree[rt << ], tree[rt <<  | ]);

    mtree[rt] = mtree[rt << ];

}

void Print(int l, int r, int rt)

{

    if (l == r){

        cout << rt << " = " << tree[rt] << endl;

        return;

    }

    cout << rt << " = " << tree[rt] << endl;

    int m = (r + l) >> ;

    if (l <= m)Print(lson);

    if (r > m)Print(rson);

}

int main()

{

    std::ios::sync_with_stdio(false);

    int m, n; cin >> m >> n;

    for (int i = ; i <= m; i++){

        cin >> a[i];

        if (ma < a[i])ma = a[i];

    }

    build(, m, );

    int temp;

    while (n--){

        cin >> temp;

        if (temp <= a[] || temp>ma)

            continue;

        update(temp, , m, );

        //Print(1, m, 1);

    }

    for (int i = ; i <= m; i++){

        if (i != )cout << endl;

        cout << a[i];

    }

}

巴特西

51NOD 1287 加农炮（不水的线段树）

最新文章

热门文章