[TIOJ] 1975. 即時工作排程系統（Scheduler）

題目連結:https://tioj.infor.org/problems/1975

---

首先本題要可以觀察到對於只有即時性工作時我們很簡單的就是計算他重疊最多的部分是多少，而對於非即時性工作則是要透過由deadline由小到大排後，每次選取被加值最少的那些不重疊區間來分配，最後計算最大值。
合併這兩個思考之後就可以發現本題變成一個用treap可以維護的題目了XD

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
const int C = 1000000 + 5;

namespace Treap{
	#define sz( x ) ( ( x ) ? ( ( x )->size ) : 0 )
	#define sm( x ) ( ( x ) ? ( ( x )->sum ) : 0 )
	struct node{
		int size, cnt, sum;
		uint32_t pri;
		node *lc, *rc;
		node(): size( 0 ), cnt( 0 ), sum( 0 ), pri( rand() ),
		        lc( nullptr ), rc( nullptr ) {}
		node( int x ): size( 1 ), cnt( x ), sum( x ), pri( rand() ),
		        lc( nullptr ), rc( nullptr ) {}
		void pull() {
			sum = cnt;
			if ( lc ) sum += lc->sum;
			if ( rc ) sum += rc->sum;
			size = 1;
			if ( lc ) size += lc->size;
			if ( rc ) size += rc->size;
		}
	};
	node* merge( node* L, node* R ) {
		if ( not L or not R ) return L ? L : R;
		if ( L->pri > R->pri ) {
			L->rc = merge( L->rc, R );
			L->pull();
			return L;
		} else {
			R->lc = merge( L, R->lc );
			R->pull();
			return R;
		}
	}
	void split_by_size( node* rt, int k, node*& L, node*& R ) {
		if ( not rt ) L = R = nullptr;
		else if( sz( rt->lc ) + 1 <= k ) {
			L = rt;
			split_by_size( rt->rc, k - sz( rt->lc ) - 1, L->rc, R );
			L->pull();
		} else {
			R = rt;
			split_by_size( rt->lc, k, L, R->lc );
			R->pull();
		}
	}
	void split_by_sum( node* rt, int k, node*& L, node*& R ) {
		if ( not rt ) L = R = nullptr;
		else if( sm( rt->lc ) + rt->cnt <= k ) {
			L = rt;
			split_by_sum( rt->rc, k - sm( rt->lc ) - rt->cnt, L->rc, R );
			L->pull();
		} else {
			R = rt;
			split_by_sum( rt->lc, k, L, R->lc );
			R->pull();
		}
	}
	#undef sz
	#undef sm
}

int cnt[ C ];
pair< int, int > arr[ N ];

int solve( Treap::node*, int );

int main() {
	ios_base::sync_with_stdio( false );
	cin.tie( nullptr );
	int n; cin >> n;
	for ( int i = 0 ; i < n ; ++ i ) {
		int l, r; cin >> l >> r;
		cnt[ l ]++;
		cnt[ r + 1 ]--;
	}
	for ( int i = 1 ; i < C ; ++ i )
		cnt[ i ] += cnt[ i - 1 ];

	int m; cin >> m;
	for ( int i = 0 ; i < m ; ++ i )
		cin >> arr[ i ].first >> arr[ i ].second;
	sort( arr, arr + m, []( const pair< int, int >& a, const pair< int, int > & b ) {
		return a.second < b.second;
	} );

	Treap::node *root = new Treap::node( 0 );
	for ( int i = 1 ; i <= n + m ; ++ i )
		root = Treap::merge( root, new Treap::node( 0 ) );

	int ptr = 0;
	for ( int i = 0 ; i < m ; ++ i ) {
		while ( ptr <= arr[ i ].second ) {
			Treap::node *a, *b;
			Treap::split_by_size( root, cnt[ ptr ] + 1, a, b );
			Treap::node *c, *d;
			Treap::split_by_size( a, cnt[ ptr ++ ], c, d );
			d->cnt++; d->pull();
			root = Treap::merge( merge( c, d ), b );
		}
		Treap::node *a, *b;
		Treap::split_by_sum( root, arr[ i ].first - 1, a, b );
		a = Treap::merge( new Treap::node( 0 ), a );
		int tot = a->sum, need = arr[ i ].first - tot;

		Treap::node *c, *d;
		Treap::split_by_size( b, 1, c, d );
		Treap::node *e, *f;
		Treap::split_by_size( a, a->size - 1, e, f );
		Treap::node *g, *h;
		Treap::split_by_size( d, 1, g, h );

		// e, f, c, g, h
		f->cnt += c->cnt - need; f->pull();
		g->cnt += need; g->pull();

		root = Treap::merge( Treap::merge( e, f ), Treap::merge( g, h ) );
	}

	while ( ptr < C ) {
		Treap::node *a, *b;
		Treap::split_by_size( root, cnt[ ptr ] + 1, a, b );
		Treap::node *c, *d;
		Treap::split_by_size( a, cnt[ ptr ++ ], c, d );
		d->cnt++; d->pull();
		root = Treap::merge( merge( c, d ), b );
	}

	cout << solve( root, 0 ) - 1 << '\n';
	return 0;
}

int solve( Treap::node* cur, int s ) {
	if ( not cur ) return 0;
	int ans = 0;
	if ( cur->lc ) {
		ans = max( ans, solve( cur->lc, s ) );
		s += cur->lc->size;
	}
	++ s;
	if ( cur->cnt ) ans = max( ans, s );
	if ( cur->rc )
		ans = max( ans, solve( cur->rc, s ) );
	return ans;
}