【wikioi】1217 借教室

题目链接http://www.wikioi.com/problem/1217/

算法：二分答案（线段树可过wikioi数据）

• 二分：http://www.wikioi.com/solution/list/1217/   （我不多阐述）

  我的代码

  #include <cstdio>
  
  using namespace std;
  
  #define MID (l+r) >> 1
  
  const int maxn = 1000000+10;
  
  int sum[maxn], cl[maxn], d[maxn], s[maxn], t[maxn], n, m, last, last_q;
  
  int check(int r) {
  
  	int ret = 0;
  
  	for(int i = 1; i <= n; ++i) { //这里必须要到n，因为是用前缀和， 即sum[t[i]]的t[i]后可能还有sum= =。。
  
  		ret += sum[i];
  
  		if(ret > cl[i]) return 0;
  
  	}
  
  	return 1;
  
  }
  
  int main() {
  
  	scanf("%d%d", &n, &m);
  
  	int l = 1, r = m, mid, i;
  
  	for(i = 1; i <= n; ++i) scanf("%d", &cl[i]);
  
  	while(l <= r) {
  
  		mid = MID;
  
  		if(last_q < mid){
  
  			for(i = last+1; i <= mid; ++i) scanf("%d%d%d", &d[i], &s[i], &t[i]);
  
  			last_q = mid;
  
  		}
  
  		//这里最容易错，要清楚标记
  
  		for(i = mid+1; i <= last; ++i) sum[s[i]] -= d[i], sum[t[i]+1] += d[i]; //将原来加上去的和减的恢复
  
  		for(i = last+1; i <= mid; ++i) sum[s[i]] += d[i], sum[t[i]+1] -= d[i]; //加上去的和减去新添加的元素
  
  		last = mid;
  
  		if(check(mid)) l = mid+1;
  
  		else r = mid-1;
  
  	}
  
  	//一般闭区间二分的答案是l-1，在这里，l-1=m时说明所有人都满足
  
  	if(l-1 == m) printf("0");
  
  	else printf("-1\n%d", l); //而因为l-1是答案，所以l-1+1=l就是下一个不符合答案的
  
  	return 0;
  
  }
  

• 线段树（区间更新和维护最小）

  注意：用线段树最容易错的地方就是认为当修改后全部教室加起来的和为负的那个人就是解。其实应该是每天的教室需求量，不是和。所以不能维护区间和，要维护一个最小值，最小值为负，说明这个人就是答案

  #include <cstdio>
  
  using namespace std;
  
  #define lson l, m, rt << 1
  
  #define rson m+1, r, rt << 1 | 1
  
  #define MID (l+r)>>1
  
  #define lc rt << 1
  
  #define rc rt << 1 | 1
  
  int min(const int& a, const int& b){return a < b ? a : b;}
  
  const int maxn = 1e6+10;
  
  int minx[maxn << 2], add[maxn << 2], n, m, L, R, _add;
  
  //向上传递最小的
  
  void pushup(int rt) {
  
  	minx[rt] = min(minx[lc], minx[rc]);
  
  }
  
  //向下传递修改值
  
  void pushdown(int rt) {
  
  	if(add[rt]) {
  
  		add[lc] += add[rt];
  
  		add[rc] += add[rt];
  
  		minx[lc] += add[rt];
  
  		minx[rc] += add[rt];
  
  		add[rt] = 0;
  
  	}
  
  }
  
  void build(int l, int r, int rt) {
  
  	add[rt] = 0;
  
  	if(l == r) {
  
  		scanf("%d", &minx[rt]);
  
  		return;
  
  	}
  
  	int m = MID;
  
  	build(lson); build(rson);
  
  	pushup(rt);
  
  }
  
  void update(int l, int r, int rt) {
  
  	if(L <= l && r <= R) {
  
  		add[rt] += _add;
  
  		minx[rt] += _add; //这里直接修改即可
  
  		return;
  
  	}
  
  	pushdown(rt);
  
  	int m = MID;
  
  	if(L <= m) update(lson);
  
  	if(m < R) update(rson);
  
  	pushup(rt);
  
  }
  
  int main() {
  
  	scanf("%d%d", &n, &m);
  
  	build(1, n, 1);
  
  	int i;
  
  	for(i = 1; i <= m; ++i) {
  
  		scanf("%d%d%d", &_add, &L, &R);
  
  		_add = -_add;
  
  		update(1, n, 1);
  
  		if(minx[1] < 0) { printf("-1\n%d", i); return 0;}
  
  	}
  
  	printf("0");
  
  	return 0;
  
  }