【TIOJ 1975】即時工作排程系統（Scheduler）

原題連結：https://tioj.ck.tp.edu.tw/problems/1975

這題很神奇，至於神奇在哪先不馬上劇透(?

首先，當$\color{white}{\space M=0\space}$時，有顯然的$\color{white}{\space O(NlgN)\space}$排序解。
但我們換個角度，把區間的工作視為區間加值，那就有差分後的$\color{white}{\space O(N+C)\space}$解法。

這個解法的關鍵在於只要取被加最多次的點的值就是答案，所以接下來在處理「非即時性工作」時我們也將採取同樣的策略－－也就是在加完「即時性工作」後，把每個「非即時性工作」的量分別盡量的、不重複的分給死線前、被加的值少的點，最後再取一次被加最多次的點的值就是答案。

為了方便，我們事先把所有非即時性工作讀進來對死線排序，然後把當前工作$\color{white}{\space i\space}$死線$\color{white}{\space d_i\space}$前的點值全部補進資料結構內，每次拿前$\color{white}{\space w_i\space}$小的值出來每個$\color{white}{\space +1\space}$再丟回去－－這是最直觀的寫法了，首先一般我們會想到用pq來維護前k小，但這樣複雜度會是慘慘的$\color{white}{\space O(N+MClgC)\space}$。

於是很自然的也能發現，重複的值太多了，不妨把全部的值全部壓縮在一起綁成pair拿map維護吧！
……結果照樣吃了TLE，因為不能重複分配的關係導致單調性失效。

不過這個壓縮在一起的動作卻是關鍵，可以觀察到，我們是把前$\color{white}{\space w_i\space}$小的值+1，假設被加的值種類分別是$\color{white}{\space v_1,v_2, \cdots ,v_t\space}$，那加值完之後不就只是把前面全部拔掉，變成$\color{white}{\space v_1+1,v_2+1,...,v_{t-1}+1\space}$，並且$\color{white}{\space v_t \space}$被拆成兩份而已嗎！？

這個平移大部份資料位置卻不改變值的動作可以很快速的聯想到某個強大而精美的資料結構－－$\color{white}{\space \text{treap} \space}$！

而我們的$\color{white}{\space \text{treap} \space}$必須支援以下幾個動作：
1.單點加值
2.查找前面所提到的$\color{white}{\space v_t \space}$
3.區間加索引值

這裡可能會有一個疑問，為什麼可以輕易地動到一棵二元樹的索引值？原因就在於$\color{white}{\space \text{treap} \space}$可以很優美的把$\color{white}{\space v_t \space}$以前的值切出來，合併回去的時候只要好好維護掉$\color{white}{\space v_t \space}$的一些問題，索引值的大小關係就完全不會改變到！

這也是我最一開始提到，這題的神奇之處
他完美的讓我們能活用$\color{white}{\space \text{treap} \space}$大量的功能，懶標、移動、查詢之類的，而且又不像大多數模板題一樣無趣，有其靈活的地方在。

分析一下複雜度，剛開始差分完$\color{white}{\space O(N+C)\space}$，每個點的值會丟進去$\color{white}{\space \text{treap} \space}$所以有$\color{white}{\space O(Clg(N+M))\space}$，區間加索引值的動作每個$\color{white}{\space M\space}$一次共$\color{white}{\space O(Mlg(N+M))\space}$。

總複雜度$\color{white}{\space O(N+(M+C)lg(N+M))\space}$。

講了那麼多，總而言之$\color{white}{\space \text{treap} \space}$好好寫就是了啦(X
這單純是我個人很開心而已，請各位路過的大神不要太見外m(_ _)m

附上code：

	#pragma GCC optimize("Ofast")
	#include <bits/stdc++.h>
	#define ll long long
	#define pb push_back
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define F first
	#define S second
	#define MEM(i,j) memset(i,j,sizeof i)
	#define MP make_pair
	#define pii pair<int,int>
	#define pll pair<long long,long long>
	#define ET cout << "\n"
	#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
	using namespace std;
	int line[1000005];
	pii work[100005];
	struct node
	{
	int key,pri,cnt,sz,lazy;
	node *l,*r;
	node(int k,int v):key(k),pri(rand()<<15|rand()),cnt(v),sz(v),lazy(0),l(0),r(0){}
	void up()
	{
	sz=cnt;
	if(l) sz+=l->sz;
	if(r) sz+=r->sz;
	}
	void down()
	{
	if(!lazy) return;
	if(l) l->lazy+=lazy,l->key+=lazy;
	if(r) r->lazy+=lazy,r->key+=lazy;
	lazy=0;
	}
	};
	int sz(node *o)
	{
	return o ? o->sz : 0;
	}
	node *merge(node *a,node *b)
	{
	if(!a || !b) return a ? a : b;
	if(a->pri<b->pri) return a->down(),a->r=merge(a->r,b),a->up(),a;
	return b->down(),b->l=merge(a,b->l),b->up(),b;
	}
	void split(node *o,node *&a,node *&b,int k)
	{
	if(!o) return a=b=0,void();
	o->down();
	if(o->key<=k) a=o,split(o->r,a->r,b,k),a->up();
	else b=o,split(o->l,a,b->l,k),b->up();
	}
	bool add(int k,int v,node *&o)
	{
	if(!o) return 0;
	int re=0;
	o->down();
	if(o->key==k) o->cnt+=v,re=1;
	else if(o->key<k) re=add(k,v,o->r);
	else re=add(k,v,o->l);
	return o->up(),re;
	}
	void insert(int k,int v,node *&o)
	{
	if(add(k,v,o)) return;
	node *a,*b;
	split(o,a,b,k),o=merge(a,merge(new node(k,v),b));
	}
	int search(int x,node *&o)
	{
	o->down();
	if(sz(o->l)>=x) return search(x,o->l);
	if(sz(o->l)+o->cnt>=x) return o->key;
	return search(x-sz(o->l)-o->cnt,o->r);
	}
	void use(int x,node *&o)
	{
	int k=search(x,o),t;
	node *a,*b,*c;
	split(o,a,b,k-1),split(b,b,c,k);
	if(a) a->down(),++a->lazy,++a->key;
	insert(k+1,x-sz(a),c),t=sz(b)-x+sz(a);
	delete b;
	if(t) insert(k,t,a);
	o=merge(a,c);
	}
	int main()
	{jizz
	srand(time(NULL));
	node *treap=0;
	int n,m,w,d,t=1,s=0,C=0;
	cin >> n;
	while(n--)
	cin >> w >> d,++line[w],--line[d+1],C=max(C,d);
	cin >> m;
	for(int i=0;i<m;++i)
	cin >> work[i].S >> work[i].F,C=max(C,work[i].F);
	sort(work,work+m),work[m++]=MP(C+1,0);
	for(int i=0;i<m;++i)
	{
	while(t<=work[i].F) insert(s+=line[t++],1,treap);
	if(work[i].S) use(work[i].S,treap);
	}
	for(treap->down();treap->r;treap=treap->r,treap->down());
	cout << treap->key << "\n";
	}

view raw gistfile1.txt hosted with ❤ by GitHub