SRM 234 DIV1 Hard HowUnsorted

問題 Editorial

問題

"unsortedness point"とは、(数列a, 0 <= i < j < |n|)に対して(a[i] > a[j])となるインデックスの組である。
m,bが与えられるので、(a[0] = 1; a[i] = (m * a[i-1] + c) mod 2^31-1)というように数列を長さnまで生成する。
その数列の"unsortedness point"の数を求めよ

• 3 <= n <= 100000

解答

まず数列を座標圧縮する。
そして(v[i] = (座標圧縮後の)数値iの個数)という列を考える。
そして、数列のインデックスを回していきながらその列を更新していく。
そのつどその列の(数列[i]+1)から最後までのsumを取っていけばいい。(今まで, ここ)の"unsortedness point"の個数ということで。
これは logN系データ構造を使えばいい。FenwickTree(BIT)は定数も速いので良い。

コメント

まず数列を座標圧縮しての列を考えられなかった。それは普通になんというか普通に。
そして、インデックス回しながら更新していく、という感じも思いつけなかった。これも普通に。
2つの数の次元(インデックス, 数)があるから…と思っていたけれど、順番に更新していくようにすればどちらか一方だけに減らせることがあるということ。これはきちんと考えよう。
自分は最初なんかぐちゃぐちゃとバケット法的な感じに書いてAC取った。でも遅すぎる。入力がランダムということに依存してるし、実行時間も遅いし。
でもバケット法っぽい感じもきちんと速く書けないと！
とりあえず、バケットのサイズとかは色々実際に試してみるということはしっかりしよう

コード

Fenwick木バージョン

#include <vector>
#include <algorithm>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
using namespace std;
typedef long long ll;

struct FenwickTree {
	typedef ll T;
	vector<T> v;
	FenwickTree(int n): v(n, 0) {}
	void add(int i, T x) {
		for(; i < v.size(); i |= i+1) v[i] += x;
	}
	T sum(int i) {	//[0, i)
		T r = 0;
		for(-- i; i >= 0; i = (i & (i+1)) - 1) r += v[i];
		return r;
	}
	T sum(int left, int right) {	//[left, right)
		return sum(right) - sum(left);
	}
};

struct HowUnsorted {
	long long howMany(int m, int c, int n) {
		static int a[111111];
		a[0] = 1;
		reu(i, 1, n) a[i] = ((ll)a[i-1] * m + c) % 2147483647LL;
		map<int,int> compress;
		rep(i, n) compress[a[i]] = -1;
		int k = 0;
		each(i, compress) i->second = k ++;
		rep(i, n) a[i] = compress[a[i]];

		FenwickTree ft(k);
		ll r = 0;
		rep(i, n) {
			r += ft.sum(a[i]+1, k);
			ft.add(a[i], 1);
		}
		return r;
	}
};

バケット法？バージョン

#include <vector>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
using namespace std;
typedef vector<int> vi; typedef long long ll;
int a[111111];
struct HowUnsorted {
	long long howMany(int m, int c, int n) {
		const ll MOD = (1LL<<31)-1;
		int mx = 1;
		a[0] = 1;
		reu(i, 1, n) a[i] = ((ll)m * a[i-1] + c) % MOD, mx = max(mx, a[i]);
		int splits = 100;
		vi vv;
		vi s(a, a+n);
		sort(all(s));
		vv.pb(0);
		rep(i, splits) {
			vv.pb(s[(ll)n * i / splits]);
		}
		vv.pb(mx);
		vv.erase(unique(all(vv)), vv.end());
		splits = vv.size();
		vector<vi> ranges(splits);
		rep(i, n) {
			ranges[lower_bound(all(vv), a[i]) - vv.begin()].pb(i);
		}
		ll count = 0;
		rep(i, n) {
			int x = a[i];
			reu(j, 0, lower_bound(all(vv), x - 1) - vv.begin())
				count += ranges[j].end() - lower_bound(all(ranges[j]), i+1);
			if(x != 0) {
				const vi& v = ranges[lower_bound(all(vv), x - 1) - vv.begin()];
				for(aut(j, lower_bound(all(v), i+1)); j != v.end(); ++ j)
					if(x > a[*j]) count ++;
			}
		}
		return count;
	}
};