题目链接： bzoj点我:-) 洛谷点我:-) 题目描述： 在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种： 1:(0,l,r)表示将区间[l,r]的数字升序排序 2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。
输入格式： 输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 105 第二行为n个整数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 105 ，1 <= m <= 105
输出格式： 输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。
思路： 二分答案x， 每次将原序列小于等于x的数换成0，大于x的数换成1， 用线段树的求和与区间修改维护一遍操作， 如果操作完毕后位置q的数字为0，则答案小于等于x, 否则大于x
感想： 这题二分答案比较巧妙， 可以发现对于原序列做一些换数操作是有用的， ———————————来自YALI省选集训某dalao的试题讨论
代码很好打，难度也不大，主要是思路很巧妙
代码：
//miaomiao 3.10 #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; #define For(i, a, b) for(int i = (a); i <= (int)(b); ++i) #define N (100000+5) struct OP{ int op, l, r; }rop[N]; int n, m, r[N], tr[N]; #define lc (o<<1) #define rc (o<<1|1) #define mid ((L+R)>>1) int ql, qr; struct Seg_tree{ int sum[N<<2], set[N<<2]; bool tag[N<<2]; void maintain(int o, int L, int R){ if(tag[o]){ sum[o] = (R-L+1)*set[o]; return; } sum[o] = sum[lc]+sum[rc]; } void push_down(int o, int L, int R){ if(!tag[o]) return; tag[o] = 0; tag[lc] = 1; tag[rc] = 1; set[lc] = set[rc] = set[o]; maintain(lc, L, mid); maintain(rc, mid+1, R); } void build(int o, int L, int R){ if(L == R){ sum[o] = tr[L]; tag[o] = false; return; } tag[o] = false; build(lc, L, mid); build(rc, mid+1, R); maintain(o, L, R); } void Modify(int o, int L, int R, int nset){ if(ql <= L && qr >= R){ tag[o] = true; set[o] = nset; maintain(o, L, R); return; } push_down(o, L, R); if(ql <= mid) Modify(lc, L, mid, nset); if(qr > mid) Modify(rc, mid+1, R, nset); maintain(o, L, R); } int query(int o, int L, int R){ if(ql <= L && qr >= R) return sum[o]; int ret = 0; push_down(o, L, R); if(ql <= mid) ret += query(lc, L, mid); if(qr > mid) ret += query(rc, mid+1, R); return ret; } }ST; #undef lc #undef rc #undef mid int Q; bool check(int now){ For(i, 1, n) tr[i] = r[i]>now; ST.build(1, 1, n); int op, Sum1, Sum0, L, R; For(i, 1, m){ op = rop[i].op; L = ql = rop[i].l; R = qr = rop[i].r; Sum1 = ST.query(1, 1, n); Sum0 = R-L+1-Sum1; ql = L; qr = R-(op? Sum0: Sum1); if(ql <= qr) ST.Modify(1, 1, n, op); ql = qr+1; qr = R; if(ql <= qr) ST.Modify(1, 1, n, op^1); } ql = qr = Q; return ST.query(1, 1, n); } int main(){ #ifndef ONLINE_JUDGE freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif scanf("%d%d", &n, &m); For(i, 1, n) scanf("%d", &r[i]); For(i, 1, m) scanf("%d%d%d", &rop[i].op, &rop[i].l, &rop[i].r); int L = 1, R = n, mid; scanf("%d", &Q); while(L < R){ mid = (L+R)>>1; if(check(mid)) L = mid+1; else R = mid; } printf("%d\n", L); return 0; }