題目傳送門
前言
線段樹好題！！！！
咕咕了挺久的一道題目，很早之前就想寫了，今天終于找了個時間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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549581.html
標籤：其他