MAXimal

���������: 11 Jun 2008 11:00
�������������: 25 Oct 2011 21:31

���������� [������]

������ ��������

������ �������� — ��� ��������� ������, ������� ��������� ���������� (�.�. �� ����������� O (\log n)) ����������� �������� ���������� ����: ���������� �����/�������� ��������� ������� � �������� ������� (a[l \ldots r], ��� lr ��������� �� ���� ���������), ��� ���� ������������� �������� ��������� ��������� �������: ��� ��������� �������� ������ ��������, ��� � ��������� ��������� �� ����� ���������� ������� (�.�. ����������� ��������� ���� ��������� a[l \ldots r] �����-���� ��������, ���� ��������� �� ���� ��������� ������� �����-���� �����).

������, ������ �������� — ����� ������ ���������, � ����� �����, �������� ��, ������������ �������������. ������ ���������� ���� ����� �������� � ��������� ��������, ����� �������� � ������� ����� ������� �������� (��. ������ "����������� ������ ������ ��������"). � ���������, ������ �������� ����� ���������� �� ������� �����������: ��������, ��� ������� ������ � ������ �����/�������� � ��������� ����������������� ������ ������� (������, ��� ������ �� ����� O (\log^2 n)).

������ ������������ �������� �������� �������� ��, ��� ��� ���������� �������� ����� ������: ������������ ������ �������� ��������� ������� 4n ��������� ������ ��� ������ ��� �������� ������� n.

�������� ������ �������� � ������� ��������

��� ������ ���������� ���������� ������ ������ �������� — ������ �������� ��� ����. ���� ������� ������ ���������, �� � ��� ���� ������ a[0..n-1], � ���� ������ �������� ������ ����� �������� ����� ��������� � l-�� �� r-�� (��� ������ �����), � ����� ������������ ��������� �������� ������ ���������� �������� �������, �.�. ���������� ����������� �� ���������� a[i]=x (��� ������ �����������). ��� ��� ����������, ������ �������� ������ ������������ ��� ���� ������� �� ����� O (\log n).

��������� ������ ��������

����, ��� �� ������������ �� ���� ������ ��������?

���������� � �������� ���-������ ����� ��������� ����� �������, �.�. ������� a[0 \ldots n-1]. ����� ��������� ����� �� ���� ���������� ����� �������: a[0 \ldots n/2]a[n/2+1 \ldots n-1]. ������ �� ���� ���� ��������� � ���� ������� �������� �������, ��������� � �������� ����� �� ���, ����� ����� �������� �������, � ��� �����, ���� ������� ������� �� ��������� ����� 1. ����� �������, �� �������� � ������� [0;n-1] � ������ ��� ����� ������� ������� ������ (���� �� ��� �� ���� �������� ��������� �����), ������� ����� ��� �� ��������� �� ����� ���������; ��� ������� ������ ������� �� ������ ����� ����� �� ���.

����� ��������, ��� ��� �������, �� ������� �� ������� �����, �������� ������: ������ ����� ������ — ������� [0 \ldots n-1], � ������ ������� ����� ����� ���� ������� (����� ������-�������, � ������� ������� ����� ����� 1). ������ � ���������� �������� — "������ ��������" (���� ��� ���������� ������ �������� ������ ���� �� ��������, �� �� ���� ���� � ������� ����������).

����, �� ������� ��������� ������ ��������. ����� �������, ��� ��� ����� �������� ������, � ������, �������� ����� 2n ������. ������ ��� ����� ��������� �������: ������ ������� ������ �������� �������� ���� ������� (������� [0 \ldots n-1]), ������ ������� — � ������ ������ ��� �������, �� ������� ������ � ������ ������ ����� ������ �������, � ��� �����, ���� ����� ������ �� ��������� n. ����� �������, ����� ������ � ������ ������ ����������� ������ n + n/2 + n/4 + n/8 + \ldots + 1 < 2n.

����� ��������, ��� ��� n, �������� �� �������� ������, �� ��� ������ ������ �������� ����� ��������� ���������. ��������, ��� n=3 ����� ��� ����� ���� ������� [0 \ldots 1], ������� ���� ��������, � �� ����� ��� ������ ��� ����� — ������� [2 \ldots 2], ���������� ������. ������� ������ ���������� ��� ���������� ��� �� ����������, �� ��� �� ����� ��� ���� ����� � ����.

������ ������ �������� ���� �������� O (\log n) — ��������, ������ ��� ����� ������� � ����� ������ ����� n, � ��� �������� �� ���� ������� ���� ����� �������� ����������� �������� �����.

����������

������� ���������� ������ �������� �� ��������� ������� a ����� ������ ���������� ��������� �������, ����� �����: ������� ������� �������� ��������� a[i] � ��������������� ������ ������, ����� �� ������ ��� ��������� �������� ��� ������ ����������� ������ ��� ����� �������� � ���� �������, ����� ����������� ������� ��������� �������� ��� ��� ������ ������, � �.�. ������ ��������� ��� �������� ����������: �� ��������� ��������� ���������� �� ����� ������ ��������, � ���� ��������� ����������, ���� � ������� �� �� �����, �������� ���� �� ������� �� ���� ������� � ��������� ����������� ��������, � ���� � ������� �� ����� — �� ������ ���������� � ���� �������� ����� �������� �������.

����������� ���������� ������ �������� ��������, ����� �������, O(n).

������ �����

���������� ������ ������ �����. �� ���� ��������� ��� ����� lr, � �� ������ �� ����� O (\log n) ��������� ����� ����� �� ������� a[l \ldots r].

��� ����� �� ����� ���������� �� ������������ ������ ��������, ��������� ��� �������� ������ ����������� ����� ����� �� ������ ������� ������. ���������� �� ����� � ������ ������ ��������. ���������, � ����� �� ���� ��� ������� �������� ������� ������� [l \ldots r] (��������, ��� ������� ����� ������ �������� — ��� ������� [0 \ldots n/2][n/2+1 \ldots n-1]). �������� ��� ��������: ��� ������� [l \ldots r] �������� ������ � ������ ���� �����, � ���, ��������, ������� ������������ � ������ ���������.

������ ������ �����: ������ ������� � ���� ����, � ������� ����� ��� �������-������, � �������� ����������� ����� �������� � ������� �������.

�� ������ �� ������ ��� �� ������� ������ ���������, ����� ��� ������� ������� � ������ ���� � ��������� ����� �� ������ � ���, � ����� — ������� � ������� ����, ��������� � ��� ����� � ��������� � ������ ������. ����� �������, ���� ����� ��� ����������� ������� [l_1 \ldots r_1], � ������ — ������� [l_2 \ldots r_2] (�������, ��� l_2 = r_1 + 1), �� �� ������� � ������ ���� � �������� [l \ldots r_1], � � ������� — � �������� [l_2 \ldots r].

����, ��������� ������� ����� ������������ ����� ����������� �������, ������� ������ ��� �������� ���� ���� �� ������ ����, ���� �� ������� (�� ������� ������� ������� � ����� �������), ���� �� ����� ����� (��� ���� ���� ��� ������ �� ��� ��������������� ����������). ������ ����������� ������ ����� ������ �� ������: ���� ������� ������ ������ � ��������� ������� � ������� ������� ������ ��������, �� � �������� ������ ����� ���������� ��������������� �������� ����� �� ���� �������, ���������� � ������ ��������.

