[NTUJ] 2789. Graduate Record Examinations

題目連結:http://acm.csie.org/ntujudge/problem.php?id=2789

---

原本想要用離散化在定義一堆其怪的狀態來做這題，不過越寫越寫不出來。被雷了才知道，原來其實把那堆bit看成一堆線段就好了，那其實退位就是讓目前最低位消失，並在低他一位的地方長出一堆一直到現在這位置，而進位就更不用說了，畢竟原本進位就是均攤$O(1)$了。

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;

vector<PII> work, ans;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t; cin>>t;
	while(t--){
		work.clear();
		ans.clear();
		minHeap<int> pq1, pq2;
		int n; cin>>n;
		for(int i=0;i<n;i++){
			char c;int k;
			cin>>c>>k;
			if(c=='+') pq1.push(k);
			else if(c=='-') pq2.push(k);
		}
		while(pq1.size()>1){
			auto a=pq1.top();pq1.pop();
			auto b=pq1.top();pq1.pop();
			if(a==b) pq1.push(a+1);
			else{
				work.PB({a,1});
				pq1.push(b);
			}
		}
		if(!pq1.empty()) work.PB({pq1.top(), 1});
		while(pq2.size()>1){
			auto a=pq2.top();pq2.pop();
			auto b=pq2.top();pq2.pop();
			if(a==b) pq2.push(a+1);
			else{
				work.PB({a,0});
				pq2.push(b);
			}
		}
		if(!pq2.empty()) work.PB({pq2.top(), 0});
		sort(ALL(work), [](PII a, PII b){return a>b;});
		for(auto i:work){
			if(i.SS == 1) ans.PB({i.FF,i.FF});
			else{
				int high = ans.back().SS++;
				if(ans.back().FF < ans.back().SS) ans.pop_back();
				ans.PB({high-1, i.FF});
			}
		}
		int cnt=0;
		for(auto i:ans) cnt += i.FF-i.SS+1;
		cout<<cnt<<'\n';
	}
	return 0;
}