HDU 3564 Another LIS splay
빈 시퀀스 지정
n개수 삽입(1, 2, 3, 4·n 순으로 삽입)
다음 n개수는 i가 어느 위치에 꽂혀 있는지 나타낸다.
한 개의 수를 삽입한 후에 이 서열의lis를 출력합니다
그리고...
매번 삽입된 수가 현재 시퀀스에서 가장 큰 수이기 때문이다
그래서 뒤에 있는 수의 dp값에 영향을 주지 않아요.
그러면 이 위치의 dp값은 삽입 위치의 앞 최대 dp값+1입니다
그리고 이 서열의 가장 큰 dp값을 출력합니다.
==
아이디어:
splay...
Q:왜 이 문제는 splay를 사용해야 하는지, 간단한 라인 트리 아닌가
A:아이큐가 부족해서 트리를 어떻게 쓰는지 생각이 안 나요.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if(x>9) pt(x/10);
putchar(x%10+'0');
}
using namespace std;
inline int Mid(int a,int b){return (a+b)>>1;}
#define N 100010
#define L(x) tree[x].ch[0]
#define R(x) tree[x].ch[1]
#define Siz(x) tree[x].siz
#define Father(x) tree[x].fa
#define Max(x) tree[x].max
#define Val(x) tree[x].val
#define Pt(x) tree[x].pt()
struct node{
int ch[2], siz, fa;
int max, val;
void pt(){printf("val:%d max:%d siz:%d fa:%d{%d,%d}
", val,max,siz,fa,ch[0],ch[1]);}
}tree[N*2];
int tot, root;
void Newnode(int &id, int val, int fa, int siz = 1){
id = ++tot;
L(id) = R(id) = 0;
Father(id) = fa;
Siz(id) = siz;
Max(id) = Val(id) = val;
}
void push_up(int id){
Siz(id) = Siz(L(id)) + Siz(R(id)) +1;
Max(id) = max(Max(R(id)), Max(L(id)));
Max(id) = max(Val(id), Max(id));
}
void push_down(int id){}
void Rotate(int id, int kind){
int y = Father(id);
push_down(y); push_down(id); //here
tree[y].ch[kind^1] = tree[id].ch[kind];
Father(tree[id].ch[kind]) = y;
if(Father(y))
tree[Father(y)].ch[R(Father(y))==y] = id;
Father(id) = Father(y);
Father(y) = id;
tree[id].ch[kind] = y;
push_up(y);
}
void splay(int id, int goal){
push_down(id);
while(Father(id) != goal){
int y = Father(id);
if(Father(y) == goal)
Rotate(id, L(y)==id);
else
{
int kind = L(Father(y)) == y;
if(tree[y].ch[kind] == id)
{
Rotate(id, kind^1);
Rotate(id, kind);
}
else
{
Rotate(y, kind);
Rotate(id,kind);
}
}
}
push_up(id);
if(goal == 0)root = id;
}
int Get_kth(int kth, int sor){// sor k
push_down(sor);
int id = sor;
while(Siz(L(id)) != kth){
if(Siz(L(id)) > kth)
id = L(id);
else
{
kth -= (Siz(L(id))+1);
id = R(id);
}
push_down(id);
}
return id;
}
void init(){
Father(0) = L(0) = R(0) = Siz(0) = 0;
Max(0) = 0;
tot = 0;
Newnode(root, 0, 0);
Newnode(R(root), 0, root);
push_up(root);
}
void debug(int x){
printf("%d:
", x);
Pt(x);
if(L(x))
debug(L(x));
if(R(x))
debug(R(x));
}
void insert(int pos){
splay(1, 0);
int u = Get_kth(pos, 1);
// if(pos == 2){cout<<"=="; debug(root);}
int v = Get_kth(pos+1, 1);
splay(u, 0);
splay(v, root);
// if(pos == 2){cout<<"=="; debug(root);}
Newnode(L(v), max(Val(root), Max(L(root))) +1, v);
push_up(v);
push_up(u);
// printf("[%d,%d]
", u, v);
}
int n;
int main() {
int T, Cas = 1; cin>>T;
while(T--){
rd(n);
init();
// debug(root);
printf("Case #%d:
", Cas++);
for(int i = 1, m; i <= n; i++){
rd(m);
insert(m);
// printf("id:%d, pos:%d
", i, m); debug(root);
pt(Max(root)); putchar('
');
splay(tot, 0);
// puts("================");debug(root);
}/**/
puts("");
}
return 0;
}
/*
1
7
0 1 1 1 0 4 1
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.