P2894 [USACO08FEB]Hotel G（线段树,最大子段和）

思路:用线段树维护一个最大子段和,如果最大子段和大于当前询问的长度 l e n len len必然有解.考虑怎么找到这个解,实际上就是查询的时候在满足最大子段和的情况尽量靠左,那么询问递归写法按顺序考虑以下这三种情况 1.完全在左区间.2.横跨中点,左区间+右区间 3.完全在右区间 考虑到非法的情况,应该先查询根的最大子段和( t r e e [ 1 ] . m x > = k ) tree[1].mx>=k) tree[1].mx>=k)的情况下再做查询,小于的情况输出0即可.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
//类似最大子段和那样的写法,讨论区间是否横跨线段树的中点.
//维护一个区间空房间最大子段和,左边起连续最大值,右边起最大值
//查询是否存在一个区间大于k的段,若有,则尽量靠左
//故查询区间顺序先是 左子树,左右合并的情况,右子树
struct Node{
	int lmx,rmx,sum,mx;
};
struct Seg_ment{
	int n;
	vector tree;vector lazy;
	#define L (idxr||end=l&&end=k) return query(L,start,MID,k);
		//再查左边并起来右边的情况.
		if(tree[L].rmx + tree[R].lmx >=k) return MID - tree[L].rmx+1;//MID这个点属于左区间的别算错了
		return query(R,MID+1,end,k);//可能存在非法情况
	}
};
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	Seg_ment seg;
	seg.init(n);seg.build(1,1,n);
	for(int i=1;i>op;
		if(op==1){
			int x;cin>>x;
			//先判一下最大子段和小于x的情况
			if(seg.tree[1].mx