一个只追踪特定数字 $m$ 位置的问题。

我们将排列转化为 $01$ 序列（$1$ 表示 $p_i < m$，$0$ 表示 $p_i >= m$），

通过维护 $01$ 序列来快速统计区间内小于 $m$ 的元素个数，并模拟操作对 $m$ 位置的影响。

由于操作会将区间内的元素按“最小值、最大值、次小值、次大值……”交替放置。

这等价于：与区间左端点 $l$ 同奇偶的位置（即 $l, l+2, l+4, ...$）放置最小的若干个数（升序），另一列（$l+1, l+3, ...$）放置剩余较大的数（降序）。

因此可以分别维护奇数位置和偶数位置上的 $01$ 序列，用两颗线段树支持区间赋值和区间求和。

详见注释：

#include<bits/stdc++.h>
using namespace std;

#define lc(p) (p << 1)
#define rc(p) ((p << 1) | 1)
const int N = 1e5 + 10;
int a[N];

struct node {
	int l, r, sum, tag;
} tro[N << 2], tre[N << 2];

void pushup(int p, node* tr) {
	tr[p].sum = tr[lc(p)].sum + tr[rc(p)].sum;
}

void pushdown(int p, node* tr) {
	if (tr[p].tag != -1) {
		int pt = tr[p].tag;
		
		tr[lc(p)].tag = pt;
		tr[lc(p)].sum = (tr[lc(p)].r - tr[lc(p)].l + 1) * pt;
		tr[rc(p)].tag = pt;
		tr[rc(p)].sum = (tr[rc(p)].r - tr[rc(p)].l + 1) * pt;
		
		tr[p].tag = -1;
	}
}

void build(int p, int l, int r, int v[], node* tr) {
	tr[p] = {l, r, 0, -1};
	if (l == r) {
		tr[p].sum = v[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(lc(p), l, mid, v, tr);
	build(rc(p), mid + 1, r, v, tr);
	pushup(p, tr);
}

void change(int p, int l, int r, int v, node* tr) {
	if (r < tr[p].l || tr[p].r < l) {
		return ;
	}
	if (l <= tr[p].l && tr[p].r <= r) {
		tr[p].tag = v;
		tr[p].sum = (tr[p].r - tr[p].l + 1) * v;
		return ;
	}
	pushdown(p, tr);
	change(lc(p), l, r, v, tr);
	change(rc(p), l, r, v, tr);
	pushup(p, tr);
}

int query(int p, int l, int r, node* tr) {
	if (r < tr[p].l || tr[p].r < l) {
		return 0;
	}
	if (l <= tr[p].l && tr[p].r <= r) {
		return tr[p].sum;
	}
	pushdown(p, tr);
	return query(lc(p), l, r, tr) + query(rc(p), l, r, tr);
}

int get_o(int x) {   // 获取实际下标 x 的奇数线段树下标  
	return ((x + 1) >> 1);
}

int get_e(int x) {   // 获取实际下标 x 的偶数线段树下标  
	return (x >> 1);
}

// 将实际下标区间 [l, r]，转换成 v 对应线段树的下标 
bool rng(int l, int r, int v, int &ql, int &qr) {
	int x = l, y = r;
	if ((x & 1) != v) {   // != 优先级很高，所以要加括号 
		x ++;
	}
	if ((y & 1) != v) {
		y --;
	}
	if (x > y) {
		return 0;
	}
	if (v & 1) {
		ql = get_o(x);
		qr = get_o(y);
	}
	else {
		ql = get_e(x);
		qr = get_e(y);
	}
	return 1;
}

int bo[N], be[N];

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, q, m;
	cin >> n >> q >> m;
	
	int pos = 0;  // 值 m 所属下标（位置） 
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		if (a[i] == m) {
			pos = i;
		}
	}
	
	memset(bo, 0, sizeof(bo));
	memset(be, 0, sizeof(be));
	int no = (n + 1) >> 1, ne = n >> 1; 
	for (int i = 1; i <= n; i ++) {
		int v = (a[i] < m);   // 比 m 小为 1 
		if (i & 1) {
			bo[get_o(i)] = v;
		}
		else {
			be[get_e(i)] = v;
		}
	}
	
	if (no) {
		build(1, 1, no, bo, tro);   // 赋值 
	}
	if (ne) {
		build(1, 1, ne, be, tre);
	}
	
	for (int i = 1; i <= q; i ++) {
		int l, r;
		cin >> l >> r;
		
		int co = 0, ce = 0, ql, qr;
		// co 和 ce 需要初始化为 0，不然未执行 if 值就会变得奇怪 
		if (no && rng(l, r, 1, ql, qr)) {
			co = query(1, ql, qr, tro);   
			// 如果区间 [l, r] 在奇数线段树有区间
			// 计算 co 为奇数线段树里比 m 小的值的数量 
		}
		if (ne && rng(l, r, 0, ql, qr)) {
			ce = query(1, ql, qr, tre);
			// 如果区间 [l, r] 在偶数线段树有区间
			// 计算 ce 为偶数线段树里比 m 小的值的数量
		}
		int cnt = co + ce;   // cnt 为整个区间 [l, r] 里比 m 小的值的数量 
		
		int len = r - l + 1;
		int half = (len + 1) >> 1;
		
		if (l <= pos && pos <= r) {   // m 的位置在区间 [l, r] 里 
			if (cnt + 1 <= half) {  // 如果 m 的位置在前半段 
				pos = l + 2 * cnt;   // 因为大小穿插，m 应该在这里 
			}
			else {
				pos = l + 2 * (len - cnt - 1) + 1;
				// 最大（第一大）放 l + 1
				// 次大（第二大）放 l + 3
				// m 是第 cnt + 1 小，第 len - (cnt + 1) + 1 大 
			}
		}
		
		int p0 = l & 1;
		int l0, r0;  // 和 l 同奇偶的线段树区间 
		int l1, r1;  // 和 l 不同奇偶的线段树区间 
		bool ok0 = rng(l, r, p0, l0, r0);
		bool ok1 = rng(l, r, p0 ^ 1, l1, r1);
		int x = min(half, cnt);     // 在前半部分比 m 小的值的数量 
		int y = max(cnt - half, 0);  // 在后半部分比 m 小的值的数量 
		
		// 重新排序后，修改区间内数的顺序，即重新覆盖 0 和 1 
		if (ok0) {   // 和 l 同奇偶的线段树有区间 
			if (l0 <= l0 + x - 1) {
				if (p0) change(1, l0, l0 + x - 1, 1, tro);
				else change(1, l0, l0 + x - 1, 1, tre);
			}
			if (l0 + x <= r0) {
				if (p0) change(1, l0 + x, r0, 0, tro);
				else change(1, l0 + x, r0, 0, tre);
			}
		}
		if (ok1) {   // 和 l 不同奇偶的线段树有区间 
			if (l1 <= r1 - y) {
				if (p0 ^ 1) change(1, l1, r1 - y, 0, tro);
				else change(1, l1, r1 - y, 0, tre);
			}
			if (r1 - y + 1 <= r1) {
				if (p0 ^ 1) change(1, r1 - y + 1, r1, 1, tro);
				else change(1, r1 - y + 1, r1, 1, tre);
			}
		}
	}
	
	cout << pos << "\n";
	
	return 0; 
}

