fy0123
2017-12-10 15:29:22
大意：
给一个n的排列（n<=10^5），有m（m<=10^5）个操作：
1 l r 表示把[l, r]区间内的数降序排序；
0 l r 表示把[l, r]区间内的数升序排序。
最后询问这个序列的第p个位子上的数是多少。
做法：
由于将一个普通序列排序很慢，需要nlogn的时间，所以我们试着把它转化为对01序列排序。先来考虑一个简单的问题：
如何将一个01序列排序？（logn的复杂度）
对于这个问题，我们使用线段树来维护。查询一段区间内的1的个数记为cnt1，如果是升序，就将这段区间的[r-cnt1+1, r]都更改为1，将[l, r-cnt1]更改为0。降序则将[l, l+cnt1-1]更改为1，将[l+cnt, r]更改为0。这样我们就成功地把排序转化为了区间查询和区间修改。
接下来我们来说本题的做法：
这是一个离线的做法。首先二分答案mid。我们把原排列中大于等于mid的数都标记为1，小于mid的都标记为0。然后对于每个操作我们就将01序列排个序。最后如果第p个位子仍是1的话就是可行的。
这个二分成立因为是满足单调性的：可以简单地假设一下，如果你二分的答案是1，那么原序列所有的值都转化为了1，所以最后肯定是true。如果二分一个值成立当且仅当这个位子的值大于等于mid，故如果check返回true，则l = mid+1，否则r = mid-1。
（这题的思想可以借鉴，比较巧妙）
#include<cstdio>
#include<cstring>
#include<cctype>
#define lc o<<1
#define rc o<<1|1
#define mid (l+r)/2
using namespace std;
const int N = 100010;
int n, m, p;
int T[4*N], lazy[4*N];//segment tree
int a[N], ch[N], L[N], R[N];//the information by reading
inline int read()
{
char ch = getchar(); int x = 0;
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)){ x = x*10+ch-'0'; ch = getchar(); }
return x;
}
inline void build(int o, int l, int r, int x)
{
if (l == r){
T[o] = a[l] >= x;
lazy[o] = 0;
return;
}
build(lc, l, mid, x); build(rc, mid+1, r, x);
T[o] = T[lc]+T[rc]; lazy[o] = 0;
}
inline void pushdown(int o, int l, int r)
{
if (!lazy[o]) return;
lazy[lc] = lazy[rc] = lazy[o];
if (lazy[o] == 1){
T[lc] = mid-l+1; T[rc] = r-mid;
} else T[lc] = T[rc] = 0;
lazy[o] = 0;
}
inline int query(int o, int l, int r, int x, int y)
{
if (x <= l && y >= r) return T[o];
if (x > r || y < l) return 0;
pushdown(o, l, r);
return query(lc, l, mid, x, y) + query(rc, mid+1, r, x, y);
}
inline int queryPoint(int o, int l, int r, int x)
{
if (l == x && r == x) return T[o];
pushdown(o, l, r);
if (x <= mid) return queryPoint(lc, l, mid, x);
else return queryPoint(rc, mid+1, r, x);
}
inline void update(int o, int l, int r, int x, int y, int val)
{
if (x <= l && y >= r){
T[o] = val*(r-l+1); lazy[o] = val ? 1 : -1;
return;
}
if (x > r || y < l) return;
pushdown(o, l, r);
update(lc, l, mid, x, y, val);
update(rc, mid+1, r, x, y, val);
T[o] = T[lc]+T[rc];
}
inline bool check(int x)
{
build(1, 1, n, x);
for (int i = 1; i <= m; i ++){
int cnt1 = query(1, 1, n, L[i], R[i]);
if (ch[i] == 0){
update(1, 1, n, R[i]-cnt1+1, R[i], 1);
update(1, 1, n, L[i], R[i]-cnt1, 0);
}
else{
update(1, 1, n, L[i], L[i]+cnt1-1, 1);
update(1, 1, n, L[i]+cnt1, R[i], 0);
}
}
return queryPoint(1, 1, n, p);
}
int main()
{
n = read(); m = read();
for (int i = 1; i <= n; i ++) a[i] = read();
for (int i = 1; i <= m; i ++){
ch[i] = read(); L[i] = read(); R[i] = read();
}
p = read();
int ll = 1, rr = n, midd, ans;
while (ll <= rr){
midd = (ll+rr) >> 1;
if (check(midd)) ans = midd, ll = midd+1; else rr = midd-1;
}
printf("%d\n", ans);
return 0;
}