yukicoder : No.670 log は定数

まんまとはまった。
https://yukicoder.me/problems/no/670

問題

N要素の整数列A[i]が与えられる。
それとは別に、Q個のクエリが与えられる。
各クエリの値X[j]に対し、AのうちX[j]より小さい要素数をR[j]とする。
R[j]*(j-1)のxorを取ったものを答えよ。

解法

AとXを先にソートして尺取り法をすると解けるには解けるが、Qが大きいのでソートが割とつらい。
Xの方をバケットソートすると若干短くなるが、手元では4s切るものの実環境では4s以上5s未満で通らなかった。

そこでAの方をバケットソートしてしまおう。
バケットソート後の各バケット内の要素数の累積和を取っておく。
そうするとX[j]に対し同じバケット内にあるA[i]とのみ大小比較すればよい。
A,Xはともに乱数で生成されるため、意地悪く特定のバケットに値が集中することはないのでこれで通る。

using ull = unsigned long long;

ull seed;
int next() {
	seed = seed ^ (seed << 13);
	seed = seed ^ (seed >> 7);
	seed = seed ^ (seed << 17);
	return (seed >> 33);
}

int N,Q;
int A[201010];
const int D=15;
vector<int> bucket[1<<(31-D)];
int S[5+(1<<(31-D))];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>seed;
	FOR(i,10000) next();
	FOR(i,N) {
		x=next();
		bucket[x>>D].push_back(x);
		S[1+(x>>D)]++;
	}
	FOR(i,3+(1<<(31-D))) S[i+1]+=S[i];
	
	ll ret=0;
	FOR(i,Q) {
		x = next();
		int num=S[x>>D];
		FORR(v,bucket[x>>D]) if(v<x) num++;
		ret^=num*1LL*i;
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

Xの分割でも通ると思ったんだけどなぁ。