Codeforces 629 D Finals in arithmetic(最大上升子序列和，O(nlogn)、线段树/树状数组)

题目链接：
Codeforces 629 D Finals in arithmetic
题意：
已知$n$块圆柱形蛋糕的底面圆半径和高，需要利用这些蛋糕尽可能堆成一个体积最大的蛋糕，但是需要满足：

• 编号大的蛋糕只能放在编号比它小的蛋糕上面或者桌子上
• 上面蛋糕的体积必须严格大于下面蛋糕的体积

求最终堆成的蛋糕的最大体积？
数据范围:$1?\leq ?n?\leq?100?000,r_i\leq 10^4,h_i\leq 10^4$.
分析：
实际上就是求最大上升子序列和。
普通的dp方法是：

$$用dp[i]表示从以位置i结尾的最大上升子序列和。\\ dp[i]=max(dp[j])+data[i]\quad (data[j]<data[i],j<i)$$
时间复杂度是 $O(n^2)$，显然这里肯定不行了。
考虑将寻找 $dp[j]$的时间优化至 $\log n$。
对于 $i$只能在满足 $data[j]<data[i]并且j<i$中找到 $j$的最大值，这样子就有了一种有序性，我们先将原有的所有体积排序，去重，离散化。假设还剩 $m$个完全不一样的体积，建立线段树，对于线段树的叶子结点就是以该叶子节点为结尾的最大上升子序列和，区间中存的是区间最大值，假设对于蛋糕 $i$的体积 $data[i]$在所有蛋糕中排在 $pos$位置，那么它只能在区间 $[1,pos-1]$中查找最大值（下标从1开始），同样我们将它更新也是更新在 $pos$位置，这样子就避免了查找原来排在 $i$之前但是体积比 $i$大的情况。
时间复杂度： $O(n\log n)$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define lson(x) (x << 1) 
#define rson(x) ((x << 1) | 1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 100010;int n;
ll data[MAX_N], extra[MAX_N];struct SegmentTree {int left, right;ll value, lazy;}segtree[MAX_N << 2];void build(int left, int right, int cur)
{segtree[cur].left = left, segtree[cur].right = right, segtree[cur].value = 0;if(left == right) return ;int mid = (left + right) >> 1;build(left, mid, lson(cur));build(mid + 1, right, rson(cur));
}ll query(int a, int b, int cur)
{if(a > b) return 0;int left = segtree[cur].left, right = segtree[cur].right;if(left == a && right == b) {return segtree[cur].value;}int mid = (left + right) >> 1;if (b <= mid) return query(a, b, lson(cur));else if (a > mid) return query(a, b, rson(cur));else return max(query(a, mid, lson(cur)), query(mid + 1, b, rson(cur)));
}void update(int goal, ll value, int cur)
{int left = segtree[cur].left, right = segtree[cur].right;if(left == right) {segtree[cur].value = max(segtree[cur].value, value);return ;}int mid = (left + right) >> 1;if(goal <= mid) update(goal, value, lson(cur));else update(goal, value, rson(cur));segtree[cur].value = max(segtree[lson(cur)].value, segtree[rson(cur)].value);
}int main()
{while (~scanf("%d", &n)) {for (int i = 1; i <= n; ++i) {ll r, h;scanf("%I64d%I64d", &r, &h);data[i] = r * r * h;extra[i] = data[i];}sort(extra + 1, extra + n + 1);int m = unique(extra + 1, extra + n + 1) - extra - 1;build(1, m, 1);ll ans = 0;for (int i = 1; i <= n; ++i) {int pos = lower_bound(extra + 1, extra + m + 1, data[i]) - extra;ll tmp = data[i] + query(1, pos - 1, 1);ans = max(ans, tmp);update(pos, tmp, 1);//printf("pos = %d ans = %I64d\n", pos, ans);}printf("%.10lf\n", ans * acos(-1.0));}return 0;
}

好像用树状数组写更方便点。。。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 100010;int n;
ll data[MAX_N], C[MAX_N], extra[MAX_N];ll GetMax(int x)
{ll res = 0;while (x) {res = max(res, C[x]);x -= (x & (-x));}return res;
}ll update(int x, ll value)
{while(x <= n) {C[x] = max(C[x], value);x += (x & (-x));}
}int main()
{while (~scanf("%d", &n)) {for(int i = 1; i <= n; ++i) {ll r, h;scanf("%I64d%I64d", &r, &h);extra[i] = data[i] = r * r * h;}sort(extra + 1, extra + n + 1);int m = unique(extra + 1, extra + n + 1) - extra - 1;memset(C, 0, sizeof(C));ll ans = 0;for (int i = 1; i <= n; ++i) {int pos = lower_bound(extra + 1, extra + m + 1, data[i]) - extra;ll tmp = GetMax(pos - 1);ans = max(ans, tmp + data[i]);update(pos, tmp + data[i]);}printf("%.10lf\n", ans * acos(-1.0));}return 0;
}