TCO12 500pt : ThreePoints

問題概要

2次元平面上に点がN(<3*10^5)個ある。x座標、y座標はどれも互いに異なる。3点選んでx[0]

解法

とりあえず座標圧縮しておく。その後x座標の大きい方から右上にいくつ点があるのかとx[1]

acceptされたコード

#include <algorithm>
#include <cstring>
using namespace std;

typedef long long int64;
const int MAX_N = 300000;

struct Point{
	int y, x;
	Point(){}
	Point(int y, int x):y(y), x(x){}
};

bool operator< (const Point& lhs, const Point& rhs){
	return lhs.x < rhs.x;
}

Point ps[MAX_N];
int tmp[MAX_N];

BinaryIndexedTree bit1, bit2;

struct ThreePoints {

	int64 countColoring(int N, int xzero, int xmul, int xadd, int xmod, int yzero, int ymul, int yadd, int ymod) {
		int X, Y;
		ps[0] = Point(yzero, xzero);
		for(int i=0; i<N-1; ++i){
			ps[i+1].y = ((int64)ps[i].y * ymul + yadd) % ymod;
			ps[i+1].x = ((int64)ps[i].x * xmul + xadd) % xmod;
		}

		for(int i=0; i<N; ++i){
			tmp[i] = ps[i].x;
		}
		sort(tmp, tmp+N);
		X = unique(tmp, tmp+N) - tmp;
		for(int i=0; i<N; ++i){
			ps[i].x = lower_bound(tmp, tmp+X, ps[i].x) - tmp;
		}

		for(int i=0; i<N; ++i){
			tmp[i] = ps[i].y;
		}
		sort(tmp, tmp+N);
		Y = unique(tmp, tmp+N) - tmp;
		for(int i=0; i<N; ++i){
			ps[i].y = lower_bound(tmp, tmp+Y, ps[i].y) - tmp;
		}

		sort(ps, ps + N);
		int64 ans = 0;
		bit1.init(N);
		bit2.init(N);
		for(int i=N-1; i>=0; --i){
			int64 np = bit1.sum(ps[i].y, Y);
			int64 up = bit2.sum(ps[i].y, Y);

			if(np > 0){
				ans += np * (np - 1) / 2 - up;
			}
			bit1.add(ps[i].y, 1);
			bit2.add(ps[i].y, np);
		}
		return ans;
	}

};