TCO2012 Round2C d1m ThreePoints

Programming

ネタバレ
多分rng問題のほうにも軽く書くと思うけど別立てで.

問題:平面上の点(x[i],y[i])がN(<=300000)個与えられる.次を満たすa,b,cの組の個数を求めよ:x[a]<x[b]<x[c]かつy[a]<y[c]<y[b]








僕の解答:
平方分割+遅延評価 みたいな.
まずどう数えるかというとaを固定して,各cにたいするbの数(以下,cのうれしみ)の和を高速に求める.点たちを右から追加していくことで,各cのうれしみ はy[a]によらず決まる.点を追加するときはその点より下の点のうれしみを+1して,上の点たちのうれしみの総和を答えに足せば良い.

yに対して,sqrt(N)個くらいのバケットに分けて,そのバケットに一様に足されたうれしみad,今何個追加されたかn,一様でなく持ってるうれしみx,バケット全体でのうれしみs を持つ.追加する点を持っているバケットbに対してはad[b]を各xに対して足す(遅延評価)それ以外のとこに対しては一様に足す.これでちゃんと総和が求められる.

なんか遅延評価ってsegtreeにくっつくものだとおもってたけどこういう感じのこともできるんだなあ(きっと典型だが僕はsqrt(N)弱いのでわからず)


想定解?:
p)x[a]<x[b],x[c] かつ y[a]<y[b],y[c] の個数は各点の右上にある点の個数が求まればわかる.
q)x[a]<x[b]<x[c] かつ y[a]<y[b]<y[c] の個数はbを固定すると右上と左下の〃.
よく考えると答えはこれの差で求められる.
右上の点,とかはBITとかなんでもOK


共通する発想としては,真ん中を固定する気持ちになることで,僕の解法では点を右から見ることでxに関することをあまり考えずに済むようにしてy[c]とy[b]の大小関係に専念できるようにした.

q)が楽に求まるのは分かってたんだけどpの発想がなかった(ちゃんと全部並べる不等式しか考えてなかった) おもしろいなあ.

僕のコード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int B=548;		//a bucket has B eles
vector<P> ps;
int x[B*B],ad[B],n[B],s[B];		//each,add,num,sum(including ad*num)
vector<int> ash;
bool is[B*B];
class ThreePoints{
	public:
	long long countColoring(int N, int xz, int xm, int xa, int xmod, int yz, int ym, int ya, int ymod){
		rep(i,N){
			ps.pb(P(xz,yz));
			xz=((ll)xz*xm+xa)%xmod;
			yz=((ll)yz*ym+ya)%ymod;
		}
		sort(all(ps));
		rep(i,N) ash.pb(ps[i].sc);
		sort(all(ash));
		int M=(N-1)/B+1;
		ll ans=0;
		rep(i,N){
			int y=lower_bound(all(ash),ps[N-1-i].sc)-ash.begin();
			int b=y/B;
			for(int j=b*B;j<min((b+1)*B,N);j++){
				if(is[j]){
					x[j]+=ad[b];
					if(j<y) x[j]++,s[b]++;
				}
			}
			ad[b]=0;
			n[b]++;
			is[y]=1;
			rep(j,b){
				ad[j]++;
				s[j]+=n[j];
			}

			for(int j=y+1;j<min((b+1)*B,N);j++){
				if(is[j]) ans+=x[j];
			}
			for(int j=b+1;j<M;j++){
				ans+=s[j];
			}
		}
		return ans;
	}
};