����� �������, ���������� ������� ������������ ����� ����� �� ������ ��������, ������� ���������������� �� ���� ������ ������ ������, � ��� ������� ������ ������������ ��� ����������� ����� �� ������� ������� � ������ ��������.

������ �� ����������� ����� ��������� ����� O (\log n)? ��� ����� ��������� �� ������ ������ ������ ��������, ������� �������� �������� ����� �������� ���� ����������� ������� ��� ��������� ������-���� �������. ������������, ��� ����� �������� �� ����� ���� ����� ������; �����, �������� ������ O (\log n) ��� ������ ������, �� � �������� ������ ����������� ������� ������ ���������.

�������, ��� ��� ������ � ������ �������� �����. � ����� ����, �� ������� ������ ������ �������� ������������� ������������ ������� — ������ ������. ������ �� ������ ������ ����������� ����� � ������ ������ ����������� �� ��� ����������� ������, �� ����� ����� ��, ��� ������� � ���� ���� ������� ����� �������������, �.�. ����� l^{\prime\prime} ������� �� ������ ����������� ������ ����� �� ������� ������ ����� r^\prime ������� � ������ ����������� ������. ������ �������, ��� �� ��������� ������ ������ �� ���� ���� ������� ��� �������� ��� �� ��� ����������� ������, �� � ����� ������ �������� ���� �������� ���������� ������������, ���� ������ �������� �� ������� ������ ��������. ����� �������, ������ ��� � ��� ����� �� ����� ���� ������� ���������� ������ �������� (����� �������, ��� ���� ����� ������������ � ����� ������� �������, � ������ ����� — � ������), � ����� ����� ���������� �������� �� ����� ��������� ������ ������ ��������, ���������� �� ������, �.�. ��� ���� ����� O (\log n).

� ���������� ����� �������� � ����� ��������� ������ ������� �����: ������� ������� [l \ldots r] ����������� �� ��������� �����������, ����� �� ������ �� ������� ��� ��������� � �������� � ������. ���� ������ ��� ��������� ���������� �������, �� ��������� ��������� ������ �������� ����� ����������� ����������� ������ ����� O (\log n), ��� � ��� ������������� ������ ������ ��������.

������ ����������

��������, ��� ������ ���������� �������� �� ���� ������ i � �������� x, � ������������� ������ �������� ����� �������, ����� ��� ��������������� ������ �������� a[i]=x. ���� ������ ������ ����� ����������� �� ����� O (\log n).

��� ����� ������� ������ �� ��������� � �������� �������� �����. ���� � ���, ��� ������� a[i] ��������� ������ � ������������ ��������� ����� ������ ������ ��������: � ������, � O (\log n) �������� — �� ����� � ������� ������.

����� �������, ��� ������ ���������� ����� ����������� ��� ����������� �������: �� ��������� ������� ������� ������ ��������, � ��� ������� ��������� ����������� ����� �� ������ �� ���� ����� ������� (�� ����, ������� �������� ������� i � ���� �������), � ����� ����� — ������������� �������� ����� � ������� ������� ����� ����� �� �������, ��� �� ��� ������ ��� ���������� ������ �������� (�.�. ��� ����� �������� �� ����� �������� ������� �������).

����������

�������� �������������� ������ — ��� ��, ��� ������� ������ �������� � ������. � ����� �������� �� �� ����� ������� ������ � ����� ����, � ������������� ����� ������: ������, ��� ������ ������ ����� ����� 1, ��� ������� — ������ 23, �� ������� — ������ � 4 �� 7, � ��� �����. ����� ������ ������������ ��������� �������: ���� ������� ����� ����� i, �� ����� � ����� ��� — ��� ������� � ������� 2i, � ������ — � ������� 2i+1.

����� ���� ����������� �������� ���������������� ������ ��������, — ������ ��� �� ����� ������� � ������ ��������� ������ ��������, � ������ ���� ������� �����-���� ������ ��� ���� �� ������ ������� ������ ��������.

����� ������ ��������, ��� ������ ����� ������� ��� ����� ��������� ���� ������� �� 2n, � 4n. ���� � ���, ��� ����� ��������� �� �������� �������� � ������, ����� n �� �������� �������� ������ — ����� ���������� ����������� ������, ������� �� ������������� ������� ������� ������ (����������, ��������� ���� ���� ������� ����, ��� ���� �� n ��������� �� ����� �� ��������� ������� ������). ��� �� ������ ������� ���������� ��� ����������, ������ �������� � ����, ��� ������ ������� ���� ����������� �� 4n.

����, ������ �������� �� ������ ������ � ���� ������� t[], ������� �������� ������ ������� n ������� ������:

int n, t[4*MAXN];

��������� ���������� ������ �������� �� ��������� ������� a[] �������� ��������� �������: ��� ����������� �������, �� ��������� ��� ������ a[], ����� v ������� ������� ������, � ������� tltr �������, ���������������� ������� ������� ������. �� �������� ��������� �������� ��� ������� ������� � ����������� v=1, tl=0, tr=n-1.

void build (int a[], int v, int tl, int tr) {
	if (tl == tr)
		t[v] = a[tl];
	else {
		int tm = (tl + tr) / 2;
		build (a, v*2, tl, tm);
		build (a, v*2+1, tm+1, tr);
		t[v] = t[v*2] + t[v*2+1];
	}
}

�����, ������� ��� ������� ����� ������������ �� ���� ����� ����������� �������, ������� ����� �� ������� ��������� ���������� � ������� ������� ������ (�.�. ����� v, tl, tr, ������� � �������� ��������� ������� ���������� �������� 1, 0, n-1 ��������������), � ������ ����� — ����� ������� lr �������� �������. � ����� ��������� ���� ��� ������� ������ ������ �� ��� ����������� ������, ���� ���� �� ����� ���� ����� ���� — ������ ������� ������������ ������ ���������� ������, � �������� l > r, ��� ����� ���������� �������������� ��������� � ����� ������ �������.

int sum (int v, int tl, int tr, int l, int r) {
	if (l > r)
		return 0;
	if (l == tl && r == tr)
		return t[v];
	int tm = (tl + tr) / 2;
	return sum (v*2, tl, tm, l, min(r,tm))
		+ sum (v*2+1, tm+1, tr, max(l,tm+1), r);
}

�������, ������ �����������. ��� ����� ��� �� ��������� ���������� � ������� ������� ������ ��������, � ������������� ����������� ������ ����������� ��������, � ����� ��� ����� ��������.

void update (int v, int tl, int tr, int pos, int new_val) {
	if (tl == tr)
		t[v] = new_val;
	else {
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			update (v*2, tl, tm, pos, new_val);
		else
			update (v*2+1, tm+1, tr, pos, new_val);
		t[v] = t[v*2] + t[v*2+1];
	}
}

����� ��������, ��� ������� \rm update ����� ������� �������������, ��������� �������� � ��� ���������, �.�. ������������ ������� �� ����������: ���� ����� ����� �������� ������ ���� ����������� �����. ��� ������������� ���������� �������� ������ ����� ������� � ��������� ���.

