hdu 3564 Another LIS （Splay Tree OR Segment Tree）

Problem - 3564

　　好不容易看见一道可以用Splay Tree写的题，结果应该是常数过大超时了。

　　好不容易还是给我找到bug了，就是一个字母打错，导致超时了。splay tree可以以421ms的时间完美通过。做法就是模拟插入数字，维护区间的最大LIS值即可。

Splay版代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 
  6 using namespace std;
  7 
  8 const int inf = 0x77777777;
  9 
 10 struct Node {
 11     int data, cnt, max, val;
 12     Node *c[2], *p;
 13     Node(int data = 0, int val = 0, int cnt = 0) : data(data), val(val), cnt(cnt) {
 14         c[0] = c[1] = p = NULL;
 15         max = 0;
 16     }
 17 } *Null, *Root, *Head, *Tail;
 18 
 19 void up(Node *x) {
 20     Node *nl = x->c[0], *nr = x->c[1];
 21     x->max = max(nl->max, nr->max);
 22     x->max = max(x->max, x->val);
 23     x->cnt = nl->cnt + nr->cnt + 1;
 24 }
 25 
 26 void rotate(Node *x, bool right) {
 27     Node *y = x->p;
 28     bool left = !right;
 29     y->c[left] = x->c[right];
 30     if (x->c[right] != Null) x->c[right]->p = y;
 31     x->p = y->p;
 32     if (y->p != Null) {
 33         if (y->p->c[0] == y) {
 34             y->p->c[0] = x;
 35         } else {
 36             y->p->c[1] = x;
 37         }
 38     }
 39     x->c[right] = y;
 40     y->p = x;
 41     if (y == Root) Root = x;
 42     up(y);
 43 }
 44 
 45 void splay(Node *x, Node *f) {
 46     while (x->p != f) {
 47         if (x->p->p == f) {
 48             if (x->p->c[0] == x) {
 49                 rotate(x, 1);
 50             } else {
 51                 rotate(x, 0);
 52             }
 53         } else {
 54             Node *y = x->p, *z = y->p;
 55             if (z->c[0] == y) {
 56                 if (y->c[0] == x) {
 57                     rotate(y, 1);
 58                     rotate(x, 1);
 59                 } else {
 60                     rotate(x, 0);
 61                     rotate(x, 1);
 62                 }
 63             } else {
 64                 if (y->c[0] == x) {
 65                     rotate(x, 1);
 66                     rotate(x, 0);
 67                 } else {
 68                     rotate(y, 0);
 69                     rotate(x, 0);
 70                 }
 71             }
 72         }
 73     }
 74     up(x);
 75 }
 76 
 77 Node *getPos(int pos) {
 78 //    cout << pos << "??" << endl;
 79     Node *p = Root;
 80     pos++;
 81 //    cout << p->cnt << ' ' << p->data << ' ' << pos << endl;
 82 //    cout << p->c[0]->cnt << ' ' << p->c[0]->data << ' ' << pos << endl;
 83     while (true) {
 84         int cnt = p->c[0]->cnt;
 85 //        cout << cnt << ' ' << pos << endl;
 86         if (pos == cnt + 1) {
 87             break;
 88         } else if (pos <= cnt) {
 89             p = p->c[0];
 90         } else {
 91             pos -= cnt + 1;
 92             p = p->c[1];
 93         }
 94     }
 95     return p;
 96 }
 97 
 98 void inTra(Node *x) {
 99     if (x == Null) return ;
100     inTra(x->c[0]);
101     cout << x->data << ' ';
102     inTra(x->c[1]);
103 }
104 
105 void insPos(int elem, int val, int pos) {
106 //    cout << "here " << pos << endl;
107 //    inTra(Root);
108     Node *pl = getPos(pos), *pr = getPos(pos + 1);
109 //    cout << pl->data << "= =" << pr->data << " ~~ " << pl->cnt << "!!" << pr->cnt << endl;
110     Node *tmp = new Node(elem, val, 1);
111     splay(pl, Null);
112     splay(pr, pl);
113     pr->c[0] = tmp;
114     tmp->p = pr;
115     tmp->c[0] = tmp->c[1] = Null;
116     splay(tmp, Null);
117 }
118 
119 void init() {
120     Null = new Node();
121     Head = Root = new Node(inf, 0, 2);
122     Tail = new Node(inf, 0, 1);
123     Root->c[1] = Tail;
124     Root->c[0] = Root->p = Null;
125     Tail->p = Root;
126     Tail->c[0] = Tail->c[1] = Null;
127 }
128 
129 int getMax(int pos) {
130     Node *pl = getPos(0), *pr = getPos(pos + 1);
131 //    cout << pl->data << "= =" << pr->data << endl;
132     splay(pl, Null);
133     splay(pr, pl);
134 //    inTra(Root);
135 //    cout << "tra~~" << endl;
136     pr = pr->c[0];
137     if (pr == Head || pr == Tail) return 0;
138     return pr->max;
139 }
140 
141 int main() {
142 //    freopen("in", "r", stdin);
143     int n, T, x;
144     scanf("%d", &T);
145     for (int cas = 1; cas <= T; cas++) {
146         init();
147         scanf("%d", &n);
148         printf("Case #%d:\n", cas);
149         int LIS = 0;
150         for (int i = 1; i <= n; i++) {
151             scanf("%d", &x);
152             int tmp = getMax(x);
153 //            cout << "tmp " << tmp << endl;
154             LIS = max(LIS, tmp + 1);
155             printf("%d\n", LIS);
156 //            cout << "can not insert?" << endl;
157             insPos(i, tmp + 1, x);
158 //            cout << "no!!" << endl;
159 //            inTra(Root);
160 //            puts("");
161         }
162         puts("");
163     }
164     return 0;
165 }
View Code

