排序
Time Limit: 60 Sec Memory Limit: 256 MB
[Submit][Status][Discuss]
Description
在2016年，佳媛姐姐喜欢上了数字序列。
因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。
这个难题是这样子的：
给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：
1: (0,l,r)表示将区间[l,r]的数字升序排序
2: (1,l,r)表示将区间[l,r]的数字降序排序
最后询问第q位置上的数字。
Input
输入数据的第一行为两个整数n和m。
n表示序列的长度，m表示局部排序的次数。
第二行为n个整数，表示1到n的一个全排列。
接下来输入m行，每一行有三个整数op, l, r,
op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。
最后输入一个整数q，q表示排序完之后询问的位置。
Output
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。
Sample Input
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5
HINT
1 <= n <= 10^5，1 <= m <= 10^5, 1 <= q <= n。
Solution
我们先考虑如果权值很小的话怎么做，显然可以对每个权值开一个线段树维护在哪些位置出现过。
那么排序显然就是覆盖连续的一段。只要知道某一区间有几个这个权值即可。
但是这样显然是过不了的，于是我们考虑二分答案，把val >= mid的设为1，其余的设为0。
这样就把权值变成了0/1，那么显然我们按照以上操作，如果Q位置上是1说明mid<=Ans，还可以更大一点，否则说明mid>Ans。
只要支持区间求和以及区间覆盖0/1即可。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long s64; const int ONE = ;
const int MOD = 1e9 + ; int get()
{
int res = , Q = ; char c;
while( (c = getchar()) < || c > )
if(c == '-') Q = -;
if(Q) res = c - ;
while( (c = getchar()) >= && c <= )
res = res * + c - ;
return res * Q;
} int n, m, Q;
int a[ONE];
int res, now; struct power
{
struct point
{
int val, tag;
}Node[ONE]; void Build(int i, int l, int r)
{
Node[i].tag = -;
if(l == r) return;
int mid = l + r >> ;
Build(i << , l, mid);
Build(i << | , mid + , r);
} int pushdown(int i, int l, int r)
{
int mid = l + r >> ;
if(Node[i].tag != -)
{
Node[i << ].tag = Node[i].tag;
Node[i << ].val = Node[i].tag * (mid - l + );
Node[i << | ].tag = Node[i].tag;
Node[i << | ].val = Node[i].tag * (r - (mid + ) + );
Node[i].tag = -;
}
} void Update(int i, int l, int r, int L, int R, int x)
{
if(L > R) return;
if(L <= l && r <= R)
{
Node[i].tag = x;
Node[i].val = x * (r - l + );
return;
}
pushdown(i, l, r);
int mid = l + r >> ;
if(L <= mid) Update(i << , l, mid, L, R, x);
if(mid + <= R) Update(i << | , mid + , r, L, R, x);
Node[i].val = Node[i << ].val + Node[i << | ].val;
} void Query(int i, int l, int r, int L, int R)
{
if(L > R) return;
if(L <= l && r <= R)
{
res += Node[i].val;
return;
}
pushdown(i, l, r);
int mid = l + r >> ;
if(L <= mid) Query(i << , l, mid, L, R);
if(mid + <= R) Query(i << | , mid + , r, L, R);
}
}C[]; struct operate
{
int l, r, x;
}oper[ONE]; void Modify(int id, int Left, int Right)
{
res = ;
C[id].Query(, , n, Left, Right);
C[id].Update(, , n, Left, Right, );
C[id].Update(, , n, now, now + res - , );
now += res;
} int Check(int mid)
{
for(int i = ; i <= ; i++)
C[i].Node[].tag = ; for(int i = ; i <= n; i++)
C[a[i] >= mid].Update(, , n, i, i, ); for(int i = ; i <= m; i++)
{
now = oper[i].l;
if(oper[i].x == ) for(int id = ; id <= ; id++) Modify(id, oper[i].l, oper[i].r);
if(oper[i].x == ) for(int id = ; id >= ; id--) Modify(id, oper[i].l, oper[i].r);
} res = , C[].Query(, , n, Q, Q);
return res;
} int main()
{
n = get(); m = get();
for(int i = ; i <= n; i++)
a[i] = get();
for(int i = ; i <= m; i++)
oper[i].x = get(), oper[i].l = get(), oper[i].r = get(); Q = get();
int l = , r = n;
while(l < r - )
{
int mid = l + r >> ;
if(Check(mid)) l = mid;
else r = mid;
} if(Check(r)) printf("%d", r);
else printf("%d", l);
}