�� ������ ����������� ����� ���������, ��� ��������� � ������� �� ��� ����� �������� �������� ���������� — ��� ����� ������� �������� ������������������ ������ ��������.

����������� ������ ������ ��������

������ �������� — ����� ������ ���������, � ��������� ������ ��������� �� ������ ��������� ������������. ���������� ���� ���������������� ��.

����� ������� ������� � �������

��������� ������ �������� � ���� ����������� ����� ���� ��� �������� ���������� (��� � ������ ��������/��������� ������ �����), ��� � ������ � ������ ��������������.

����� ��������/���������

������� ������� ������� ������, ��������� ����: ������ ������� ����� ����� ����������� ������ ������ ��������/��������� �� �������.

����� ������ �������� ��� ����� ������ ����������� ����� �� ���������� �� ������ ��������, ���������� ����. ������ ���� �������� ������ ���������� t[v] � �������� \rm build\rm update, � ����� ���������� ������������� ������ � ������� \rm sum (�������� ������������ �� �������/��������).

����� ��������/��������� � ���������� ���, ������� �� �����������

������ ���������� ����������, ������ ������ ������ ��������� ��������� ����� ���������� ���������� ��� ���������. ��� ������ ����� ������������ �������, ��������, ��� ������� � ������� ������ �������� ����� ������: ����� ���������� ������������� ������������ ���������������������� � �������� �������.

��� ������� ���� ������ � ������ ������� ������ �������� ����� ������� ���� �����: ����� ��������� ���������� ��� ��������� �� ��������������� �������. ����� ��� ���������� ������ �� ������ ������ �� ���� ����� �����, ���������� �� ������� ������� �������, �������� ���� ��� ������� �������.

����������� ���� ����� ��� � ���� ����� �������� � ��������� �������, ��������� ��� �������� ���� ����� ����������� � � ������� �����������, � � ������� ������ ���������.

pair<int,int> t[4*MAXN];
 
pair<int,int> combine (pair<int,int> a, pair<int,int> b) {
	if (a.first > b.first)
		return a;
	if (b.first > a.first)
		return b;
	return make_pair (a.first, a.second + b.second);
}
 
void build (int a[], int v, int tl, int tr) {
	if (tl == tr)
		t[v] = make_pair (a[tl], 1);
	else {
		int tm = (tl + tr) / 2;
		build (a, v*2, tl, tm);
		build (a, v*2+1, tm+1, tr);
		t[v] = combine (t[v*2], t[v*2+1]);
	}
}
 
pair<int,int> get_max (int v, int tl, int tr, int l, int r) {
	if (l > r)
		return make_pair (-INF, 0);
	if (l == tl && r == tr)
		return t[v];
	int tm = (tl + tr) / 2;
	return combine (
		get_max (v*2, tl, tm, l, min(r,tm)),
		get_max (v*2+1, tm+1, tr, max(l,tm+1), r)
	);
}
 
void update (int v, int tl, int tr, int pos, int new_val) {
	if (tl == tr)
		t[v] = make_pair (new_val, 1);
	else {
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			update (v*2, tl, tm, pos, new_val);
		else
			update (v*2+1, tm+1, tr, pos, new_val);
		t[v] = combine (t[v*2], t[v*2+1]);
	}
}

����� ����������� ������ �������� / ����������� ������ ��������

�.�. �� ����� ��������� ������ ���/��� ���� ����� � �������� ������� �������.

��� �������� ���������� ��������� ������ �������� ���������� ��������� ����� �� ����, ��� � ������� �������� ��� �����/��������/���������: ���������� ������ ������� � ������ ������� ������ ���/��� ���� ����� � ��������������� ������� �������.

������� ���������� �����, ����� k-�� ����

� ���� ������ �� ����� ��������� �������� �� ������ ���������� ����� � �������� ������� �������, � ����� �� ������ ���������� k-�� �������� ��������.

����� ������� ������� ������, ���������� � ������ ��������: ����� ������� ������ � ������� t[] ���������� �����, ������������� � ��������������� �������� �������. �������, ��� ������������ � ������������ ��� ������ � �������� \rm build, \rm sum, \rm update, — ��� ����� �� ������ ������ � ���������� ����� � �������� ������� �������.

������ �������� ������ ������ � ������ ������� k-�� ��������� ���� � �������. ��� ����� ����� ���������� �� ������ ��������, ������� � �����, � �������� ������ ��� � ������ ��� ������� ���� � ����������� �� ����, � ����� �� �������� ��������� ������� k-�� ����. � ����� ����, ����� ������, � ������ ���� ��� ���� ����������, ���������� ���������� �� ��������, ���������� � ����� ����: ���� ��� ������ ���� ����� k, �� ���������� ���� � ������ ���� (������ ��� � ��� ������� ���� ��� ������� k �����), � ����� — ���������� � ������� ����.

��� ���������� ����� ������ ������, ����� k-�� ���� �� ����������, ��� ��� ����� � �������, ������ � �������� ������, ��������, -1.

int find_kth (int v, int tl, int tr, int k) {
	if (k > t[v])
		return -1;
	if (tl == tr)
		return tl;
	int tm = (tl + tr) / 2;
	if (t[v*2] >= k)
		return find_kth (v*2, tl, tm, k);
	else
		return find_kth (v*2+1, tm+1, tr, k - t[v*2]);
}

����� �������� ������� � �������� ������

������ �����: ��������� �� ������� �������� x ������ ����� ����� i, ��� ����� ������ i ��������� ������� a[] ������ ���� ����� x (������, ��� ������ a[] �������� ������ ��������������� �����).

��� ������ ����� ������ �������� �������, �������� ������ ��� ������ ���� ����� �� ��� ��� ���� �������� �������, �� ��� ������� � ������� �� ����� O (\log^2 n).

������ ����� ����� ��������������� ��� �� ����� �����, ��� � � ���������� ������, � ������ ������� ������� ����� ������� �� ������: �������� ������ ��� � ������ ��� ������� ���� � ����������� �� �������� ����� � ����� ����. ����� ����� �� ������ ������ ����� ������������ ����� ���� ����� ����� �� ������, �, �������������, ����� ����������� �� O (\log n).

����� ���������� � ������������ ������

��-�������� �� ���� ����� ������ a[0 \ldots n-1], � ��������� ������� (l,r), ������� ��������: ����� ����� ���������� a[l^\prime \ldots r^\prime], ��� l \le l^\prime, r^\prime \le r, � ����� ����� ������� a[l^\prime \ldots r^\prime] �����������. ������� ����������� ��������� ��������� ������� �����������. �������� ������� ����� ���� �������������� (�, ��������, ���� ��� ����� ������������, �� ����������� ����������� ����� ������ — �� ��� ����� ����� ����).

��� ������ ������������� ��������� ������ �������� ���������� ��������� �������. ����� ������� � ������ ������� ������ �������� ������ ��������: ����� �� ���� �������, ������������ ����� ����� ���� ��������� ����� �������, ������������ ����� ����� ���� ���������, � ����� ������������ ����� ���������� �� ���. ����� �������, ��� ������� ������� ������ �������� ����� �� ��� ��� ������������, � ����� ������������� ����� �������� ����� ���� ��������, ����������� � ����� ������� �������, � ����� ����� ���� ��������, ����������� � ������ �������.

