现在是用什么软件做网站,百度免费推广登录入口,医疗企业网站模板,紫搜科技建站题目链接 题面 题目描述 在2016年#xff0c;佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题#xff0c;现在他在研究一个难题#xff0c;需要你来帮助他。这个难题是这样子的#xff1a;给出一个1到n的全排列#xff0c;现在对这个全排列序列进行…题目链接 题面 题目描述 在2016年佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题现在他在研究一个难题需要你来帮助他。这个难题是这样子的给出一个1到n的全排列现在对这个全排列序列进行m次局部排序排序分为两种 1:(0,l,r)表示将区间[l,r]的数字升序排序 2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。 输入输出格式 输入格式 输入数据的第一行为两个整数n和m。n表示序列的长度m表示局部排序的次数。 1 n, m 10^5第二行为n个整数表示1到n的一个全排列。接下来输入m行每一行有三个整数op, l, r, op为0代表升序排序op为1代表降序排序, l, r 表示排序的区间。 最后输入一个整数qq表示排序完之后询问的位置, 1 q n。1 n 10^51 m 10^5 输出格式 输出数据仅有一行一个整数表示按照顺序将全部的部分排序结束后第q位置上的数字。 题解 这道题好有趣 正解居然是二分答案 因为最后要询问的只有一个位置所以直接二分这个位置上的数。 然后修改一下原数组——原数组中比二分的答案大的数都改为1, 小于等于的都改为0。 然后用线段树模拟整个排序过程。把一个01序列的区间排序是很简单的——数出区间内有多少个1, 然后如果是顺序排序把右面对应的几个改成1, 剩下的改成0。 模拟执行一遍之后就可以知道实际上排完序后询问位置上的数应该比你二分的答案大还是小了继续二分即可。 #include cstdio
#include cstring
#include cmath
#include algorithm
#include iostream
#include vector
#define space putchar( )
#define enter putchar(\n)
typedef long long ll;
using namespace std;
template class T
void read(T x){char c;bool op 0;while(c getchar(), c 0 || c 9)if(c -) op 1;x c - 0;while(c getchar(), c 0 c 9)x x * 10 c - 0;if(op) x -x;
}
template class T
void write(T x){if(x 0) putchar(-), x -x;if(x 10) write(x / 10);putchar(0 x % 10);
}const int N 100005;
int n, m, a[N], val[N], pos, op[N], ql[N], qr[N];
int data[4*N];
bool lazy[4*N], tag[4*N];void build(int k, int l, int r){tag[k] 0;if(l r) return (void)(data[k] val[l]);int mid (l r) 1;build(k 1, l, mid);build(k 1 | 1, mid 1, r);data[k] data[k 1] data[k 1 | 1];
}
void pushdown(int k, int l, int r){if(!tag[k]) return;int mid (l r) 1;data[k 1] lazy[k] * (mid - l 1);data[k 1 | 1] lazy[k] * (r - mid);lazy[k 1] lazy[k 1 | 1] lazy[k];tag[k 1] tag[k 1 | 1] 1;tag[k] 0;
}
void change(int k, int l, int r, int ql, int qr, int x){if(ql l qr r) return (void)(data[k] x * (r - l 1), lazy[k] x, tag[k] 1);pushdown(k, l, r);int mid (l r) 1;if(ql mid) change(k 1, l, mid, ql, qr, x);if(qr mid) change(k 1 | 1, mid 1, r, ql, qr, x);data[k] data[k 1] data[k 1 | 1];
}
int query(int k, int l, int r, int ql, int qr){if(ql l qr r) return data[k];pushdown(k, l, r);int mid (l r) 1, ret 0;if(ql mid) ret query(k 1, l, mid, ql, qr);if(qr mid) ret query(k 1 | 1, mid 1, r, ql, qr);return ret;
}int main(){read(n), read(m);for(int i 1; i n; i) read(a[i]);for(int i 1; i m; i)read(op[i]), read(ql[i]), read(qr[i]);read(pos);int l 1, r n, mid;while(l r){mid (l r) 1;for(int i 1; i n; i)val[i] a[i] mid;build(1, 1, n);for(int i 1; i m; i){int cnt query(1, 1, n, ql[i], qr[i]);if(op[i]){if(cnt) change(1, 1, n, ql[i], ql[i] cnt - 1, 1);if(ql[i] cnt qr[i]) change(1, 1, n, ql[i] cnt, qr[i], 0);}else{if(cnt) change(1, 1, n, qr[i] - cnt 1, qr[i], 1);if(qr[i] - cnt ql[i]) change(1, 1, n, ql[i], qr[i] - cnt, 0);}}if(query(1, 1, n, pos, pos)) l mid 1;else r mid;}write(l), enter;return 0;
} 转载于:https://www.cnblogs.com/RabbitHu/p/BZOJ4552.html
