読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

KOJ 0042 - Big Range Query

KOJ データ構造

KOJ に載せている, (去年のAdvent Calendar に掲載していた)Big Range Query の問題文および解説です.



$N$ 個の数字からなる数列$\{a_i\}$ ($1 \leqq i \leqq N$) と, クエリが$Q$ 個与えられる. ここで, $i$ 番目の数値の初期値は$i$ である. すなわち, 初期状態では$a_i=i$ である. クエリは次の3 つのうちいずれかである :



  • 区間$[l,\ r]$ の数値の最小値を求める. すなわち, $l \leqq x \leqq r$ を満たす$x$ について, $\min a_{x}$ を求める.

  • 区間$[l,\ r]$ の数値の最大値を求める. すなわち, $l \leqq x \leqq r$ を満たす$x$ について, $\max a_{x}$ を求める.

  • 場所$k$ の数値を$x$ に変更する. すなわち, $a_k = x$ とする.



この$Q$ 個のクエリを処理せよ.


入力



1 行目に, 整数値$N$ と$Q$ が空白区切りで与えられる.

2 行目から$1 + i$ 行目 ($1 \leqq i \leqq Q$) に, クエリが書かれている.

$1 + i$ 行目の最初の数値が1 であるとき, 後ろに数字$l,\ r$ がこの順で空白区切りで書かれている. これは, 区間$[l,\ r]$の最小値を求めるクエリを指す.

$1 + i$ 行目の最初の数値が2 であるとき, 後ろに数字$l,\ r$ がこの順で空白区切りで書かれている. これは, 区間$[l,\ r]$の最大値を求めるクエリを指す.

$1 + i$ 行目の最初の数値が3 であるとき, 後ろに数字$k,\ x$ がこの順で空白区切りで書かれている. これは,位置$k$ の数値を$x$ に変更するクエリを指す.

制限



  • $1 \leqq N \leqq 10^9$ 数列の長さ

  • $1 \leqq Q \leqq 10^5$ クエリの個数

  • 数列の添字は1-indexed で与えられる.

  • クエリを与える前後で, 数列の各数値は $-10^9 \leqq a_i \leqq 10^9$ を必ず満たす.


出力



1 と2 のタイプのクエリに対して, 条件を満たす数値を出力せよ.


入出力例


入力例 1

5 3
1 1 5
3 3 30
2 2 4

出力例 1

1
30


クエリが与えられる過程で, 数列は次の様に変化する.







クエリ数列の状態クエリへの答え
(初期状態)1 2 3 4 5
1 1 51 2 3 4 51
3 3 301 2 30 4 5
2 2 41 2 30 4 530

入力例 2

10 10
1 2 2
3 2 -2
2 2 2
2 1 10
1 1 8
3 1 10
3 2 1000000000
1 1 2
2 2 2
1 2 5

出力例 2

2
-2
10
-2
10
1000000000
3

空白の間隔が広いのはごめんなさい.

解説

この問題に於いて用いるのは, 元の数列の単調増加性と座標圧縮です.
まず, 変更クエリがまったく無いときを考えると, min(a_x | l ≦ x ≦ r) = a_l = l, max(a_x | l ≦ x ≦ r) = a_r = r となります. よって, [l, r]の中の区間(l, r)は必要ないことになります.

しかし, 変更がある場合を考えると, 変更された数値の場所を含め, その両隣も座標圧縮に加味してあげなければなりません. なぜならば, 変更クエリで変更された点で単調増加性が成立しなくなる可能性があるからです.

よって, 最大値/最小値クエリの両端座標, 変更クエリの座標+両隣を座標圧縮に加えることで, O(Q log Q) でこの問題に答えることができます.

本当は数列の数値の初期値を全部おなじ値にするつもりでしたが, これでもできそうなのでこっちを少し考えるとやっぱりできました.
interactive に解くことができるか少し考えてみます.

コード

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
	int mini, maxi;
	Node(int mini, int maxi) : mini(mini), maxi(maxi) {}
	Node(){}
} seg[1 << 23];

void update(int k, int x)
{
	k += (1 << 22) - 1;
	seg[k].mini = seg[k].maxi = x;
	
	for (k = (k - 1) / 2; k; k = (k - 1) / 2){
		seg[k].maxi = max(seg[k * 2 + 1].maxi, seg[k * 2 + 2].maxi);
		seg[k].mini = min(seg[k * 2 + 1].mini, seg[k * 2 + 2].mini);
	}
}

Node getKing(int a, int b, int k = 0, int l = 0, int r = 1 << 22)
{
	if (b <= l || r <= a) return (Node(1000000000, -1000000000));
	
	if (a <= l && r <= b)
		return (seg[k]);
	
	Node ret;
	Node lch = getKing(a, b, k * 2 + 1, l, (l + r) >> 1),
		 rch = getKing(a, b, k * 2 + 2, (l + r) >> 1, r);
	
	return (Node(min(lch.mini, rch.mini), max(lch.maxi, rch.maxi)));
}

int q[1000000], a[1000000], b[1000000];
vector<int> v;

int main()
{
	int N, Q;
	
	scanf("%d %d", &N, &Q);
	
	for (int i = 0; i < Q; i++){
		scanf("%d %d %d", q + i, a + i, b + i);
		if (q[i] != 3){
			v.push_back(a[i]); v.push_back(b[i]);
		}
		else {
			v.push_back(max(a[i] - 1, 1));
			v.push_back(a[i]);
			v.push_back(min(a[i] + 1, N));
		}
	}
	
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	
	for (int i = 0; i < v.size(); i++){
		update(i, v[i]);
	}
	
	for (int i = 0; i < Q; i++){
		if (q[i] == 3){
			update(lower_bound(v.begin(), v.end(), a[i]) - v.begin(), b[i]);
		}
		else {
			Node t = getKing(lower_bound(v.begin(), v.end(), a[i]) - v.begin(), lower_bound(v.begin(), v.end(), b[i]) - v.begin() + 1);
			printf("%d\n", q[i] == 1 ? t.mini : t.maxi);
		}
	}
	
	return (0);
}