��� �� ��������� ������ �������� � ������ �������? ����� ������� � ����� � ����������� ����� ������: ����� ��� ������� ������� ��� ������ �������� � ����� ���� � � ������ ���� ��� ����������, ��������� �� ������ ��� ����� �������. �������, ��� ����� � ����� ������� �����:

  • ���� ������ � ����� ����, ��� ��������, ��� ������ ���������� � ������� ������� ������� ���������� � ������� ������ ����,
  • ���� ������ � ������ ����, ��� ��������, ��� ������ ���������� � ������� ������� ������� ���������� � ������� ������� ����,
  • ���� ����� ������������� �������� � ����� ���� � ������������� �������� � ������ ����, ��� ��������, ��� ������ ���������� ����� ����� ������� � ����� ����, � ������ — � ������.

������, ����� � ������� ������� ����� ��������� �� ���� ��� �������. ������������� �� ������������ ����� �� ��������� � ��������� ��� �����. ������� ���������� ������� \rm combine, ������� ����� ������������ ��� ��������� \rm data, ���������� � ���� ������ � ����� � ������ ��������, � ������� ���������� ������ � ������� �������.

struct data {
	int sum, pref, suff, ans;
};
 
data combine (data l, data r) {
	data res;
	res.sum = l.sum + r.sum;
	res.pref = max (l.pref, l.sum + r.pref);
	res.suff = max (r.suff, r.sum + l.suff);
	res.ans = max (max (l.ans, r.ans), l.suff + r.pref);
	return res;
}

����� �������, �� ��������� ������� ������ ��������. ������ ����� �������� � ���������� ������� �����������: ��� � � ����� ������� ������ ��������, �� ��������� �������� �������� �� ���� ������������ �������� ������ ��������, ��� ���� ���������� �� �� �� ������� \rm combine. ��� ���������� �������� ������ � ������� ����� ��������������� ������� \rm make\_data, ������� ���������� ��������� \rm data, ����������� �� ������ ����� \rm val.

data make_data (int val) {
	data res;
	res.sum = val;
	res.pref = res.suff = res.ans = max (0, val);
	return res;
}
 
void build (int a[], int v, int tl, int tr) {
	if (tl == tr)
		t[v] = make_data (a[tl]);
	else {
		int tm = (tl + tr) / 2;
		build (a, v*2, tl, tm);
		build (a, v*2+1, tm+1, tr);
		t[v] = combine (t[v*2], t[v*2+1]);
	}
}
 
void update (int v, int tl, int tr, int pos, int new_val) {
	if (tl == tr)
		t[v] = make_data (new_val);
	else {
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			update (v*2, tl, tm, pos, new_val);
		else
			update (v*2+1, tm+1, tr, pos, new_val);
		t[v] = combine (t[v*2], t[v*2+1]);
	}
}

�������� ����������� � ������� �� ������. ��� ����� �� ��� ��, ��� � ������, ���������� �� ������, �������� ��� ����� ������� ������� [l \ldots r] �� ��������� �����������, ����������� � ��������� ������ ��������, � ���������� ������ � ��� � ������ ����� �� ��� ������. ����� �������, ��� ������ ����� �� ���������� �� ������ �������� ������ ��������, ������ ���� ������ �������� ������������/��������/��������� �������� ������������ ������� \rm combine. ���������� ���� ���������� ������� ���������� �� ���������� ������� \rm sum: ��� �� ��������� �������, ����� ����� ������� l ������� ��������� ������ ������� r (����� ��������� ���������� ������ — ����� ��������� \rm data ����������, ����� ������� ������� ������?..).

data query (int v, int tl, int tr, int l, int r) {
	if (l == tl && tr == r)
		return t[v];
	int tm = (tl + tr) / 2;
	if (r <= tm)
		return query (v*2, tl, tm, l, r);
	if (l > tm)
		return query (v*2+1, tm+1, tr, l, r);
	return combine (
		query (v*2, tl, tm, l, tm),
		query (v*2+1, tm+1, tr, tm+1, r)
	);
}

���������� ����� ���������� � ������ ������� ������ ��������

��� ��������� ���������, ������� ��������� �� ���������, ��������� � ������ ������� ������ �������� �� ����� ������� �� �����-�� ������ ���������� �� ���� ���������� (�����, �������, �������� � �.�.), � ��� �������� �������, ������� � ���� ����������. ����� �������, ������ ������ �������� ����� ������� ��� �������� �������, ����� ��� ����� — ������ �������� �������, ������ ��� ����� — ������ ��������, � ��� �����.

����� ������� ������� ���������� ���� ������� — ����� � ������ ������� ������ �������� �������� ��������������� ������ ���� �����, ������������� � ��������������� �������. � ����� ������� ��������� �������� �� ������, � �����-���� ��������� ������, ����������� ��� ����� �������� (\rm set, \rm map � �.�.). �� ��� ��� ������ ���������� ��, ��� � ������ ������� ������ �������� �������� ����� ��������� ������, ������� � ������ ������ ������� ����� ���������������� �������.

������ ������������ ������, �������� ��� ������������ �������� �������� ����� ������ — ��� ����� ������������ ������. ������������, ��� ���� � ������ ������� ������ �������� �������� ������ ���� ������������� �� ���� ������� �����, ���� ����� ������ ��������� ������ ������� ���� �� �������, �� � ����� �� ������ �������� ����� �������� O (n \log n) ����� ������. ������ ��� ���? ������ ��� ������ ����� a[i] �������� � O (\log n) �������� ������ �������� (���� �� ������, ��� ������ ������ �������� ���� O (\log n)).

����, �������� �� ��������� ���������������� ������ ������ ��������, �� ���������� ������ �� ������ ������ �������� ������ ��������.

���� ������� ��������� �������� ���������� ����� ��������� ������. ����� ����� �������� ����� �������� �������� �������� ����� ���� � ���������� ����������� ������ (����������, � �����-�� ������ ��� � ���� ��������� ��������� ������, �� � �������� ������������� �������������).

����� ����������� �����, ������ ���� ������� ���������, � ��������� �������. �������� ����������� ���

��������� �������� �� ������� ���������� ����: (l,r,x), ��� �������� ����� ����������� ����� � ������� a[l \ldots r], ������� ������ ���� ����� x.

�������� ������ ��������, � ������� � ������ ������� ����� ������� ��������������� ������ ���� �����, ������������� �� ��������������� �������. ��������, ������ ����� ��������� ������ a[] � ��������������� ����. ��� ��������� ����� ������ �������� ����������� ����������? ��� ����� ������� � ������, ��� ������, � ����� ������ ��������: ����� ��� ������ � ������� ������� ������� ������� ��� ������ ��� ���������, � ��� ��������� ��������� ���� ������ ��� ������� �������. ��� ����� ���������� ������� ���������� ����� ��������, ��� ��� ����� ������� �� �������� �����: ��� ������ ���� ���������� ��� ��������������� ������ � ����, ��� �������� ����� �������� �� ��� � ����� �����������. ������������� C++ ��� �����, ������ ��� ���� �������� ������� ��� ������� � ����������� ���������� STL:

vector<int> t[4*MAXN];
 
