首页 > 代码库 > fzu 2136 取糖果(线段树)
fzu 2136 取糖果(线段树)
题目链接:fzu 2136 2136 取糖果
题目大意:略。
解题思路:线段树区间合并。将袋子按照个数排序,每次将最小的放入线段树,如果当前连续的个数超过区间,那么说
明最小值即为最后加入的袋子糖果个数。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], L[maxn << 2], R[maxn << 2], S[maxn << 2];
void pushup(int u) {
S[u] = max(max(S[lson(u)], S[rson(u)]), R[lson(u)] + L[rson(u)]);
L[u] = L[lson(u)] + (L[lson(u)] == rc[lson(u)] - lc[lson(u)] + 1 ? L[rson(u)] : 0);
R[u] = R[rson(u)] + (R[rson(u)] == rc[rson(u)] - lc[rson(u)] + 1 ? R[lson(u)] : 0);
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
L[u] = R[u] = S[u] = 0;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify(int u, int x, int w) {
if (lc[u] == x && x == rc[u]) {
S[u] = R[u] = L[u] = w ? rc[u] - lc[u] + 1 : 0;
return;
}
int mid = (lc[u] + rc[u]) >> 1;
if (x <= mid)
modify(lson(u), x, w);
else
modify(rson(u), x, w);
pushup(u);
}
typedef pair<int, int> pii;
vector<pii> vec;
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
int n, x;
vec.clear();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
vec.push_back(make_pair(x, i));
}
sort(vec.begin(), vec.end());
build(1, 1, n);
int mv = 0;
for (int k = 1; k <= n; k++) {
while (S[1] < k)
modify(1, vec[mv++].second, 1);
printf("%d\n", vec[mv-1].first);
}
}
return 0;
}
fzu 2136 取糖果(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。