TCO 2012 Round2C Medium ThreePoints

問題

座標平面上にx座標, y座標がそれぞれ全て互いに異なるN個の点がある。

この点のうち、三つを取りそれらをr, g, bとする。
x[r] < x[g] < x[b]かつ、y[r] < y[b] < y[g]を満たすようなr, g, bの選び方は何通りあるか、求めよ。

制約条件

N≦300000
0≦座標の値＜10^9

方針

条件を満たす選び方を、直接数えようとするのは難しい。
なので、
x[r] < x[g] < x[b]かつy[r] < y[g], y[r] < y[b]を満たすr, g, bの数から、
x[r] < x[g] < x[b]かつy[r] < y[g] < y[b]を満たすr, g, bの数を引いて求める。

前者は、ある点の右上にある点の数を高速に求めることができれば求まる。
（iの右上にある点の数をtiとすると、Σti * (ti - 1) / 2になる）

後者は、ある点の右上にある点の数の和を、x座標が一定以上のものについて高速に求めることができれば求まる。

これにはbinary indexed treeを使って、点をy座標の大きい順になめながら、計算していけばよい。
x座標の値が大きいので座標圧縮が必要になる。

ソースコード

const int MX = 300010;
ll bit[MX], bit2[MX];
void add(ll *bit, int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
ll sum(ll *bit, int i){
	ll res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}

class ThreePoints {
	public:
	long long countColoring(int N, int xzero, int xmul, int xadd, int xmod, int yzero, int ymul, int yadd, int ymod) {
		
		memset(bit, 0, sizeof(bit));
		memset(bit2, 0, sizeof(bit2));
		
		vi x, y, vx, vy;
		vector<pi> p;
		
		rep(i, N){
			x.pb(xzero);
			xzero = (xzero * (ll)xmul + xadd) % xmod;
			y.pb(yzero);
			yzero = (yzero * (ll)ymul + yadd) % ymod;
			
			p.pb(mp(-y.back(), i));
		}
		vx = x;
		sort(all(vx));
		rep(i, N) x[i] = lower_bound(all(vx), x[i]) - vx.begin() + 1;
		
		
		ll res = 0;
		sort(all(p));
		
		rep(i, N){
			int k = p[i].second;
			ll t = i - sum(bit2, x[k]);
			res += t * (t - 1) / 2;
			res -= sum(bit, MX - 1) - sum(bit, x[k]);
			
			add(bit2, x[k], 1);
			add(bit, x[k], t);
		}
		return res;
	}
	
};