CF 269D Maximum Wate易做图ll(线段树，DP)
题目：给出一些墙，水从高往低流，每次只能到达一面墙，选择一个路径，使得路径上的流量的最小值最大。
http://codeforces.com/problemset/problem/269/D
首先主要的是题意的理解问题。
像上图这种情况的话，1是可以流向2的，1也是可以流向3的。
我开始的理解是1不能流向2，因为中间有3的阻挡，其实只是看公共部分的。
像这种情况1是不能流向2的，因为1和2的公共部分有3的阻挡。
理解这点之后，便好办了。
按高度排序之后，将所有的坐标离散化。
按高度将线段插入到线段树中，线段树中维护这个区间最高的一条线段的标号，也就是标号的最大值。
对于线段3进行一次查询之后，发现这段区间最后一次覆盖的应该是线段2，但是线段3并非完全覆盖于线段2的。
便可以继续查询绿色部分。
像左图，查询结果应该是线段1，所以3 是可以流向2，也是可以流向1的，这里用dp做一次最优解就行了。
但是注意上面右图的情况，查询绿色部分，得到线段1，但是线段1的右端超过了绿色的右端，根据我们之前的查询知道，绿色右端已经被2覆盖，所以这时候要对两端作一个标记，标明不能超过端点
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define test puts("OK");
#define inf 1000000000
#define lson (step<<1)
#define rson (step<<1|1)
using namespace std;
const int N=100005;
struct Wall{
int h,l,r;
Wall(){}
Wall(int _h,int _l,int _r):h(_h),l(_l),r(_r){}
bool operator<(const Wall w)const{
return h<w.h;
}
}wall[N];
struct Seg_Tree{
int left,right;
int val,all;
}L[N<<3];
int n,t;
int x[N<<1],cnt; //离散化
int dp[N]={0};
void Bulid(int step,int l,int r){
L[step].left=l;
L[step].right=r;
L[step].val=L[step].all=-1;
if(l==r) return ;
int m=(l+r)>>1;
Bulid(lson,l,m);
Bulid(rson,m+1,r);
}
void Push_Down(int step){
if(L[step].all!=-1){
L[lson].all=L[rson].all=L[step].all;
L[lson].val=L[rson].val=L[step].all;
L[step].all=-1;
}
}
void Push_Up(int step){
L[step].val=max(L[lson].val,L[rson].val);
}
void Update(int step,int l,int r,int id){
if(L[step].left==l&&L[step].right==r){
L[step].val=L[step].all=id;
return ;
}
Push_Down(step);
int m=(L[step].left+L[step].right)>>1;
if(r<=m) Update(lson,l,r,id);
else if(l>m) Update(rson,l,r,id);
else{
Update(lson,l,m,id);
Update(rson,m+1,r,id);
}
Push_Up(step);
}
int Query(int step,int l,int r){
if(L[step].left==l&&L[step].right==r)
return L[step].val;
int m=(L[step].left+L[step].right)>>1;
Push_Down(step);
if(r<=m) return Query(lson,l,r);
else if(l>m) return Query(rson,l,r);
else return max(Query(lson,l,m),Query(rson,m+1,r));
}
void slove(int l,int r,int who,int can_l,int can_r){
if(l>r) return ;
int id=Query(1,l,r);
if(id==-1){
Update(1,l,r,who);
dp[who]=x[r+1]-x[l];
return ;
}
int pre_l=wall[id].l,pre_r=wall[id].r;
if((pre_l>=l||can_l)&&(pre_r<=r||can_r)){
dp[who]=max(dp[who],min(dp[id],x[min(pre_r,r)+1]-x[max(pre_l,l)]));
}
if(l<pre_l) slove(l,pre_l-1,who,can_l,0);
if(r>pre_r) slove(pre_r+1,r,who,0,can_r);
}
int main(){
scanf("%d%d",&n,&t);
for(int i=0;i<n;i++){
int h,l,r;
scanf("%d%d%d",&h,&l,&r);
wall[i]=Wall(h,l,r);
x[i*2]=l;x[i*2+1]=r;
}
x[n*2]=-inf;x[n*2+1]=inf;
sort(x,x+2*n+2);
cnt=unique(x,x+2*n+2)-x;
wall[n++]=Wall(0,-inf,inf);
wall[n++]=Wall(t,-inf,inf);
sort(wall,wall+n);
for(int i=0;i<n;i++){
wall[i].l=lower_bound(x,x+cnt,wall[i].l)-x;
wall[i].r=lower_bound(x,x+cnt,wall[i].r)-x-1;
}
Bulid(1,0,cnt-1);
for(int i=0;i<n;i++){
int l=wall[i].l,r=wall[i].r;
slove(l,r,i,1,1);
Update(1,l,r,i);
}
printf("%d\n",dp[n-1]);
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define test puts("OK");
#define inf 1000000000
#define lson (step<<1)
#define rson (step<<1|1)
using namespace std;
const int N=100005;
struct Wall{
int h,l,r;
Wall(){}
Wall(int _h,int _l,int _r):h(_h),l(_l),r(_
补充：软件开发 , C++ ,
