题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=4552
题意：给出一个$1$到$N$的全排列，对其进行$M$次排序，每次排序将区间$[l,r]$从小到大或从大到小排序，求排序完后位置$q$上的数字。$N,M \leq 10^5$，时限$6s$
名字挂羊头卖狗肉……
暴力排序$O(NMlogN)$神级常数才能过，故考虑在排序上降低复杂度
考虑二分答案，将小于等于当前答案的设为$0$，大于当前答案的设为$1$，这样修改就变成$0,1$排序，可以使用线段树区间覆盖实现
时间复杂度$O(Mlog^2N)$
#include<bits/stdc++.h> #define MAXN 100005 using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return a; } struct node{ int l , r , mark , num1; }Tree[MAXN << ]; ] , M , askNum , mid; inline void pushup(int dir){ Tree[dir].num1 = Tree[dir << ].num1 + Tree[dir << | ].num1; } inline void pushdown(int dir){ ) Tree[dir << ].mark = Tree[dir << | ].mark = Tree[dir << ].num1 = Tree[dir << | ].num1 = ; else ){ Tree[dir << ].mark = Tree[dir << | ].mark = ; Tree[dir << ].num1 = Tree[dir << ].r - Tree[dir << ].l + ; Tree[dir << | ].num1 = Tree[dir << | ].r - Tree[dir << | ].l + ; } Tree[dir].mark = -; } void init(int l , int r , int dir){ Tree[dir].l = l; Tree[dir].r = r; Tree[dir].mark = -; if(l == r) Tree[dir].num1 = num[l] > mid; else{ init(l , l + r >> , dir << ); init((l + r >> ) + , r , dir << | ); pushup(dir); } } void change(int l , int r , int dir , int mark){ if(Tree[dir].l >= l && Tree[dir].r <= r){ Tree[dir].mark = mark; Tree[dir].num1 = mark * (Tree[dir].r - Tree[dir].l + ); return; } pushdown(dir); ) change(l , r , dir << , mark); ) change(l , r , dir << | , mark); pushup(dir); } int ask(int l , int r , int dir){ if(Tree[dir].l >= l && Tree[dir].r <= r) return Tree[dir].num1; ; pushdown(dir); ) sum += ask(l , r , dir << ); ) sum += ask(l , r , dir << | ); return sum; } inline bool check(){ init( , N , ); ; i <= M ; i++){ ] , sortNum[i][] , ); ]){ change(sortNum[i][] , sortNum[i][] + t - , , ); ] + t <= sortNum[i][]) change(sortNum[i][] + t , sortNum[i][] , , ); } else{ change(sortNum[i][] - t + , sortNum[i][] , , ); ] - t >= sortNum[i][]) change(sortNum[i][] , sortNum[i][] - t , , ); } } ); } int main(){ N = read(); M = read(); ; i <= N ; i++) num[i] = read(); ; i <= M ; i++){ sortNum[i][] = read(); sortNum[i][] = read(); sortNum[i][] = read(); } askNum = read(); , r = N; while(l < r){ mid = l + r >> ; if(check()) r = mid; else l = mid + ; } cout << l; ; }
