前言
线段树好题！！！！
咕咕了挺久的一道题目，很早之前就想写了，今天终于找了个时间A掉了。
题意
给定一个 \(1\) 到 \(n\) 的排列，有 \(m\) 次操作，分两种类型。
1.0 l r表示将下标在 \([l, r]\) 区间中的数升序排序。
2.1 l r表示将下标在 \([l, r]\) 区间中的数降序排序。
给定一个数 \(q\) 询问最后 \(q\) 位置上的数。
\(Solution\)
看到数据范围，发现前 \(30\) 分是可以暴力的，这里不多赘述。
注意到 \(n,m\leqslant 10^5\) ,优先考虑 \(O(nlogn)\) 或 \(O(n \sqrt n)\) 做法。对一个序列进行操作，自然想到，线段树，但是线段树不支持区间排序那怎么办呢。
考虑对一段 \(01\) 串做排序，显然排完序后会变成 \(00011\) 或 \(11100\) 这种形式，可以用线段树的区间推平和求和操作来完成。
但是原序列不是 \(01\) 串，我们就要把它转换成 \(01\) 串。
可以选取一个基准数，让原序列大于等于这个数的都变成 \(1\) ，其他的都是 \(0\) 就能解决这个问题了。
如果操作完之后 \(q\) 上的是 \(1\) ，说明答案至少是大于等于这个基准数的，所以二分就行了。
总复杂度 \(O(n log^2n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m, pos;
int a[N];
struct question
{
int op, l, r;
} Q[N];
struct segment_tree
{
int l, r, val, tag;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define val(x) tr[x].val
#define tag(x) tr[x].tag
} tr[N << 2];
void pushup(int x)
{
val(x) = val(x << 1) + val(x << 1 | 1);
}
void pushdown(int x)
{
if(tag(x) == -1) return;
val(x << 1) = (r(x << 1) - l(x << 1) + 1) * tag(x);
tag(x << 1) = tag(x);
val(x << 1 | 1) = (r(x << 1 | 1) - l(x << 1 | 1) + 1) * tag(x);
tag(x << 1 | 1) = tag(x);
tag(x) = -1;
}
void build(int l, int r, int x, int v)
{
l(x) = l, r(x) = r, tag(x) = -1, val(x) = 0;
if(l == r)
{
val(x) = (a[l] >= v);
return;
}
int mid = l + r >> 1;
build(l, mid, x << 1, v), build(mid + 1, r, x << 1 | 1, v);
pushup(x);
}
void update(int l, int r, int x, int v)
{
if(l <= l(x) && r(x) <= r)
{
tag(x) = v;
val(x) = (r(x) - l(x) + 1) * v;
return;
}
pushdown(x);
int mid = l(x) + r(x) >> 1;
if(l <= mid) update(l, r, x << 1, v);
if(r > mid) update(l, r, x << 1 | 1, v);
pushup(x);
}
int query(int l, int r, int x)
{
if(l <= l(x) && r(x) <= r) return val(x);
pushdown(x);
int mid = l(x) + r(x) >> 1, res = 0;
if(l <= mid) res += query(l, r, x << 1);
if(r > mid) res += query(l, r, x << 1 | 1);
return res;
}
int check(int v)
{
build(1, n, 1, v);
for(int i = 1;i <= m;i ++)
{
int l = Q[i].l, r = Q[i].r, op = Q[i].op;
int sum = query(l, r, 1);
if(sum == 0) continue;
update(l, r, 1, 0);
if(op == 0) update(r - sum + 1, r, 1, 1);
else update(l, l + sum - 1, 1, 1);
}
return query(pos, pos, 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= m;i ++) cin >> Q[i].op >> Q[i].l >> Q[i].r;
cin >> pos;
int l = 1, r = n, res;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid)) l = mid + 1, res = mid;
else r = mid - 1;
}
cout << res << '\n';
return 0;
}