[TIOJ] 1045. A.細菌培養

題目連結:http://tioj.infor.org/problems/1045

---

原本看到的時候想用線段樹直接揍他，結果寫一寫覺得卡卡的，然後就被嗆說幹嘛用線段樹做了QQ。想了想才發現可以離散化後直接對序列操作，複雜度$O(N^2)$，也就是把序列乘二或除二，然後算一下他的變化量來維護整段的總和。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
#define ALL(x) (x).begin(), (x).end()

const int N = 10000 + 1;

class Lisan{
	private:
		vector<int> v;
	public:
		inline void init(){
			v.clear();
		}
		inline void insert(int x){
			v.PB(x);
		}
		inline void done(){
			sort(ALL(v));
			v.resize(distance(v.begin(), unique(ALL(v))));
		}
		inline int get(int x){
			return distance(v.begin(), lower_bound(ALL(v),x));
		}
		inline int inv_get(int x){
			return v[x];
		}
} li;

struct Opt{
	int pos, l, r, v;
};
vector<Opt> opts;
lld arr[N], sum=0;
inline void init();
inline void mul(int,int,double);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n, n){
		init();
		for(int i=0;i<n;i++){
			int l, t, r, b;
			cin>>l>>t>>r>>b;
			opts.PB({l,t,b,1});
			opts.PB({r,t,b,0});
			li.insert(t);
			li.insert(b);
		}
		li.done();
		sort(ALL(opts),[](const Opt &a, const Opt &b){return a.pos<b.pos;});
		lld ans = 0;
		int prePos = 0;
		for(auto i:opts){
			ans += (i.pos-prePos)*sum;
			mul(li.get(i.l),li.get(i.r),(i.v?2:0.5));
			prePos = i.pos;
		}
		ans += (N-1-prePos)*sum;
		cout<<ans<<'\n';
	}
	return 0;
}

inline void init(){
	fill(arr,arr+N,1);
	sum=N-1;
	opts.clear();
	li.init();
}

inline void mul(int l, int r, double x){
	for(int i=l;i<r;i++){
		sum += ((lld)(arr[i]*x) - arr[i])*(li.inv_get(i+1)-li.inv_get(i));
		arr[i]*=x;
	}
}