[라인 트리] HDOJ 5338 ZZX and Permutations
2311 단어 세그먼트 트리
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lson o << 1, L, mid
#define rson o << 1 | 1, mid+1, R
#define ls o << 1
#define rs o << 1 | 1
#define mp(x, y) make_pair(x, y)
const int maxn = 100005;
set<int> s, ss;
set<int>::iterator it;
int maxv[maxn << 2];
int List[maxn];
int pos[maxn];
int res[maxn];
int cir[maxn];
int a[maxn];
int n;
void pushup(int o)
{
maxv[o] = max(maxv[ls], maxv[rs]);
}
void build(int o, int L, int R)
{
if(L == R) {
maxv[o] = a[L];
return;
}
int mid = (L + R) >> 1;
build(lson);
build(rson);
pushup(o);
}
void update(int o, int L, int R, int q)
{
if(L == R) {
maxv[o] = -1;
return;
}
int mid = (L + R) >> 1;
if(q <= mid) update(lson, q);
else update(rson, q);
pushup(o);
}
int query(int o, int L, int R, int ql, int qr)
{
if(ql <= L && qr >= R) return maxv[o];
int mid = (L + R) >> 1, ans = -1;
if(ql <= mid) ans = max(ans, query(lson, ql, qr));
if(qr > mid) ans = max(ans, query(rson, ql, qr));
return ans;
}
void work()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pos[a[i]] = i;
}
build(1, 1, n);
s.clear();
ss.clear();
s.insert(0);
for(int i = 1; i <= n; i++) ss.insert(i);
int cnt = 0;
memset(cir, 0, sizeof cir);
memset(List, 0, sizeof List);
List[n+1] = cir[n+1] = -1;
while(cnt < n) {
int u = *ss.begin();
ss.erase(u);
cnt++;
int loc = pos[u];
int t2 = cir[loc+1] ? -1 : a[loc+1];
it = --s.upper_bound(loc);
int t1 = query(1, 1, n, (*it) + 1, loc);
if(t1 > t2) {
int loc2 = pos[t1];
List[loc] = loc2;
update(1, 1, n, loc2);
for(int i = loc2; i <= loc; i++) {
if(List[i]) continue;
List[i] = i+1;
ss.erase(a[i]);
cnt++;
update(1, 1, n, i+1);
}
cir[loc2] = cir[loc] = 1;
s.insert(loc);
}
else {
List[loc] = loc + 1;
update(1, 1, n, loc+1);
}
}
for(int i = 1; i <= n; i++) res[a[i]] = a[List[i]];
for(int i = 1; i <= n; i++) printf("%d%c", res[i], i == n ? '
' : ' ');
}
int main()
{
int _;
scanf("%d", &_);
while(_--) work();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 알고리즘 14427번 : 수열과 쿼리 15길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.