【Luogu P2824】[HEOI2016/TJOI2016]排序

题目大意：

给出一个 (1) 到 (n) 的排列，(m) 次操作让某区间升序排或降序排，问 (q) 位置最后是多少。

正文：

本题十分巧妙，二分一个 (k)，排列里大于 (k) 的数为 1，否则为 0，线段树维护这个 01串，进行排序，再根据 (q) 的位置调整二分范围。

代码：

struct SegmentTree
{
	struct Node
	{
		int l, r;
	} SMT[N << 2];
	int lazy[N << 2], val[N << 2];
	
	void pushup(int x)
	{
		val[x] = val[x << 1 | 1] + val[x << 1];
	}
	void pushdown(int x)
	{
		if(~lazy[x])
		{
			val[x << 1] = lazy[x] * (SMT[x << 1].r - SMT[x << 1].l + 1);
			val[x << 1 | 1] = lazy[x] * (SMT[x << 1 | 1].r - SMT[x << 1 | 1].l + 1);
			lazy[x << 1] = lazy[x];
			lazy[x << 1 | 1] = lazy[x]; 
			lazy[x] = -1;
		}
	}
	
	void prework()
	{
		memset(lazy, -1, sizeof lazy);
		memset(val, 0, sizeof val);
	}
	
	void build(int x, int l, int r, int k)
	{
		SMT[x].l = l, SMT[x].r = r;
		if(l == r)
		{
			val[x] = a[l] >= k;
			return ;
		}
		int mid = (l + r) >> 1;
		build(x << 1, l, mid, k);
		build(x << 1 | 1, mid + 1, r, k);
		pushup(x);
	}
	void change(int p, int l, int r, int x, int y, int vall)
	{
		if (x <= l && r <= y)
		{
			val[p] = vall * (r - l + 1);
			lazy[p] = vall;
			return ;
		}
		if (l > y || r < x) return ;
		pushdown(p);
		int mid = (l + r) >> 1;
		change(p << 1, l, mid, x, y, vall);
		change(p << 1 | 1, mid + 1, r, x, y, vall);
		pushup(p);
	}
	int query(int p , int l, int r, int x, int y)
	{
		if (x <= l && r <= y)
		{
			return val[p];
		}
		if (l > y || r < x) return 0;
		pushdown(p);
		int mid = (l + r) >> 1;
		return query(p << 1, l, mid, x, y) + query(p << 1 | 1, mid + 1, r, x, y);
	}
}smt;

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", &input[i][0], &input[i][1], &input[i][2]);
	scanf ("%d", &q);
	int l = 1, r = n, ans, mid;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		smt.prework();
		smt.build(1, 1, n, mid);
		for (int i = 1; i <= m; i++)
		{
			int cntOne = smt.query(1, 1, n, input[i][1], input[i][2]);
			if (input[i][0])
			{
				smt.change(1, 1, n, input[i][1], input[i][1] + cntOne - 1, 1);
				smt.change(1, 1, n, input[i][1] + cntOne, input[i][2], 0);
			}else
			{
				smt.change(1, 1, n, input[i][2] - cntOne + 1, input[i][2], 1);
				smt.change(1, 1, n, input[i][1], input[i][2] - cntOne, 0);
			}
		}
		int k = smt.query(1, 1, n, q, q);
		if(k) ans = mid, l = mid + 1;else r = mid - 1;
	}
	printf("%d
", ans);
	return 0;
}