2131: 免费的馅饼
Time Limit: 10 Sec Memory Limit: 259 MB[][][]Description
Input
第一行是用空格隔开的二个正整数，分别给出了舞台的宽度W（1到10^8之间）和馅饼的个数n（1到10^5）。 接下来n行，每一行给出了一块馅饼的信息。由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻t[i]（1到10^8秒），掉到舞台上的格子的编号p[i]（1和w之间），以及分值v[i]（1到1000之间）。游戏开始时刻为0。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的t[i]和p[i]都一样。
Output
一个数，表示游戏者获得的最大总得分。
Sample Input
3 4 1 2 3 5 2 3 6 3 4 1 1 5
Sample Output
12 【数据规模】 对于100%的数据，1<=w,t[i]<=10^8,1<=n<=100000。
Solution
dp[i]表示前i个馅饼的最大答案
dp[i] = max dp[j]+vi(2ti+pi>=2tj+pj，2ti−pi>=2tj−pj)
发现是二维偏序
值域树状数组维护，要先离散化
开始还想了ti有用秀逗地认为要三维偏序，我真是naive啊
#includeusing namespace std;const int N = 100000 + 5;int w, n, c[N], q[N], ans;struct Data{ int x, y, v; }e[N];bool cmp( Data a, Data b ){ return a.x < b.x; }void update( int x, int val ){ for( int i = x; i <= n; i += i&-i ) c[i] = max( c[i], val ); }int query( int x ){ int res = 0; for( int i = x; i; i -= i&-i ) res = max( res, c[i] ); return res; }int find( int x ){ int l = 1, r = n, res; while( l <= r ){ int mid = l + r >> 1; if( q[mid] >= x ) res = mid, r = mid - 1; else l = mid + 1; } return res;}int main(){ scanf( "%d%d", &w, &n ); for( int i = 1, t, p; i <= n; i++ ) scanf( "%d%d%d", &t, &p, &e[i].v ), e[i].x = 2*t-p, e[i].y = 2*t+p, q[i] = 2*t+p; sort( e + 1, e + n + 1, cmp ); sort( q + 1, q + n + 1 ); for( int i = 1; i <= n; i++ ) e[i].y = find( e[i].y ); for( int i = 1; i <= n; i++ ){ int tmp = query( e[i].y ) + e[i].v; update( e[i].y, tmp ); ans = max( ans, tmp ); } printf( "%d\n", ans ); return 0;}