void build (int a[], int v, int tl, int tr) {
	if (tl == tr)
		t[v] = vector<int> (1, a[tl]);
	else {
		int tm = (tl + tr) / 2;
		build (a, v*2, tl, tm);
		build (a, v*2+1, tm+1, tr);
		merge (t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
			back_inserter (t[v]));
	}
}

�� ��� �����, ��� ����������� ����� ������� ������ �������� ����� �������� O (n \log n) ������. � ��������� ����� ���������� ����� ��� ���������� ����� ���� �������� O (n \log n) — ���� ������ ������ �������� �� �������� ������������ ��� ������� �����. (������ ������, ����� �������������� ��������� �������� � ���������� ���������� ��������: ������ ����� �� ��������� ���������� �� ���� ������ ������ ���������, � �� ������ ����.)

������ ���������� ����� �� ������. ����� ���������� �� ������, ��� ��� ������ ����������� ����� �� ������ � ������ ��������, �������� ��� ������� a[l \ldots r] �� ��������� ����������� (������� O (\log n) ����). �������, ��� ����� �� ��� ������ ����� �������� ����� ������� �� ������ �� ���� �����������. ����� ������, ��� �������� �� ������ �� ����� ����� ����������, ����������� � ��������� �������� ������.

����, �� ������ � �����-�� ������� ������ �������� � ����� ��������� ����� �� ���, �.�. ����� ����������� �����, ������ ���� ������ ������� x. ��� ����� ��� ����� ���� ���� ��������� �������� ����� �� ������, ������������ � ���� ������� ������, � ������� ������ ����� �� ����� ������, ������ ���� ������ x.

����� �������, ����� �� ������ � ����� ���������� ���������� �� O (\log n), � ���� ������ �������������� �� ����� O (\log^2 n).

int query (int v, int tl, int tr, int l, int r, int x) {
	if (l > r)
		return INF;
	if (l == tl && tr == r) {
		vector<int>::iterator pos = lower_bound (t[v].begin(), t[v].end(), x);
		if (pos != t[v].end())
			return *pos;
		return INF;
	}
	int tm = (tl + tr) / 2;
	return min (
		query (v*2, tl, tm, l, min(r,tm), x),
		query (v*2+1, tm+1, tr, max(l,tm+1), r, x)
	);
}

��������� \rm INF ����� ���������� �������� �����, �������� ��������, ��� ����� ����� � �������. ��� ���� ����� "������ � �������� ������� �� ����������".

����� ����������� �����, ������ ���� ������� ���������, � ��������� �������. ����������� ������� �����������

������ ���������� ����������, ������ ������ ��������� ������� �����������: ���������� ���������� a[i] = y.

������� ����� ���������� ������� ���������� ������, ������ ������ ������� ������� � ������ ������� ������ �������� �� ����� ������� ���������������� ������, ������� ��������� ������ ������ ��������� �����, ������� ���, � ����� ��������� ����� �����. ��������, ��� ������ ������ ����� �� ������� ������� ����� �����������, ����������� ������� �������� ��������� ������ STL \rm multiset.

���������� ������ ������ �������� ���������� �������� ��� ��, ��� � � ���������� ������, ������ ������ ���� ���������� �� ��������������� ������, � \rm multiset, ��� ������� � ����, ��� ����������� ���������� ��������� �� n \log^2 n (����, ��-��������, ������-������ ������� ��������� ��������� ������� ���� �������� �� �������� �����, ������ ���������� STL ����� �� �����������).

����� �� ������ ������ ������ ����������� ������������ ����������� ���� ����, ������ ������ \rm lower\_bound ���� �������� �� t[v].

�������, ������ �����������. ��� ��� ��������� �� ������ ���������� �� ������, ����� ��������� �� ��� O (\log n) �������, ���������� ������������� �������. �� ������ ������� ������ �������� ����� �������� (�� �����, ��� ��� �� ���� ������� ������ � ��� ��� ������� ����� �����) � ��������� ��� ����� ��������.

void update (int v, int tl, int tr, int pos, int new_val) {
	t[v].erase (t[v].find (a[pos]));
	t[v].insert (new_val);
	if (tl != tr) {
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			update (v*2, tl, tm, pos, new_val);
		else
			update (v*2+1, tm+1, tr, pos, new_val);
	}
	else
		a[pos] = new_val;
}

��������� ����� ������� ���������� ����� �� ����� O (\log^2 n).

����� ����������� �����, ������ ���� ������� ���������, � ��������� �������. ��������� � ������� ������� "���������� ��������������"

������� ����� ������ �� ������ ������ �� ������� O (\log n) � ������� ���������� ������� "���������� ��������������" ("fractional cascading").

��������� �������������� — ��� ������� ����, ������� ��������� �������� ����� ������ ���������� �������� �������, ��������� �� ������ � ���� �� ��������. � ����� ����, ����� �� ������ ������ ����������� � ���, ��� �� ��������� ���� ������ �� ��������� ��������, ������ �� ������� ����� �������� �������� ������� �� ����� x. ��������� �������������� ��������� �������� ��� ��� �������� ������ �� ����.

���������� � ����� ��������� �������� ���������� �������������� �������� ��������� ������: ���� ��������� ��������������� ������� �����, � �� ������ � ������ ������ ����� ������ �����, ������ ���� ������ ���������.

���� �� �� ������ ������ "� ���", �� ��������� ���� �� ��������� �������� ����� �� ������� �� ���� �������, ���, ���� ���� ������� �����, ���������� ������ ������������ ��������: ���� ����� ������� k, �� ����������� ��������� O (k \log(n/k)), ��� n — ��������� ������ ���� ������� (����������� ������, ������ ��� ������ ������ — ����� ��� ������ �������� ����� ���� ����� �� �����, �.�. ����� n/k).

������ �����, �� ����� �� ���������� ��� ��� ������ � ���� ��������������� ������, � ������� ��� ������� ����� n_i ����� ������� ������ �������: ������� � ������ ������ ������� �����, ������ ���� ������� n_i, ����������� ������� �� ������ ������, � ��� �����. ����� �������, ��� ������� �������������� ����� �� ������ ������ � ���� ������ ���������� �������� ������� �� ���� � ������ �� �������. � ����� ������ ����������� ������ �� ������ ���������� O (\log n + k), ��� ����������� �����, ������ �� ��������� �������������� ������� ������������ ������: � ������, ��� ��������� O (nk) ����� ������.

������� ���������� �������������� ��� ������ � ������� ���� ������ � ���������� ����������� ������ O (n) ��� ��� �� ����� ������� ������ �� ������ O (\log n + k). (��� ����� �� ������ �� ���� ������� ������ ����� n, � ����� ������������ � k �������, �� ������ � ������ ������� ������ ������ ������ ������� �� ���������� ������; ��� ����� ������� ������ � ������ ������ ���������� ��� ������� � ����� ������� (������� � ���������), ������ ��� �������� ��-�������� ���������� �������� �� ������: �� ������ �������� ����� �� ������� ������, � ����� ��� �� ���� ������� �� �������, �������� ������ ��� � ��������� ������ � ������� ��������������� ����������, � ����� ���� ��� �����, �������� ��� �����, ��� �������� ����� ���������� ������ ������ �� ����).

