Codeforces 629D Babaei and Birthday Cake（树状数组优化dp）

题意：

线段树做法

分析：

因为每次都是在当前位置的前缀区间查询最大值，所以可以直接用树状数组优化。比线段树快了12ms~

代码：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;//[)
const int maxn = 100005,  INF = 0x3fffffff;
#define pi acos(-1.0)
typedef long long ll;
ll dp[maxn];
ll tv[maxn], v[maxn];
int tot;
ll query(int pos)
{ll res = 0;while(pos > 0){res = max(res, dp[pos]);pos -= pos & - pos;}return res;
}
void update(int pos, ll x)
{while(pos <= tot){dp[pos] = max(dp[pos], x);pos += pos & - pos;}
}
int main (void)
{int n;scanf("%d",&n);int r, h;for(int i = 0; i < n; i++){scanf("%d%d",&r,&h);tv[i] = v[i] =(ll) r * r * h;}sort(tv, tv + n);tot = unique(tv, tv + n) - tv;ll res = 0;for(int i = 0; i < n; i++){int pos = lower_bound(tv, tv + tot, v[i]) - tv + 1;ll tmp = query(pos - 1) + v[i];res = max(res, tmp);update(pos, tmp);}printf("%.10lf\n", res * pi);return 0;
}