前言

简单题。

这题和 P2824 [HEOI2016/TJOI2016] 排序 非常相似，建议先做一下这题。

Sol

接下来我们来说本题的做法：

我们只追踪数字 $m$ 的位置，不用还原整个排列。把序列转成 01 序列（参考 P2824 第一篇题解），$b_i=1\iff p_i<m$，那么任意区间里 $cnt=\sum b_i$ 就是“小于 $m$”的个数，从而 $m$ 在该区间的排名就是 $t=cnt+1$。

一次操作 $[l,r]$ 的效果可以直接刻画：令 $k=r-l+1,\ h=\lceil k/2\rceil$。与 $l$ 同奇偶的位置（$l,l+2,\dots$）会放最小的 $h$ 个数，所以这列里 1 的个数是 $x=\min(cnt,h)$，表现为“前 $x$ 个置 1，其余置 0”；另一列（$l+1,l+3,\dots$）放剩下的大数（从大到小），其中 1 的个数是 $y=\max(cnt-h,0)$，表现为“后 $y$ 个置 1，其余置 0”。同时若原来的 $pos\in[l,r]$，则 $t\le h\Rightarrow pos=l+2(t-1)$，否则 $pos=l+2(k-t)+1$。

为了高效维护 $cnt$ 和上述整段赋值，我们把奇偶下标拆成两棵线段树，具体细节见代码，复杂度 $O((n+q)\log n)$。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;

int a[N];

