http://acm.hdu.edu.cn/showproblem.php?pid=2795线段树之求最小区间端点值

本文主要是介绍http://acm.hdu.edu.cn/showproblem.php?pid=2795线段树之求最小区间端点值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

刚看到这一题还以为用的是二维线段树，，于是一个劲的想模型，想了一个上午还是没有理清头绪来，，，最后看看了hh神牛的博客，，才明白是怎么回事，以行数对应线段树的端点建树，以该行没有被覆盖列数为该区间的最大值。从而转化为求区间最大值大于给定数的最小端点值问题，，，但要注意的是更新子节点对父节点的影响

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 200005
#define M(x,y) ((x+y)>>1)
int s[N<<2];
void pushup(int x)
{s[x]=max(s[x<<1],s[x<<1|1]);
}
void build(int t,int l,int r,int w)
{s[t]=w;if(l==r) return;int mid=M(l,r);build(t<<1,l,mid,w);build(t<<1|1,mid+1,r,w);
}
int Quary(int t,int l,int r,int w)
{if(l==r) {s[t]-=w;return l;}int mid=M(l,r);int res=0;if(s[t<<1]>=w)   res=Quary(t<<1,l,mid,w);else res=Quary(t<<1|1,mid+1,r,w);pushup(t);return res;
}
int main()
{int h,w,n;while(~scanf("%d%d%d",&h,&w,&n)){if(h>n) h=n;build(1,1,n,w);for(int i=1;i<=n;++i){int a;scanf("%d",&a);if(s[1]<a) cout<<"-1"<<endl;else printf("%d\n",Quary(1,1,h,a));}}return 0;
}

这篇关于http://acm.hdu.edu.cn/showproblem.php?pid=2795线段树之求最小区间端点值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---