�� ��� � ����� ���������� � ������ �������� �� ����� ������ ���� ���� �������. ���� � ���, ��� ������ � ������� ������� �������� ��� �����, ������� ����� ����������� � ����� � ������ ��������. �������, ����� �������� ��������� ������ �� ������ ����, ��� ���������� ��� ������� ������ � ������ �������� ��������� ��� ������� ����� ��� ������� � ������� ������ � ������� ������� (������, ������� ������� �����, �������� ���� ������� ��������).

����� �������, ������ �������� ������ ���� ����� �� ������ ������ �����: ���� �����, ������� � ������ ������ ����, ������� � ������ ������� ����. ��� �������� ��� �� O (1) ���������� ������� � ������ ������ ��� ������� ����, ������ ���� ����� ������ �������� ������ �� ����.

����� ����� ��� ������� ��������� � ������, ����� ������� ����������� �����������, — ����� ��� ������� ������������ ����� ������ �����, � ������������ �� ��� ���������� ������ ����� ����� ������ ��������� ������� ���� ��������������� �������������������.

� ������, ����� ��������� ������� �����������, �� ��������� �����������: ��� ������� ������ ���� ������� � ���� ���������� ������ \rm multiset, � ��� ������� ���������� — ��������� ���������/����������� ��� ��� ���������, ��� ������� ��� ���������.

��� ��� �����, ������ ��� �������� � ����� �������������� ���������, � �������� ���� — ������ O (\log n) �������� ������� ����� �������� ������� �� ������ � ����� ������ — ������� ���������.

������ ��������� �����������

�������, ��� ��� ������� ������������� ��� ����� ����� ����� ��������� ���������� — �� ������������ ���������� ������, ��������� ��� �������� � ������ ������� ������. ���� ���� ����������� ���������� � �������������� \rm vector\rm multiset, � �� ����� ��� ������ �������������� ����� ����� ������ ���������� ��������� ������: ������ ������ �������� (�� ���� ������� ������� ���� � ������� � ����������� �������� ��������), ������ �������, ��������� ������ � �.�.

���������� �� �������

���� ��������������� ������ ������, ����� ������ ����������� ����������� ������������ ������� �������. �� ����� ����, ������ �������� ��������� ������ �������, ������� ����������� � ����� �������� ������ ������ ���������, ������ ��������� ��� ������� �� �� �� ����� O (\log n).

����������� �� �������

������ ������������ �������� �������� ������ ���� � ������ �������� ������: ������ ����������� ������������ ����� ����������� �� ���� ������ �� ��������� ���������� a[l \ldots r] ���������� ����� x. ������ ������ — ��-�������� ���������� �������� ���������� ����� a[i].

����� ������ ������ ����������� ����������, ����� ������� � ������ ������� ������ ��������, ������� ���� ��������� �� ���� ������ ����� ������� �������. ��������, ���� �������� ������ "��������� �� ����� ������� a[0 \ldots n-1] ����� 2", �� �� �������� � ����� ������ ����� 2. ��� ����� �� ������ ������������ ������ ����������� �� ����� ���������� ����������, ������ ���� ����� �������� ��� O (n) ��������.

���� ������ �������� ������ ������ �������� ���� ��� ����� �����, �� ��� ���������� ���������� �� ������, ������������� ��� ����������� �� ���� ��������, ���������� � �������� ������.

void build (int a[], int v, int tl, int tr) {
	if (tl == tr)
		t[v] = a[tl];
	else {
		int tm = (tl + tr) / 2;
		build (a, v*2, tl, tm);
		build (a, v*2+1, tm+1, tr);
	}
}
 
void update (int v, int tl, int tr, int l, int r, int add) {
	if (l > r)
		return;
	if (l == tl && tr == r)
		t[v] += add;
	else {
		int tm = (tl + tr) / 2;
		update (v*2, tl, tm, l, min(r,tm), add);
		update (v*2+1, tm+1, tr, max(l,tm+1), r, add);
	}
}
 
int get (int v, int tl, int tr, int pos) {
	if (tl == tr)
		return t[v];
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		return t[v] + get (v*2, tl, tm, pos);
	else
		return t[v] + get (v*2+1, tm+1, tr, pos);
}

���������� �� �������

����� ������ ������ ����������� ������������ ����� ���������� ���� ��������� ���������� ������� a[l \ldots r] ���������� �������� p. � �������� ������� ������� ����� ������������� ���������� �������� ������� a[i].

����� ������ ����������� �� ����� �������, ������� � ������ ������� ������ �������� �������, �������� �� ���� ������� ������� � �����-���� ����� ��� ��� (� ���� ��������, �� ������� ���� ��� �����). ��� �������� ��� ������ "�������������" ���������� ������ ��������: ��� ������� ����������� ��, ������ ���� ����� ������ �������� �� ��������� ������ ������ ��������, �������� ������ ��������� �� ���, ������� ����� "��������" ��� ������ ��������, ��� ��������, ��� ���� ���� ������� ������ �� ������ ������������ ������ ���� �������� � ���� ����.

����, ����� ���������� ������� ����������� ������ �������� ����������, ������ ������, ������������ — � ��� �������� ���������������� ��������� �����������.

��������, ���� ������ ������ ����������� "��������� ����� ������� a[0 \ldots n-1] �����-�� �����", �� � ������ �������� �� ������� ������������ ��������� — ������� ������ ������, ��� �� �������� ������� � ��� �����. ��������� �� ������� ������ ��������� �������������, ���� �� ����� ���� �� ������ ������ ���� ��������� � ���� � �� �� �����.

����������� ������, ��� � ��� �� ������ �������� ������ ������ ������ ����������� — ��������� ������ �������� ������� a[0 \ldots n/2] � �����-���� ������ �����. ����� ���������� ����� ������, �� ������ ��������� ������� ������ ���� ����� � ���� ����� ����, ������ ����� ��� ��� ������� ���, �� ������ ����������� � ������ ������. �������� ����� � ���, ��� � ������ ������ �����������, ��� ������ �������� ��������� � ������ ����, � � ������ ������ � ������ ������� ���������� ��� ������ �������� �� ���������.

����� �����: ���������� ������������� ���������� �� �����, �.�. ���� ������ ������ ��� �������� � �����-���� �����, �� ��������� � ��� ����� ��� ������� � ������ ����, � �� ����� ��� ������� ������. ����� ����� �� ����� �������� ������� ������ ���� �����, �� ����� ������� ������ ����������.

�������, ��������: ��� ����� �������� � ����� ������� (������ ����������� ��� ������) �� ����� ������ �� ������ �� ������ ������ ������ ������������� ���������� �� ������� ������� � ����� � �������. ����� �������� ��� ���, ��� ��� ������ �� ������ �� ��������� ������������� �����������, �� ����� ���������, ��������� ��� ���������� (����� �� �������� ����������� � O (\log n)).

��� ���������� ��� ��������, ��� ��� ���� ������� ������� \rm push, ������� ����� ������������ ������� ������ ��������, � ��� ����� ����������� ������������� ���������� �� ���� ������� � ����� � �������. �������� ��� ������� ������� � ����� ������ ������� ��������� �������� (�� �� �������� � �� �������, ���� �� ����� ������������ ���������� �� ����, �� � ������).

