\(\mathcal{Description}\)

给定排列 \(\{p_n\}\) 和 \(m\) 次局部排序操作，求操作完成后第 \(q\) 位的值。

\(n,m\le10^5\)。

\(\mathcal{Solution}\)

跟这道的核心套路（？）差不多。

若序列是 \(01\) 序列，局部排序就相当于把 \(1\) 扔到一端，把 \(0\) 扔到另一端，只需要知道区间 \(1\) 的个数就好。

二分答案 \(mid\)，将排列中不小于 \(mid\) 的值设为 \(1\)，其余设为 \(0\)，暴力建新的线段树维护区间和，然后暴力处理每次排序操作，最后求到此时 \(q\) 位置的值（\(1\) 或 \(0\)）。注意到这个值的意义——\(q\) 位置的值大于等于 / 小于 \(mid\)，借此调整二分区间即可。

复杂度 \(\mathcal O(m\log^2n+n\log n)\)。

\(\mathcal{Code}\)

#include <cstdio>

const int MAXN = 1e5;

int n, m, a[MAXN + 5]; 

struct Event { int op, l, r; } evt[MAXN + 5];

inline int rint () {

	int x = 0; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}

struct SegmentTree {

	int one[MAXN << 2], tag[MAXN << 2];

	inline void pushup ( const int rt ) { one[rt] = one[rt << 1] + one[rt << 1 | 1]; }

	inline void pushdn ( const int rt, const int len ) {

		if ( ! ~ tag[rt] ) return ;

		one[rt << 1] = tag[rt] * ( len + 1 >> 1 );

		one[rt << 1 | 1] = tag[rt] * ( len >> 1 );

		tag[rt << 1] = tag[rt << 1 | 1] = tag[rt];

		tag[rt] = -1;

	}

	inline void build ( const int rt, const int l, const int r, const int thrval ) {

		tag[rt] = -1;

		if ( l == r ) return void ( one[rt] = a[l] >= thrval );

		int mid = l + r >> 1;

		build ( rt << 1, l, mid, thrval ), build ( rt << 1 | 1, mid + 1, r, thrval );

		pushup ( rt );

	}

	inline void assign ( const int rt, const int l, const int r, const int al, const int ar, const int v ) {

		if ( al > ar ) return ;

		if ( al <= l && r <= ar ) return void ( one[rt] = ( tag[rt] = v ) * ( r - l + 1 ) );

		int mid = l + r >> 1; pushdn ( rt, r - l + 1 );

		if ( al <= mid ) assign ( rt << 1, l, mid, al, ar, v );

		if ( mid < ar ) assign ( rt << 1 | 1, mid + 1, r, al, ar, v );

		pushup ( rt );

	}

	inline int query ( const int rt, const int l, const int r, const int ql, const int qr ) {

		if ( ql <= l && r <= qr ) return one[rt];

		int mid = l + r >> 1, ret = 0; pushdn ( rt, r - l + 1 );

		if ( ql <= mid ) ret += query ( rt << 1, l, mid, ql, qr );

		if ( mid < qr ) ret += query ( rt << 1 | 1, mid + 1, r, ql, qr );

		return ret;

	}

} st;

int main () {

	n = rint (), m = rint ();

	for ( int i = 1; i <= n; ++ i ) a[i] = rint ();

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

		evt[i].op = rint (), evt[i].l = rint (), evt[i].r = rint ();

	}

	int l = 1, r = n, q = rint ();

	while ( l < r ) {

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

		st.build ( 1, 1, n, mid );

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

			int el = evt[i].l, er = evt[i].r, t = st.query ( 1, 1, n, el, er );

			if ( ! evt[i].op ) {

				st.assign ( 1, 1, n, el, er - t, 0 );

				st.assign ( 1, 1, n, er - t + 1, er, 1 );

			} else {

				st.assign ( 1, 1, n, el, el + t - 1, 1 );

				st.assign ( 1, 1, n, el + t, er, 0 );

			}

		}

		if ( st.query ( 1, 1, n, q, q ) ) l = mid;

		else r = mid - 1;

	}

	printf ( "%d\n", l );

	return 0;

}

巴特西

Solution -「HEOI/TJOI 2016」「洛谷 P2824」排序

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章