线段树的之后补上。

UPD:

　　解释一下我的线段树法的操作。首先，我把插入的位置倒序插入线段树中，从而得到每个数最终的位置。然后再正序模拟插入过程，更新LIS的值。

线段树版本：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 
  6 using namespace std;
  7 
  8 #define lson l, m, rt << 1
  9 #define rson m + 1, r, rt << 1 | 1
 10 
 11 const int N = 111111;
 12 int mx[N << 2], cnt[N << 2];
 13 
 14 void up1(int rt) {
 15     cnt[rt] = cnt[rt << 1] + cnt[rt << 1 | 1];
 16 }
 17 
 18 void build1(int l, int r, int rt) {
 19     if (l == r) {
 20         cnt[rt] = 1;
 21         return ;
 22     }
 23     int m = l + r >> 1;
 24     build1(lson);
 25     build1(rson);
 26     up1(rt);
 27 }
 28 
 29 int ins1(int x, int l, int r, int rt) {
 30     if (l == r) {
 31         cnt[rt] = 0;
 32         return l;
 33     }
 34     int m = l + r >> 1, ret;
 35     if (cnt[rt << 1] >= x) {
 36         ret = ins1(x, lson);
 37     } else {
 38         ret = ins1(x - cnt[rt << 1], rson);
 39     }
 40     up1(rt);
 41     return ret;
 42 }
 43 
 44 int rec[N], id[N];
 45 
 46 void PRE(int n) {
 47     for (int i = 0; i < n; i++) scanf("%d", &rec[i]);
 48     build1(0, n - 1, 1);
 49     for (int i = n - 1; i >= 0; i--) id[i] = ins1(rec[i] + 1, 0, n - 1, 1);
 50 //    for (int i = 0; i < n; i++) cout << i << " : " << id[i] << ' ' << rec[i] << endl;
 51 }
 52 
 53 void up2(int rt) {
 54     mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
 55 }
 56 
 57 void build2(int l, int r, int rt) {
 58     cnt[rt] = mx[rt] = 0;
 59     if (l == r) return ;
 60     int m = l + r >> 1;
 61     build2(lson);
 62     build2(rson);
 63 }
 64 
 65 void ins2(int x, int val, int l, int r, int rt) {
 66     if (l == r) {
 67         mx[rt] = val;
 68         return ;
 69     }
 70     int m = l + r >> 1;
 71     if (x <= m) ins2(x, val, lson);
 72     else ins2(x, val, rson);
 73     up2(rt);
 74 }
 75 
 76 int query2(int L, int R, int l, int r, int rt) {
 77     if (L <= l && r <= R) {
 78         return mx[rt];
 79     }
 80     int m = l + r >> 1, ret = 0;
 81     if (L <= m) ret = max(ret, query2(L, R, lson));
 82     if (m < R) ret = max(ret, query2(L, R, rson));
 83     return ret;
 84 }
 85 
 86 void work(int n) {
 87     int tmp, curMax = 0;
 88     build2(0, n - 1, 1);
 89     for (int i = 0; i < n; i++) {
 90         tmp = query2(0, id[i], 0, n - 1, 1);
 91         curMax = max(curMax, tmp + 1);
 92         printf("%d\n", curMax);
 93         ins2(id[i], tmp + 1, 0, n - 1, 1);
 94     }
 95 }
 96 
 97 int main() {
 98 //    freopen("in", "r", stdin);
 99     int T, n;
100     scanf("%d", &T);
101     for (int i = 1; i <= T; i++) {
102         scanf("%d", &n);
103         printf("Case #%d:\n", i);
104         PRE(n);
105         work(n);
106         puts("");
107     }
108     return 0;
109 }
View Code

——written by Lyon

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/LyonLys/p/hdu_3564_Lyon.html