【HDU5649 BestCoder Round 76 (div1)D】【二分+线段树】DZY Loves Sorting 全排列1~n 区间升序降序排序 最后k位置的数是几

本文主要是介绍【HDU5649 BestCoder Round 76 (div1)D】【二分+线段树】DZY Loves Sorting 全排列1~n 区间升序降序排序 最后k位置的数是几，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DZY有一个数列$a[1..n]$，它是$1\sim n$这$n$个正整数的一个排列。现在他想支持两种操作：$0lr$: 将$a[l..r]$原地升序排序。$1lr$: 将$a[l..r]$原地降序排序。操作完后，他会给你指定一个位置$k$，请你告诉他$a[k]$的值。

第一行$t$，表示有$t$组数据。接下来$t$组数据。 每组数据中：第一行有两个整数$n,m$，其中$m$表示操作数目。第二行是空格隔开的$n$个正整数$a[1],a[2],\cdots ,a[n]$，表示数组的初始值，保证它是$1\sim n$的一个排列。接下来$m$行，每行有三个整数$opt,l,r$，表示一次操作。最后一行为整数$k$。(1\le t \le 50,1\le n,m \le 100000,1\le k \le n, 1\le l\le r\le n, opt \in \{0,1\}1≤t≤50,1≤n,m≤100000,1≤k≤n,1≤l≤r≤n,opt∈{0,1},所有数据的$n$之和不超过$150000$,所有数据的$m$之和不超过$150000$)

每组数据输出一行答案，表示操作完后$a[k]$的值。

1
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

5

1 6 2 5 3 4 -> [1 2 5 6] 3 4 -> 1 2 [6 5 4 3] -> 1 [2 5 6] 4 3，最终$a[3]=5$。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 2e5+10, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, m, k;
int a[N];
int op[N], l[N], r[N];
int M, L, R, V;
int sum[1 << 19];
int len[1 << 19];
int flag[1 << 19];
void pushup(int o)
{sum[o] = sum[ls] + sum[rs];
}
void pushdown(int o)
{if (~flag[o]){sum[ls] = len[ls] * flag[o];sum[rs] = len[rs] * flag[o];flag[ls] = flag[o];flag[rs] = flag[o];flag[o] = -1;}
}
void build(int o, int l, int r)
{len[o] = r - l + 1;flag[o] = -1;if (l == r){sum[o] = (a[l] > M);return;}int mid = (l + r) >> 1;build(lson);build(rson);pushup(o);
}
int check(int o, int l, int r)
{if (L <= l&&R >= r)return sum[o];pushdown(o);int ret = 0;int mid = (l + r) >> 1;if (L <= mid)ret += check(lson);if (R > mid)ret += check(rson);return ret;
}
void change(int o, int l, int r)
{if (L <= l&&R >= r){sum[o] = len[o] * V;flag[o] = V;return;}pushdown(o);int mid = (l + r) >> 1;if (L <= mid)change(lson);if (R > mid)change(rson);pushup(o);
}
int num[2];
int main()
{scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){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", &op[i], &l[i], &r[i]);scanf("%d", &k);int lft = 1;int rgt = n;while (lft < rgt){M = (lft + rgt) >> 1;build(1, 1, n);for (int i = 1; i <= m; ++i){L = l[i];R = r[i];num[1] = check(1, 1, n);num[0] = R - L + 1 - num[1];V = op[i];L = l[i];R = L + num[V] - 1;if (L <= R)change(1, 1, n);V = V ^ 1;L = R + 1;R = r[i];if (L <= R)change(1, 1, n);}L = k;R = k;int val = check(1, 1, n);val == 1 ? lft = M + 1 : rgt = M;}printf("%d\n", lft);}return 0;
}
/*
【trick&&吐槽】
不要忘记区间操作要保证L<=R哦【题意】
给你一个a[]，a[]是[1,n]的一个全排列。
我们有两种操作。
0 l r，把[l,r]排序升序
1 l r，把[l,r]排序降序
当做完全部的操作之后，我们告诉你一个位置k，让你求ans[k]，
即第k个位置的数的数值是多少。【类型】
线段树+二分【分析】
这道题一个很特殊的地方，就是我们的查询只有一个ans[k]
ans[k]对应着a[]呢？因为是全排列。于是，我们存在一种二分答案的可能解法。
我们可以二分ans[k]对应着数mid
这时，把<=mid的数标记为0，把>mid的数标记为1。
然后我们用线段树模拟全部的操作。这里只要实现——
1，查询区间中1的个数
2，区间赋值对于升序排序或者逆序排序，我们查询1的个数为num后。
升序就是把后num个数赋值为1，降序则把前num个数赋值为1。这样操作到最后，我们查询ans[k]。
如果对应的ans[k]为1，则说明当前的数是[mid,r]范围的数；
否则当前的数是(l,mid)范围的数。
于是到最后就可以得到答案【时间复杂度&&优化】
O(nlogn)
*/

这篇关于【HDU5649 BestCoder Round 76 (div1)D】【二分+线段树】DZY Loves Sorting 全排列1~n 区间升序降序排序 最后k位置的数是几的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！