void push (int v) {
	if (t[v] != -1) {
		t[v*2] = t[v*2+1] = t[v];
		t[v] = -1;
	}
}
 
void update (int v, int tl, int tr, int l, int r, int color) {
	if (l > r)
		return;
	if (l == tl && tr == r)
		t[v] = color;
	else {
		push (v);
		int tm = (tl + tr) / 2;
		update (v*2, tl, tm, l, min(r,tm), color);
		update (v*2+1, tm+1, tr, max(l,tm+1), r, color);
	}
}
 
int get (int v, int tl, int tr, int pos) {
	if (tl == tr)
		return t[v];
	push (v);
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		return get (v*2, tl, tm, pos);
	else
		return get (v*2+1, tm+1, tr, pos);
}

������� \rm get ����� ���� �� ����������� � ��-�������: �� ������ � ��� ������������� ����������, � ����� ���������� �����, ��� ������ ��� �������� � ������� ������ ��������, ������� ����������� � ��� ��� ���� ����.

����������� �� �������, ������ ���������

����� ������ �������� ����������� ����� ����� ������ ����������� �� ���� ������ ���������� ���������� ������ � ���� �� �����, � �������� ������ ����� ���������� ��������� � ��������� ����������.

����� � ������ ������� ������ �������� ���� ����� ������������� ������� �������� �� ��� ���� ����������. �� �������� ����� ����������� � ���, ��� ���� ������������� ��� ��������.

��������, ����� ��������� ������ "��������� �� ���� ������ ��������, �.�. a[0 \ldots n/2], ����� 2". ����� � ������ ��� ��������� ������� ����� 2 � ������ ���� �����. ��� ������ ��������� ����� �������� ��������� � ����� ���� � � �����? ����� ���������� ����� �� ���������� — ����� �������� �������� � ������� ������: �������� ��� ����� ����������� �� ���� ���� �������, ��� �� � ������ ���. ������� ����� ����� �� ���� ��������, �� ������� — ��������������� ������������ ��� �����. ��������, ��� ������ ������� �������� � ����� ����� ���������� ��� �������� �� ���� �����: �������� � ����� ���� ���� ����������� � ����� ����, � �������� � ������ ���� ���� ����������� � ���. ��� ������ �� ������� �������� � ����� ����� ���������� ��� ����������� � ����� ���� �������� �� ���������� � ����� � ������ ��������.

������ �����������

����� ���� ����������� ������ ������� ���������� �������� �������� � ������� � ������������� �� �������. ��������� ������ ���������� �� ������ ��� �� ����� ����, ��� ������� �����.

����� ������ ���� ����� ���������� ��� ������ � ����������� �������������: ������� �������, ��� ���� ���� � ������� ������� �� ��� "�����������" ���������� �����������, �� � ����� � ������ ��������, ������ �����, ����� ��� �� �������. ������� ����� ����������� �������� �������� \rm push ����� �� ������ � ������� ������� ������� �������, ���� �� ��������� ��������� ���������� ����������� � ���.

��������� �� ������� �����������

������ �������� ���������� ������ ������������ ������� �� ��������� � ������ ����������� ������. ���� � ���������� ������ �� ��������� ������� ������� �� �������, �� � ��������� ������ ������ ����� ������� ��������� �� �� ������ ��������, � ��� ������� ������� �� ������ �������� — ������� ������� ������ �������� �� ������ ��������. ����� �������, �������� ���� ������� — ��� ����������� �������� �������� �� ������ �������� ������ ������ �������� �� ������ ��������.

������� ��� ���� �� ������� ���������� ������.

��������� ������ �������� � ���������� ��������

���� ������������� ������� a[0 \ldots n-1, 0 \ldots m-1], � ��������� ������� ������ ����� (��� ��������/���������) �� ��������� ������������������ a[x_1 \ldots x_2, y_1 \ldots y_2], � ����� ������� ����������� ��������� ��������� ������� (�.�. ������� ���� a[x][y] = p).

����, ����� ������� ��������� ������ ��������: ������� ������ �������� �� ������ ���������� (x), ����� — �� ������ (y).

����� ������� ���������� ��� ����� �������, ����� �� ����� ������, ��� �������� ������ ��� ���������, � �������� ������ ������ ����������. ����� ������� ������� ���������� ������ ��������, ������� ������ � ������ �����������. �� � �������� �������� ������� ������� �� ����� ���������� �� �����-�� �����, ��� � ���������� ������, � ����� ������ ��������: �.�. � ���� ������ �� ����������, ��� � ��� ���� ��� � ������ ����������; �� �.�. � ���� ������ ��� �������������, ��� ������ ���������� ���� ��������� ������� [l \ldots r], �� �� ���������� �������� � ����� ������� a[l \ldots r, 0 \ldots m-1], � ��� �� ������ ������ ��������.

������� ���������� �������� ���������� ���������� ������. ��� ���������� ������������ ����� ��� ��������� �����: ���������� ������ �������� �� ���������� x (\rm build\_x) � �� ���������� y (\rm build\_y). ���� ������ ������� ����� ����� �� ���������� �� �������� ����������� ������, �� ������ ��������� ����������� �������� � ����� ��������: ����� ������� ������� �� ������ ���������� ([tlx \ldots trx]) ����� ��������� �����, � ����� — �����, ������� �������. � ������ ������ �� ������ ���� ������ �������� �� ������� a[][], � �� ������ — ���������� �������� ���� �������� �������� �� ������ ���� � ������� ���� �� ���������� x.

void build_y (int vx, int lx, int rx, int vy, int ly, int ry) {
	if (ly == ry)
		if (lx == rx)
			t[vx][vy] = a[lx][ly];
		else
			t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
	else {
		int my = (ly + ry) / 2;
		build_y (vx, lx, rx, vy*2, ly, my);
		build_y (vx, lx, rx, vy*2+1, my+1, ry);
		t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
	}
}
 
void build_x (int vx, int lx, int rx) {
	if (lx != rx) {
		int mx = (lx + rx) / 2;
		build_x (vx*2, lx, mx);
		build_x (vx*2+1, mx+1, rx);
	}
	build_y (vx, lx, rx, 1, 0, m-1);
}

����� ������ �������� �������� ��-�������� �������� ����� ������, �� ��� � ������� ����������: 16 n m ����� ������. �������, ��� �������� ��� ��������� ���� ���������� \rm build\_x ���� �� �������� �����.

�������� ������ � ��������� ��������. �������� �� ��������� ������ ����� �� ���� �� ������ ��������: ������� ��������� ������ �� ������ ����������, � �����, ����� �� ����� �� �����-�� ������� ������ �������� �� ������ ���������� — �������� ������ �� ���������������� ������ �������� �� ������ ����������.

int sum_y (int vx, int vy, int tly, int try_, int ly, int ry) {
	if (ly > ry)
		return 0;
	if (ly == tly && try_ == ry)
		return t[vx][vy];
	int tmy = (tly + try_) / 2;
	return sum_y (vx, vy*2, tly, tmy, ly, min(ry,tmy))
		+ sum_y (vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry);
}
 
int sum_x (int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
	if (lx > rx)
		return 0;
	if (lx == tlx && trx == rx)
		return sum_y (vx, 1, 0, m-1, ly, ry);
	int tmx = (tlx + trx) / 2;
	return sum_x (vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry)
		+ sum_x (vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry);
}

