》》點(diǎn)擊進(jìn)入原題測(cè)試《《

Input示例
9 11
1
2
0
4
3
2
1
5
7
2
8
0
7
6
5
3
4
5
6
5
Output示例
2
2
2
4
3
3
5
6
7

思路：剛開始以為結(jié)點(diǎn)存最大值就行了，然后大于左子樹的最大值就能進(jìn)入右子樹；然后發(fā)現(xiàn)樣例都過不了；后面發(fā)現(xiàn)，并不是這個(gè)樣子，假如這個(gè)數(shù)小于等于右孩子最左邊那個(gè)數(shù)的話，也不能進(jìn)入有孩子，所以結(jié)點(diǎn)還得保存右孩子最左邊的那個(gè)值；同時(shí)更新一個(gè)最大值，當(dāng)輸入值咸魚等于a[0]或者大于最大值時(shí)跳過。

#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 + 5;
ll tree[maxn << 2], mtree[maxn << 2], 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) >> 1;build(lson);build(rson);tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);mtree[rt] = mtree[rt << 1];
}
void update(int x, int l, int r, int rt)
{if (l == r){a[l] += 1;tree[rt] += 1;mtree[rt] += 1;if (a[l] > ma)ma = a[l];return;}int m = (l + r) >> 1;if (tree[rt << 1] < x&&x>mtree[rt << 1 | 1])update(x, rson);else update(x, lson);tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);mtree[rt] = mtree[rt << 1];
}
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) >> 1;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 = 1; i <= m; i++){cin >> a[i];if (ma < a[i])ma = a[i];}build(1, m, 1);int temp;while (n--){cin >> temp;if (temp <= a[1] || temp>ma)continue;update(temp, 1, m, 1);//Print(1, m, 1);    
    }for (int i = 1; i <= m; i++){if (i != 1)cout << endl;cout << a[i];}}

?

轉(zhuǎn)載于:https://www.cnblogs.com/zengguoqiang/p/9385192.html

總結(jié)

以上是生活随笔為你收集整理的51NOD 1287 加农炮（不水的线段树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。