BZOJ4552（二分+线段树）

要点

• 序列是n个不同的数，则新学到的一种策略就是二分这个位置的答案，然后可以上下调。
• 神奇地只关注大于还是小于mid并赋值0、1，这样m个操作的排序就能用线段树维护了！

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

int n, m, a[maxn], op[maxn], L[maxn], R[maxn], question;

class SegmentTree {

public:

	#define ls(p) p << 1

	#define rs(p) p << 1 | 1

	struct Node {

		int l, r, sum, tag;

	}t[maxn * 3];

	void Push_up(int p) {

		t[p].sum = t[ls(p)].sum + t[rs(p)].sum;

	}

	void Change(int son, int fa) {

		t[son].tag = t[fa].tag;

		t[son].sum = t[fa].tag * (t[son].r - t[son].l + 1);

	}

	void Push_down(int p) {

		if (t[p].tag < 0)	return;

		Change(ls(p), p), Change(rs(p), p);

		t[p].tag = -1;

	}

	void Build(int l, int r, int p, int val) {

		t[p].l = l, t[p].r = r, t[p].tag = -1;

		if (l == r) {

			t[p].sum = a[l] >= val;

			return;

		}

		int mid = (l + r) >> 1;

		Build(l, mid, ls(p), val);

		Build(mid + 1, r, rs(p), val);

		Push_up(p);

	}

	void Modify(int l, int r, int p, int k) {

		if (l <= t[p].l && t[p].r <= r) {

			t[p].tag = k;

			t[p].sum = k * (t[p].r - t[p].l + 1);

			return;

		}

		Push_down(p);

		int mid = (t[p].l + t[p].r) >> 1;

		if (l <= mid)	Modify(l, r, ls(p), k);

		if (mid < r)	Modify(l, r, rs(p), k);

		Push_up(p);

	}

	int Query(int l, int r, int p) {

		if (l <= t[p].l && t[p].r <= r)	return t[p].sum;

		Push_down(p);

		int mid = (t[p].l + t[p].r) >> 1;

		if (l > mid)	return Query(l, r, rs(p));

		if (r <= mid)	return Query(l, r, ls(p));

		return Query(l, r, ls(p)) + Query(l, r, rs(p));

	}

};

bool OK(int mid) {

	SegmentTree tree;

	tree.Build(1, n, 1, mid);

	for (int i = 1; i <= m; i++) {

		int val = tree.Query(L[i], R[i], 1);

		if (val == 0 || val == R[i] - L[i] + 1)	continue;

		if (op[i]) {

			tree.Modify(L[i], L[i] + val - 1, 1, 1);

			tree.Modify(L[i] + val, R[i], 1, 0);

		} else {

			tree.Modify(R[i] - val + 1, R[i], 1, 1);

			tree.Modify(L[i], R[i] - val, 1, 0);

		}

	}

	return tree.Query(question, question, 1) == 1;

}

int main() {

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)

		scanf("%d", &a[i]);

	for (int i = 1; i <= m; i++)

		scanf("%d %d %d", &op[i], &L[i], &R[i]);

	scanf("%d", &question);

	int l = 1, r = n, ans;

	while (l <= r) {

		int mid = (l + r) >> 1;

		if (OK(mid))	ans = mid, l = mid + 1;

		else	r = mid - 1;

	}

	return !printf("%d\n", ans);

}