struct SegTree {
    int c[N * 4], add[N * 4];
    #define lc(u) (u << 1)
    #define rc(u) ((u << 1) | 1)
    void build(int u, int l, int r, vector<int> &tmp) {
        add[u] = -1; 
        if (l == r) {
            c[u] = tmp[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(u), l, mid, tmp);
        build(rc(u), mid + 1, r, tmp);
        c[u] = c[lc(u)] + c[rc(u)];
    }
    void pushtag(int u, int l, int r, int k) {
        c[u] = (r - l + 1) * k;
        add[u] = k; 
    }
    void pushdown(int u, int l, int r) {
        if (add[u] == -1) return;
        int mid = (l + r) >> 1;
        pushtag(lc(u), l, mid, add[u]);
        pushtag(rc(u), mid + 1, r, add[u]);
        add[u] = -1;
    }
    void modify(int u, int l, int r, int nowl, int nowr, int k) {
        if (l > nowr || r < nowl) return; 
        if (l <= nowl && nowr <= r) {
            pushtag(u, nowl, nowr, k);
            return;
        }
        pushdown(u, nowl, nowr);
        int mid = (nowl + nowr) >> 1;
        if (l <= mid) modify(lc(u), l, r, nowl, mid, k);
        if (r > mid)  modify(rc(u), l, r, mid + 1, nowr, k);
        c[u] = c[lc(u)] + c[rc(u)];
    }
    int query(int u, int nl, int nr, int l, int r) {
        if (l > nr || r < nl) return 0;
        if (l <= nl && nr <= r) {
            return c[u];
        }
        pushdown(u, nl, nr);
        int mid = (nl + nr) >> 1, ans = 0;
        if (l <= mid) {
            ans += query(lc(u), nl, mid, l, r);
        }
        if (r > mid) {
            ans += query(rc(u), mid + 1, nr, l, r);
        }
        return ans;
    }
} so, se;

int idd(int i) { return (i + 1) >> 1; }
int ide(int i) { return i >> 1; }

using nd = tuple<int, int, int>;
int n, q, tg;
vector<nd> Q;

bool rng(int l, int r, int p, int &ql, int &qr) {
    int a = l;
    if ((a & 1) != p) ++a;
    int b = r;
    if ((b & 1) != p) --b;
    if (a > b) return false;
    if (p) {
        ql = idd(a);
        qr = idd(b);
    } else {
        ql = ide(a);
        qr = ide(b);
    }
    return true;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int m;
    cin >> n >> q >> m;
    int pos = -1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] == m) pos = i;
    }
    // using nd = pair<int, int>;
    int no = (n + 1) >> 1;
    int ne = n >> 1;
    vector<int> bo(no + 1), be(ne + 1);
    for (int i = 1; i <= n; ++i) {
        int v = (a[i] < m);
        if (i & 1) bo[idd(i)] = v;
        else be[ide(i)] = v;
    }
    if (no) so.build(1, 1, no, bo);
    if (ne) se.build(1, 1, ne, be);
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        int k = r - l + 1;
        int h = (k + 1) >> 1;
        int ql, qr;
        int co = 0, ce = 0;
        if (no && rng(l, r, 1, ql, qr)) co = so.query(1, 1, no, ql, qr);
        if (ne && rng(l, r, 0, ql, qr)) ce = se.query(1, 1, ne, ql, qr);
        int cnt = co + ce;
        if (l <= pos && pos <= r) {
            int t = cnt + 1;
            if (t <= h) pos = l + 2 * (t - 1);
            else pos = l + 2 * (k - t) + 1;
        }
        int p0 = l & 1;
        int l0, r0, l1, r1;
        bool ok0 = rng(l, r, p0, l0, r0);
        bool ok1 = rng(l, r, p0 ^ 1, l1, r1);
        int x = cnt;
        if (x > h) x = h;
        int y = cnt - h;
        if (y < 0) y = 0;
        if (ok0) {
            if (l0 <= l0 + x - 1) {
                if (p0) so.modify(1, l0, l0 + x - 1, 1, no, 1);
                else    se.modify(1, l0, l0 + x - 1, 1, ne, 1);
            }
            if (l0 + x <= r0) {
                if (p0) so.modify(1, l0 + x, r0, 1, no, 0);
                else    se.modify(1, l0 + x, r0, 1, ne, 0);
            }
        }
        if (ok1) {
            int len = r1 - l1 + 1;
            if (y > len) y = len;
            if (l1 <= r1 - y) {
                if (p0 ^ 1) so.modify(1, l1, r1 - y, 1, no, 0);
                else se.modify(1, l1, r1 - y, 1, ne, 0);
            }
            if (r1 - y + 1 <= r1) {
                if (p0 ^ 1) so.modify(1, r1 - y + 1, r1, 1, no, 1);
                else se.modify(1, r1 - y + 1, r1, 1, ne, 1);
            }
        }
    }
    cout << pos << "\n";
}