BZOJ1577 USACO 2009 Feb Gold 1.Fair Shuttle Solution

问题补充:n个站,有m群奶牛,第i群奶牛有mi只,要从si站出发,到ti站下车.乳牛の群れには、全部乗らなくてもいいです.同時に車の上の乳牛の数はcを超えることができなくて、最大でどれだけの乳牛の要求を満たすことができることを求めます.
Sol:
最初は非常に素朴な費用フローを思い浮かべ,モデリングは等式差分によって非常に明らかであった.しかし、これは深刻なタイムアウトになります.
現在の負荷と答えを2つの変数now,ansでそれぞれ記録した.
乳牛の群れごとに現在残っている数numを維持します.
乳牛群をsiの大きい順から小さい順に並べて処理した.
現在の乳牛群iについて、残りの乳牛群j中のtj<=siの乳牛群を探し出し、負荷:now+=numjを還元した.
私たちは現在の乳牛群をすべて乗車させたが、負荷を超える可能性があるので、負荷が条件を満たすまで、現在残っているti最大の乳牛群を貪欲に減らした.この過程で、答えを更新します.
これにより,O(mlogm)の時間的複雑さでこの問題を解決した.
具体的な実現面では、大根炉と小根炉をそれぞれ維持し、tiを維持する.
Code:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

#define N 20010
#define M 50010
int n, m;
struct Interval {
	int l, r, num;
	Interval(int _l = 0, int _r = 0, int _num = 0):l(_l),r(_r),num(_num){}
	void read() {
		scanf("%d%d%d", &l, &r, &num);
	}
	bool operator < (const Interval &B) const {
		return l < B.l;
	}
}S[M];

inline bool cmp(int a, int b) {//return a < b
	return S[a].r < S[b].r;
}
struct Heap {
	int a[M], ch[M], top;
	bool d;
	Heap(bool _d):d(_d) {
		top = 0;
	}
	bool empty() {
		return (top == 0);
	}
	void up(const int &x, bool del) {
		for(int i = x; i != 1; i >>= 1) {
			if (del || (cmp(a[i], a[i >> 1]) ^ d)) {
				swap(ch[a[i]], ch[a[i >> 1]]);
				swap(a[i], a[i >> 1]);
			}
			else
				break;
		}
	}
	void down(const int &x) {
		int son;
		for(int i = x; (i << 1) <= top; ) {
			son=(((i<<1)==top)||(cmp(a[i<<1],a[(i<<1)|1])^d))?(i<<1):((i<<1)|1);
			if (cmp(a[son], a[i]) ^ d) {
				swap(ch[a[i]], ch[a[son]]);
				swap(a[i], a[son]);
				i = son;
			}
			else
				break;
		}
	}
	void insert(const int &x) {
		a[++top] = x;
		ch[x] = top;
		up(top, 0);
	}
	void pop() {
		a[1] = a[top];
		ch[a[top--]] = 1;
		down(1);
	}
	void cutdown(const int &x) {
		int ins = ch[x];
		up(ins, 1);
		pop();
	}
	int res() {
		return a[1];
	}
}Max(1), Min(0);

int main() {
	//freopen("tt.in", "r", stdin);
	int lim;
	scanf("%d%d%d", &m, &n, &lim);
	
	int i;
	for(i = 1; i <= m; ++i)
		S[i].read();
	sort(S + 1, S + m + 1);
	S[0].r = -1;
	S[m + 1].r = 1 << 30;
	
	int now = 0, ans = 0, x;
	for(i = 1; i <= m; ++i) {
		while(!Min.empty() && S[x = Min.res()].r <= S[i].l) {
			Min.cutdown(x);
			Max.cutdown(x);
			now -= S[x].num;
		}
		now += S[i].num;
		ans += S[i].num;
		Min.insert(i);
		Max.insert(i);
		while(now > lim) {
			x = Max.res();
			if (S[x].num > now - lim) {
				ans -= now - lim;
				S[x].num -= now - lim;
				now = lim;
				break;
			}
			else {
				Min.cutdown(x);
				Max.cutdown(x);
				ans -= S[x].num;
				now -= S[x].num;
			}
		}
	}
	
	printf("%d", ans);
	
	return 0;
}