[TJOI 2016&HEOI 2016]排序

Description

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题

，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排

序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q

位置上的数字。

Input

输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整

数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序

排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5

，1 <= m <= 10^5

Output

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。

Sample Input

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

Sample Output

题解（转载）

->原文地址<-

首先常规套路，如果值域较小，那么枚举值域线段树区间覆盖
那么这题这么做这个转换呢？直接二分答案，把小于的部分赋为$0$，大于等于部分$1$，这样转换过来了，注意线段树只要存$1$就好,$0$直接可以相减得出

 //It is made by Awson on 2017.10.23

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <cmath>

 #include <stack>

 #include <queue>

 #include <vector>

 #include <string>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Lr(o) (o<<1)

 #define Rr(o) (o<<1|1)

 using namespace std;

 const int N = 1e5;

 int n, m, q, a[N+];

 struct operat {

   int opt, l, r;

 }p[N+];

 struct tt {

   int sgm[(N<<)+], lazy[(N<<)+];

   void build(int o, int l, int r, int key) {

     lazy[o] = ;

     if (l == r) {

       sgm[o] = (a[l]>=key); return;

     }

     int mid = (l+r)>>;

     build(Lr(o), l, mid, key); build(Rr(o), mid+, r, key);

     sgm[o] = sgm[Lr(o)]+sgm[Rr(o)];

   }

   void pushdown(int o, int l, int r, int mid) {

     if (lazy[o] == ) {

       lazy[Lr(o)] = lazy[Rr(o)] = ;

       sgm[Lr(o)] = mid-l+, sgm[Rr(o)] = r-mid;

       lazy[o] = ;

     }else if (lazy[o] == -) {

       lazy[Lr(o)] = lazy[Rr(o)] = -;

       sgm[Lr(o)] = , sgm[Rr(o)] = ;

       lazy[o] = ;

     }

   }

   void update(int o, int l, int r, int a, int b, int key) {

     if (a <= l && r <= b) {

       if (key) lazy[o] = , sgm[o] = r-l+;

       else lazy[o] = -, sgm[o] = ;

       return;

     }

     int mid = (l+r)>>;

     pushdown(o, l, r, mid);

     if (a <= mid) update(Lr(o), l, mid, a, b, key);

     if (mid < b) update(Rr(o), mid+, r, a, b, key);

     sgm[o] = sgm[Lr(o)]+sgm[Rr(o)];

   }

   int query(int o, int l, int r, int a, int b) {

     if (a <= l && r <= b) return sgm[o];

     int mid = (l+r)>>;

     pushdown(o, l, r, mid);

     int ca = , cb = ;

     if (a <= mid) ca = query(Lr(o), l, mid, a, b);

     if (mid < b) cb = query(Rr(o), mid+, r, a, b);

     return ca+cb;

   }

 }T;

 bool judge(int x) {

   T.build(, , n, x);

   int l, r, cnt0, cnt1;

   for (int i = ; i <= m; i++) {

     l = p[i].l, r = p[i].r;

     cnt1 = T.query(, , n, l, r); cnt0 = r-l+-cnt1;

     if (p[i].opt == ) {

       if (cnt0 != ) T.update(, , n, l, l+cnt0-, );

       if (cnt1 != ) T.update(, , n, l+cnt0, r, );

     }else {

       if (cnt1 != ) T.update(, , n, l, l+cnt1-, );

       if (cnt0 != ) T.update(, , n, l+cnt1, r, );

     }

   }

   return T.query(, , n, q, q) == ;

 }

 void work() {

   scanf("%d%d", &n, &m);

   for (int i = ; i <= n; i++) scanf("%d", &a[i]);

   for (int i = ; i <= m; i++) scanf("%d%d%d", &p[i].opt, &p[i].l, &p[i].r);

   scanf("%d", &q);

   int l = , r = n, ans;

   while (l <= r) {

     int mid = (l+r)>>;

     if (judge(mid)) l = mid+, ans = mid;

     else r = mid-;

   }

   printf("%d\n", ans);

 }

 int main() {

   work();

   return ;

 }

巴特西