永続segtree

永続は怖いイメージがあると思いますが、segtreeくらいなら簡単に永続化できます。
単にupdateされる予定のnodeを複製して、その複製されたnodeに対してupdateを行えばいいです。
普通のセグ木に複製してリンクを張り替えるコストが増えただけで更新の計算量は変わらずO(logN)です。

永続にすると何が嬉しいんだっていう話になりますが、例えば配列A[a, b)内でk以下の値の個数を数えよみたいな問題が1クエリあたりO(logN)で解けるようになります。
どうやるかというと、まず区間sumができる永続segtree Sを用意します。A内の数字をsortして、小さい順に見ていきます。数字がもとにあった場所をvとして、Sの最新バージョンに対してS(v)に1を足す更新を行います。これで前処理は終了です。
クエリは、Aの中でk以下で最大の数字に対して処理を行ったバージョンに対して[a, b)の区間和をとればいいです。以上で前処理(NlogN)、クエリ一つ当たりO(logN)で計算できました。

l以上k以下も簡単にできるので、(k以下の値からl-1以下の値を引けばよい)二次元座標のx軸y軸に平行な辺を持つ長方形内の点の数を数えるのもO(logN)できます。

struct T {
	ll v;
	T(ll v = 0) : v(v) {}
	T operator+(const T& t) { return T(v + t.v); }
	friend ostream& operator<<(ostream& out, const T& t) {
		out << t.v; return out;
	}
};

struct p_segtree {
	struct node { T t; node *ln, *rn; };
	int n;
	vector<node*> roots;
	inline int latest(int k) { return k == -1 ? (int)roots.size() - 1 : k; }
	void init(int mx) {
		n = 1;
		while(n < mx) n *= 2;
		vector<node*> nodes(2 * n - 1);
		rep(i, 0, 2 * n - 1) {
			node* nn = new node();
			nodes[i] = nn;
		}
		rep(i, 0, n - 1) {
			nodes[i]->ln = nodes[i * 2 + 1];
			nodes[i]->rn = nodes[i * 2 + 2];
		}
		roots.pb(nodes[0]);
	}
	p_segtree(int mx = -1) {
		if(mx != -1) init(mx);
	}
	void app(int a, T x, node* root, int l, int r) {
		int b = a + 1;
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) root->t = x;
		else {
			node* nln = new node(*(root->ln));
			node* nrn = new node(*(root->rn));
			root->ln = nln; root->rn = nrn;
			app(a, x, nln, l, (l + r) / 2);
			app(a, x, nrn, (l + r) / 2, r);
			root->t = root->ln->t + root->rn->t;
		}
	}

	T ga(int a, int b, node* root, int l, int r) {
		if(b <= l || r <= a) return T();
		if(a <= l && r <= b) return root->t;
		else {
			T lv = ga(a, b, root->ln, l, (l + r) / 2);
			T rv = ga(a, b, root->rn, (l + r) / 2, r);
			return lv + rv;
		}
	}
	void update(int a, T t, int k = -1) {
		k = latest(k);
		node* nroot = new node(*roots[k]);
		roots.pb(nroot);
		app(a, t, nroot, 0, n);
	}
	T get(int a, int b, int k = -1) {
		k = latest(k);
		return ga(a, b, roots[k], 0, n);
	}
	void show(int k = -1) {
		vector<T> tmp;
		rep(i, 0, n) tmp.pb(get(i, i + 1, k));
		debug(tmp);
	}
};

似たような問題で蟻本のデータ構造の章のK-th Numberも永続segtreeを使ってシンプルに書けます。計算量は(NlogN+Mlog^2N)です。

int N, M;
p_segtree seg;
pi A[MAX_N];

bool ok(int a, int b, int t, int m) {
	return seg.get(a, b, m + 1).v >= t;
}

int main() {
	scanf("%d%d", &N, &M);
	seg.init(N);
	rep(i, 0, N) {
		scanf("%d", &A[i].fst);
		A[i].sec = i;
	}
	sort(A, A + N);
	rep(i, 0, N) {
		seg.update(A[i].sec, T(1));
	}
	while(M--) {
		int a, b, t;
		scanf("%d%d%d", &a, &b, &t); a--;
		int lv = -1, rv = N;
		while(rv - lv > 1) {
			int m = (lv + rv) / 2;
			if(ok(a, b, t, m)) rv = m;
			else lv = m;
		}
		printf("%d\n", A[rv].fst);
	}
}

実装これだけで済んですごい。でも空間量もO(NlogN)なのでTLEしました…POJの定数倍ゲーやめて。

似たような問題を永続データ構造なしで解くとしたらwavelet木になるので、こっちも勉強したいですね。