首页 > 代码库 > Codeforces 474E - Pillars
Codeforces 474E - Pillars
一眼看上去非常像最长不下降子序列。
然后比赛的时候对每个答案长度为k的序列，维护最后一个数的最大值和最小值。
当时不知道为什么认为从长度最长倒推至前面不会太长，于是心满意足地敲了个O(n^2)。结果T了。。。
正确的做法应该用线段树维护，搜起来就是log（n）,总的就是O(N*logN);
用非递归的方法写的
只用了77ms
在目前（2014/10/7） 是最快的。
#include <iostream>#include <cstdio>using namespace std;#define ll long longconst int INF = 300009;struct node { ll key; int pos;} dtmin[INF], dtmax[INF];ll n, d, t, x, M;ll pre[INF];int f[INF], ans[INF], namax[INF], namin[INF];inline int Searchmax (int x, ll k) { while (dtmax[x].key - k >= d) { if (x > M) return dtmax[x].pos; if (dtmax[x << 1 | 1].key - k >= d) x = x << 1 | 1; else x = x << 1; } return 0;}inline int Searchmin (int x, ll k) { while (k - dtmin[x].key >= d) { if (x > M) return dtmin[x].pos; if (k - dtmin[x << 1 | 1].key >= d) x = x << 1 | 1; else x = x << 1; } return 0;}inline void modify (int x, ll k, int i) { if (dtmax[x + M].key < k) namax[x] = i, dtmax[x + M].key = k; for (int t = x + M; dtmax[t >> 1].key < k && t > 0; t >>= 1) dtmax[t >> 1] = dtmax[t]; if (dtmin[x + M].key > k) namin[x] = i, dtmin[x + M].key = k; for (int t = x + M; dtmin[t >> 1].key > k && t > 0; t >>= 1) dtmin[t >> 1] = dtmin[t];}int main() { ios::sync_with_stdio (false); cin >> n >> d; cin>>x; M = n; int tem = 0; for (int k = M; k; tem++, k >>= 1) ; M = 1 << tem; for (int i = 0; i < (M << 1) + 10; i++) { dtmax[i].key = 0 , dtmin[i].key = (1LL << 60); dtmax[i].pos = i - M, dtmin[i].pos = i - M; } dtmax[1].key = dtmin[1].key = x; t = f[1] = 1; modify (t, x, 1); for (int i = 2,k; i <= n; i++) { cin >> x; if (k = Searchmax (1, x) ) if (f[i] < k + 1) f[i] = k + 1, pre[i] = namax[k]; if ((k = Searchmin (1, x))) if (f[i] < k + 1) f[i] = k + 1, pre[i] = namin[k]; if (f[i] > t) t = f[i]; if (f[i] == 0) f[i] = 1; modify (f[i], x, i); } cout << t << endl; int p = -1; for (int i = 1; i <= n; i++) if (f[i] == t) { p = i; break; } for (int i = t; i; i--) ans[i] = p, p = pre[p]; for (int i = 1; i <= t; i++) cout << ans[i] << ‘ ‘;}
Codeforces 474E - Pillars
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。