http://www.lightoj.com/volume_problemstat.php?problem=1277
LightOJ搞得挺漂亮的，第一次到那里交题，挺喜欢的。
线段树统计题，题意是：给出一行数，找到所要求的长度的单调上升子序列，并输出该序列。
这题我是先从后往前，求出到达某个位置的时候，最长可以构建出多长的单调上升子序列。这是一个dp问题，不过用dp方法复杂度是O(n^2)会超时，所以我用线段树来降低查找的复杂度。题目比较简单，不过数据范围较大，所以要用hash来离散化处理。最后回溯一下就可以搜索出目标序列了！
代码如下：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 typedef vector vi; 10 const int hashSize = 400009; 11 const int HASH = 0x55555555; 12 int hash[hashSize], hashPos[hashSize]; 13 vi buf, X; 14 15 void insHash(int x, int pos) { 16 int p = (x ^ HASH) % hashSize; 17 18 if (p < 0) p += hashSize; 19 while (hash[p] != x && ~hashPos[p]) { 20 p++; 21 if (p >= hashSize) p -= hashSize; 22 } 23 24 hash[p] = x; 25 hashPos[p] = pos; 26 } 27 28 int getPos(int x) { 29 int p = (x ^ HASH) % hashSize; 30 31 if (p < 0) p += hashSize; 32 while (hash[p] != x && ~hashPos[p]) { 33 p++; 34 if (p >= hashSize) p -= hashSize; 35 } 36 37 return hashPos[p]; 38 } 39 40 void initHash() { 41 memset(hashPos, -1, sizeof(hashPos)); 42 } 43 44 void scan(int &x) { 45 char c; 46 47 for ( ; ((c = getchar()) < '0' || c > '9') && c != '-'; ) ; 48 if (c != '-') for (x = c - '0'; '0' <= (c = getchar()) && c <= '9'; x = x * 10 + c - '0') ; 49 else for (x = 0; '0' <= (c = getchar()) && c <= '9'; x = x * 10 + '0' - c) ; 50 } 51 52 int treeSize; 53 54 void input(int n) { 55 int x; 56 57 X.clear(); 58 buf.clear(); 59 initHash(); 60 61 while (n--) { 62 scan(x); 63 X.push_back(x); 64 buf.push_back(x); 65 } 66 sort(X.begin(), X.end()); 67 68 int endi = unique(X.begin(), X.end()) - X.begin(); 69 70 treeSize = endi; 71 for (int i = 0; i < endi; i++) { 72 insHash(X[i], i); 73 } 74 } 75 76 #define lson l, m, rt << 1 77 #define rson m + 1, r, rt << 1 | 1 78 #define ROOT 0, treeSize - 1, 1 79 80 const int maxn = 100001; 81 int mx[maxn << 2]; 82 83 void build(int l, int r, int rt) { 84 mx[rt] = 0; 85 if (l == r) return ; 86 87 int m = (l + r) >> 1; 88 89 build(lson); 90 build(rson); 91 mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]); 92 } 93 94 void update(int p, int x, int l, int r, int rt) { 95 if (l == r) { 96 mx[rt] = max(mx[rt], x); 97 return ; 98 } 99 int m = (l + r) >> 1;100 101 if (p <= m) update(p, x, lson);102 else update(p, x, rson);103 mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);104 }105 106 int query(int L, int R, int l, int r, int rt) {107 if (L <= l && r <= R) {108 return mx[rt];109 }110 int m = (l + r) >> 1;111 112 if (L <= m) {113 if (m < R) {114 return max(query(L, R, lson), query(L, R, rson));115 } else {116 return query(L, R, lson);117 }118 }119 if (m < R) {120 return query(L, R, rson);121 }122 }123 124 int maxLen[maxn];125 126 void deal(int n, int m) {127 input(n);128 build(ROOT);129 for (int i = n - 1; i >= 0; i--) {130 int pos = getPos(buf[i]) + 1;131 132 // printf("~%d\n", pos);133 if (pos < treeSize) {134 maxLen[i] = query(pos, treeSize - 1, ROOT) + 1;135 update(pos - 1, maxLen[i], ROOT);136 } else {137 maxLen[i] = 1;138 update(pos - 1, maxLen[i], ROOT);139 }140 // printf("%d ", maxLen[i]);141 }142 // puts("~~~");143 144 while (m--) {145 int x, i = 0;146 147 scan(x);148 while (i < n) {149 if (maxLen[i] >= x) break;150 i++;151 }152 if (i >= n) puts("Impossible");153 else {154 int last = buf[i];155 156 printf("%d", buf[i]);157 x--;158 i++;159 while (x) {160 if (maxLen[i] >= x && buf[i] > last) {161 printf(" %d", buf[i]);162 x--;163 last = buf[i];164 }165 i++;166 }167 puts("");168 }169 }170 }171 172 int main() {173 int n, m;174 int T;175 176 // freopen("in", "r", stdin);177 scan(T);178 for (int i = 1; i <= T; i++) {179 printf("Case %d:\n", i);180 scan(n);181 scan(m);182 deal(n, m);183 }184 185 return 0;186 }
——written by Lyon