pku2761 Feed the dogs

这个题有多种做法
因为区间没有包含与被包含的，所以可以按照从左到右的顺序依次处理
处理到某个区间[i, j]，可以通过确保[1, j]之间的元素都进入某个容器一次，且之后[1, i)之间的元素都出去某个容器一次，使得容器中存的是[i, j]之间的元素
然后要求这个容器能够高效地回答里面存的第k大的元素是多少，这步可以用各种平衡树或者树状数组+二分实现，我写的是线段树

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100005;
int tree[maxn * 4] = {0}, n, m;

void change(int val, int d)
{
	int low = 1, high = n, mid, node = 1;
	tree[1] += d;
	while (low < high)
	{
		mid = (low + high) / 2;
		if (val <= mid) {
			high = mid;
			node = node * 2;
		} else {
			low = mid + 1;
			node = node * 2 + 1;
		}
		tree[node] += d;
	}
}

int lower(int k)
{
	int low = 1, high = n, mid, node = 1;
	while (low < high)
	{
		mid = (low + high) / 2;
		if (k <= tree[node * 2]) {
			high = mid;
			node = node * 2;
		} else {
			k -= tree[node * 2];
			low = mid + 1;
			node = node * 2 + 1;
		}
	}
	return low;
}

struct interval {
	int left, right, k, dog, id;
	bool operator <(const interval &rr) const
	{ return left < rr.left || left == rr.left && right < rr.right; }
} in[50001 + 5];

struct data_t {
	int val, oldID, newID;
} data[maxn];
bool cmp1(const data_t &a, const data_t &b)
{ return a.val < b.val; }
bool cmp2(const data_t &a, const data_t &b)
{ return a.oldID < b.oldID; }

int toVal[maxn], ans[maxn];

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &data[i].val);
		data[i].oldID = i;
	}
	sort(data + 1, data + n + 1, cmp1);
	for (int i = 1; i <= n; ++i)
	{
		data[i].newID = i;
		toVal[i] = data[i].val;
	}
	sort(data + 1, data + n + 1, cmp2);
	
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d%d", &in[i].left, &in[i].right, &in[i].k);
		in[i].id = i;
	}
	sort(in + 1, in + m + 1);
	
	int i, j, t;
	i = j = 1;
	for (t = 1; t <= m; ++t)
	{
		while (j <= in[t].right)
			change(data[j++].newID, 1);
		while (i < in[t].left)
			change(data[i++].newID, -1);
		in[t].dog = toVal[lower(in[t].k)];
	}
	
	for (int i = 1; i <= m; ++i)
		ans[in[i].id] = in[i].dog;
	for (int i = 1; i <= m; ++i)
		printf("%d\n", ans[i]);
	return 0;
}