本文主要是介绍FZU 2136 取糖果（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
FZU 2136 取糖果
题目链接
题意：中文题
思路：线段树，先把所有糖果按价值排序，然后线段树结点表示糖果有无，如果当前找不到一个连续段满足长度，就继续加糖果，如果满足，答案就是最后加入的那个糖果，利用线段树的区间合并去找连续段长度
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 100005;
struct Candy {int val, id;
} c[N];bool cmp(Candy a, Candy b) {return a.val < b.val;
}int t, n;#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)struct Node {int l, r, lsum, rsum, sum;int size() {return r - l + 1;}
} node[4 * N];void build(int l, int r, int x = 0) {node[x].l = l; node[x].r = r;node[x].lsum = node[x].rsum = node[x].sum = 0;if (l == r) return;int mid = (l + r) / 2;build(l, mid, lson(x));build(mid + 1, r, rson(x));
}void pushup(int x) {node[x].lsum = node[lson(x)].lsum;node[x].rsum = node[rson(x)].rsum;node[x].sum = max(node[lson(x)].sum, node[rson(x)].sum);if (node[lson(x)].lsum == node[lson(x)].size())node[x].lsum += node[rson(x)].lsum;if (node[rson(x)].rsum == node[rson(x)].size())node[x].rsum += node[lson(x)].rsum;node[x].sum = max(node[x].sum, node[lson(x)].rsum + node[rson(x)].lsum);
}void add(int v, int x = 0) {if (node[x].l == node[x].r) {node[x].sum = node[x].lsum = node[x].rsum = 1;return;}int mid = (node[x].l + node[x].r) / 2;if (v <= mid) add(v, lson(x));if (v > mid) add(v, rson(x));pushup(x);
}int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);build(1, n);for (int i = 1; i <= n; i++) {scanf("%d", &c[i].val);c[i].id = i;}sort(c + 1, c + n + 1, cmp);int u = 1;for (int i = 1; i <= n; i++) {while (node[0].sum < i) add(c[u++].id);printf("%d\n", c[u - 1].val);}}return 0;
}这篇关于FZU 2136 取糖果（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
