D. Babaei and Birthday Cake---cf629D(最长上升子序列和+线段树优化)

http://codeforces.com/problemset/problem/629/D

题目大意： 我第一反应就是求最长上升子序列和  但是数值太大了  不能直接dp求  可以用线段树优化一下

#include<stdio.h>

#include<string.h>

#include<stdio.h>

#include<math.h>

#include<iostream>

#include<algorithm>

using namespace std;

const long long INF = (1LL << );

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof(a))

#define N 1005000

const double pi = acos(-1.0);

#define Lson r<<1|1

#define Rson r<<1

double s[N],b[N];

struct node

{

    int L,R;

    double Max;

    int mid()

    {

        return (L+R)/;

    }

}a[N*];

void BuildTree(int r,int L,int R)

{

    a[r].L=L;

    a[r].R=R;

    a[r].Max=;

    if(L==R)

        return ;

    BuildTree(Lson,L,a[r].mid());

    BuildTree(Rson,a[r].mid()+,R);

}

double Qurry(int r,int L,int R)

{

    if(L>R)

        return ;

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

    {

        return a[r].Max;

    }

    if(L>a[r].mid())

        return Qurry(Rson,L,R);

    else if(R<=a[r].mid())

        return Qurry(Lson,L,R);

    else

    {

        double m1=Qurry(Lson,L,a[r].mid());

        double m2=Qurry(Rson,a[r].mid()+,R);

        return max(m1,m2);

    }

}

void Update(int r,int L,double ans)

{

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

    {

        a[r].Max=ans;

        return;

    }

    if(L>a[r].mid())

        Update(Rson,L,ans);

    else

        Update(Lson,L,ans);

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

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        double r,h;

        met(b,);

        met(s,);

        for(int i=;i<n;i++)

        {

            scanf("%lf %lf",&r,&h);

            s[i]=b[i]=pi*r*r*h;

        }

        sort(b,b+n);

        int len=unique(b,b+n)-b;

        BuildTree(,,len-);

        double  sum=;

        for(int i=;i<n;i++)

        {

            int pos=lower_bound(b,b+len,s[i])-b;///找到所在的下标

            double ans=Qurry(,,pos-)+s[i];///查找之前的最大值

            Update(,pos,ans);///更新点

            sum=max(sum,ans);

        }

        printf("%.12lf\n",sum);

    }

    return ;

}