题意：做蛋糕，给出N个半径，和高的圆柱，要求后面的体积比前面大的可以堆在前一个的上面，求最大的体积和。
思路：首先离散化蛋糕体积，以蛋糕数量建树建树，每个节点维护最大值，也就是假如节点i放在最上层情况下的体积最大值dp[i]。每次查询比蛋糕i小且最大体积的蛋糕，然后更新线段树。注意此题查询的技巧！！查询区间不变l,r,才能保证每次查到的是小且最大体积。
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#define clc(a,b) memset(a,b,sizeof(a))
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1e5 + ;
const int inf=0x3f3f3f3f;
const double pi=acos(-);
double dp[maxn];
double v[maxn],f[maxn];
int num[maxn];
struct node
{
double r,h;
} p[maxn]; double V(node a)
{
return a.r*a.r*a.h*pi;
} struct Node
{
int l,r;
double maxx;
} tree[*]; void pushup(int cnt)
{
tree[cnt].maxx=max(tree[cnt<<].maxx,tree[cnt<<|].maxx);
} void b_tree(int l,int r,int rt)
{
tree[rt].l=l;
tree[rt].r=r;
if(l==r)
{
tree[rt].maxx=0.0;
return ;
}
int mid=(l+r)>>;
b_tree(l,mid,rt<<);
b_tree(mid+,r,rt<<|);
pushup(rt);
} double query(int l,int r,int rt)
{
if(tree[rt].l>=l&&tree[rt].r<=r)
{
return tree[rt].maxx;
}
int mid=(tree[rt].l+tree[rt].r)>>;
double ans=0.0;
if(l<=mid)
ans=max(ans,query(l,r,rt<<));
if(r>mid)
ans=max(ans,query(l,r,rt<<|));
return ans;
} void update(int x,double val,int rt)
{
if(tree[rt].l==x&&tree[rt].r==x)
{
tree[rt].maxx=max(tree[rt].maxx,val);
return;
}
int mid=(tree[rt].l+tree[rt].r)>>;
if(x<=mid)
update(x,val,rt<<);
else
update(x,val,rt<<|);
pushup(rt);
} int main()
{
int n;
while(cin>>n)
{
b_tree(,n,);
clc(dp,);
for(int i=; i<n; i++)
{
scanf("%lf%lf",&p[i].r,&p[i].h);
v[i]=V(p[i]);
f[i]=v[i];
}
sort(f,f+n);
for(int i=; i<n; i++)
{
num[i]=lower_bound(f,f+n,v[i])-f+;
}
for(int i=; i<n; i++)
{
if(num[i]-==)
dp[i]=v[i];
else
dp[i]=query(,num[i]-,)+v[i];
update(num[i],dp[i],);
}
double ans=0.0;
for(int i=; i<n; i++)
ans=max(ans,dp[i]);
printf("%.10f\n",ans);
}
return ;
}