HDU 3564 Another LIS splay

4248 단어
제목:
빈 시퀀스 지정
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 */

좋은 웹페이지 즐겨찾기