��� ������� �������� �� ����� O (\log n \log m), ��������� ��� ������� ���������� �� ������ �� ������ ����������, � ��� ������ ���������� ������� ����� ������ — ������ ������ � �������� ������ �������� �� ������ ����������.

�������, ���������� ������ �����������. �� ����� ��������� �������������� ������ �������� � ������������ � ���������� �������� ������-���� �������� a[x][y] = p. �������, ��� ��������� ���������� ������ � ��� �������� ������� ������ ��������, ������� ��������� ���������� x (� ����� ����� O (\log n)), � ��� �������� ��������, ��������������� �� — ��������� ����� ������ � ��� ��������, ������� ��������� ���������� y (� ����� ����� O (\log m)). ������� ���������� ������� ����������� �� ����� ������ ���������� �� ����������� ������, ������ ������ �� ������� ���������� �� ������ ����������, � ����� — �� ������.

void update_y (int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
	if (ly == ry) {
		if (lx == rx)
			t[vx][vy] = new_val;
		else
			t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
	}
	else {
		int my = (ly + ry) / 2;
		if (y <= my)
			update_y (vx, lx, rx, vy*2, ly, my, x, y, new_val);
		else
			update_y (vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
		t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
	}
}
 
void update_x (int vx, int lx, int rx, int x, int y, int new_val) {
	if (lx != rx) {
		int mx = (lx + rx) / 2;
		if (x <= mx)
			update_x (vx*2, lx, mx, x, y, new_val);
		else
			update_x (vx*2+1, mx+1, rx, x, y, new_val);
	}
	update_y (vx, lx, rx, 1, 0, m-1, x, y, new_val);
}

������ ���������� ������ ��������

����� ������ ���������: ���� n ����� �� ���������, �������� ������ ������������ (x_i,y_i), � ��������� ������� ���� "��������� ���������� �����, ������� � �������������� ((x_1,y_1),(x_2,y_2))". �������, ��� � ������ ����� ������ ���������� ������������ �������������� ������� ��������� ������ �������� � O (n^2) ����������. ������� ����� ���� ������ ����� ��������� �������, ��������� ������ �������� ������ ����� ����� ������� ������ � O (\log n) �������� ������ �������� �� ������ ����������, �, ������, ��������� "��������" ������ ���� �������� �������� �� ������ ���������� ���� �������� O (n \log n).

����� �������� ��������� �������: � ������ ������� ������ �������� �� ������ ���������� ����� ������� ������ ��������, ����������� ������ �� ��� ������ �����������, ������� ����������� � ������� ������� ������ ���������. ����� �������, ��� ���������� ������ �������� ������ �����-�� ������� � ������� vx � ��������� tlx, trx �� ����� ������������� ������ �� �����, ������� �������� � ���� ������� x \in [tlx; trx], � ������� ������ �������� ������ ��� ����.

��� ����� �� �������� ����, ��� ������ ������ �������� �� ������ ���������� ����� �������� ����� ������� ������, ������� � ������. � ����� ��������� ����� ������ ���������� �� O (n \log n). �������� �� ������ �� ����� ��-�������� �� O (\log^2 n), ������ ������ ��� ������ ������� �� ������ �������� �� ������ ���������� �� ������ ����� ������� �������� ����� �� ������ ����������, �� ����������� ��� �� �������.

�� ��������� ������ ������������� ������ ������������ ������ �����������: � ����� ����, ���� �������� ����� �����, �� ��� ������� � ����, ��� �� ������ ����� � �����-���� ������ �������� �� ������ ���������� �������� ����� ������� � ��������, ��� ���������� ������� ����������.

� ���������� �������, ��� ������ ��������� ������� ��������� ������ �������� ���������� ����������� ������������� ��������� ���� ����������� ����������� ������ �������� (��. "���������� ����� ���������� � ������ ������� ������ ��������"). � ���������, ����������, ��� ����������� ����� ��������� ������ �������� — ��� ������ ������� ������ ���������� ���������� � ������ ������� ������, ��� ��������� ��� �������� � ���� ������ ��������. ������ �������, ��� ���� ���������� ������������ �� ���������� ������ �������� �� ������� ������������� ���������� ���� ��� ����� �������, �� ����� ����� ����������� �������� ��������� ������ �������� �� �����-���� ����� ������ ��������� ������, ��������, ��������� ������.

������ �������� � ����������� ������� ��� �������� (��������� �� persistent-��������� ������)

Persistent-���������� ������ ���������� ����� ��������� ������, ������� ��� ������ ����������� ���������� ��� ���������� ���������. ��� ��������� ��� ������������� ���������� � ����� ������������ ��� ������ ���� ��������� ������ � ��������� ������ �� ���.

������ �������� �������� ����� �� ��� �������� ������, ������� ����� ���� ���������� � persistent-��������� ������ (����������, �� ������������� ����������� persistent-���������, � �� �����, ������� �������� ��� ���� ������� ����� ������ �����������).

� ����� ����, ����� ������ ��������� � ������ �������� �������� � ��������� ������ � O (\log n) ��������, ������ ����� ����, ������������� �� �����. ������, ���� �� ����� ������� ������ �������� �� ���������� (�.�. ��������� �� ������ � ������� ������� ������� �����������, ����������� � �������), �� ��� ������� ���������� �� ������ ������ ������ ��������� ��������� ������ ������� ����� �������, ������ �� ������� ���������� �� ������ �������. ��� �����, ��� ������� ���������� ����� ������� O (\log n) ����� ������, � ��� ����� ����� ������ ����� ������ ������ ��������, � ��� ����������� ������ ������, ����������� �� ������ ������, ��������� ��� ���������.

������� ������ ���������� ��� ����������� ������ ��������: ����� ���� ������ ������ �������� ����� �� ���������� � ������ ����������� ������������� �����.

struct vertex {
	vertex * l, * r;
	int sum;
 
	vertex (int val)
		: l(NULL), r(NULL), sum(val)
	{ }
 
	vertex (vertex * l, vertex * r)
		: l(l), r(r), sum(0)
	{
		if (l)  sum += l->sum;
		if (r)  sum += r->sum;
	}
};
 
vertex * build (int a[], int tl, int tr) {
	if (tl == tr)
		return new vertex (a[tl]);
	int tm = (tl + tr) / 2;
	return new vertex (
		build (a, tl, tm),
		build (a, tm+1, tr)
	);
}
 
int get_sum (vertex * t, int tl, int tr, int l, int r) {
	if (l > r)
		return 0;
	if (l == tl && tr == r)
		return t->sum;
	int tm = (tl + tr) / 2;
	return get_sum (t->l, tl, tm, l, min(r,tm))
		+ get_sum (t->r, tm+1, tr, max(l,tm+1), r);
}
 
vertex * update (vertex * t, int tl, int tr, int pos, int new_val) {
	if (tl == tr)
		return new vertex (new_val);
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		return new vertex (
				update (t->l, tl, tm, pos, new_val),
				t->r
			);
	else
		return new vertex (
				t->l,
				update (t->r, tm+1, tr, pos, new_val)
			);
}

� ������� ����� ������� ����� ���������� � persistent-��������� ������ ����������� ����� ������ ��������.