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
", res * pi);
   return 0;
}