D. Babaei and Birthday Cake---cf629D（LIS线段树优化）

题目链接：http://codeforces.com/problemset/problem/629/D

题意就是现有n个蛋糕，蛋糕的形状是圆柱体，每个蛋糕的体积就是圆柱体的体积，每个蛋糕的编号是1---n，可以把蛋糕 i 放到蛋糕 j 上面，前提是 j<i 并且 Vj<Vi;最后求最大的体积是多少；

实质就是求上升子序列的最大和，但是由于n的范围是10w所以不能用n^2的复杂度，所以可以用线段树进行优化,时间复杂度变为nlogn；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
#define PI 4*atan(1.0)
#define N 302000
#define met(a, b) memset(a, b, sizeof(a))

#define Lson r<<1
#define Rson r<<1|1

double v[N], b[N];

struct node
{
    int L, R;
    double Max;///表示这个区间内的最大值，
    int Mid(){ return (L+R)/2; }
}a[N*4];

void Build(int r, int L, int R)
{
    a[r].L = L, a[r].R = R;a[r].Max = 0;
    if(L == R)return;
    Build(Lson, L, a[r].Mid());
    Build(Rson, a[r].Mid()+1, R);
}

double Query(int r, int L, int R)
{
    if(L > R) return 0;

    if(a[r].L == L && a[r].R == R)
        return a[r].Max;

    if(R <= a[r].Mid())
        return Query(Lson, L, R);
    else if(L > a[r].Mid())
        return Query(Rson, L, R);
    else
    {
        double ans1 = Query(Lson, L, a[r].Mid());
        double ans2 = Query(Rson, a[r].Mid()+1, R);
        return max(ans1, ans2);
    }
}

void Update(int r, int pos, double num)
{
    if(a[r].L == a[r].R && a[r].L == pos)
    {
        a[r].Max = num;
        return ;
    }
    if(pos <= a[r].Mid())
        Update(Lson, pos, num);
    else
        Update(Rson, pos, num);

    a[r].Max = max(a[Lson].Max, a[Rson].Max);
}

int main()
{
    int n;
    LL r, h;
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%I64d %I64d", &r, &h);
            v[i] = b[i] = PI*h*r*r;
        }
        sort(b, b+n);
        int len = unique(b, b+n) - b;

        Build(1, 1, len);

        double ans = 0;
        for(int i=1; i<=n; i++)
        {
            int pos = lower_bound(b, b+len, v[i]) - b;///每次找到当前这个数能放的位置；
            double res = Query(1, 1, pos-1) + v[i];///找到这个位置之前的最大值
            Update(1, pos, res);///找到之后把这个值加到那个位置上
            ans = max(ans, res);
        }
        printf("%.12f
", ans);
    }
    return 0;
}