题解
看错题了, 我以为是询问 Q 是个数字, 问它在哪个位置
我一想这不直接 01 序列搞一下就好了嘛 (事实上是 012)
然后呢, 我发现样例没过.
啊我看错题了, 问的是 Q 这个位置是啥......
哦, 套用我之前的想法不是直接拿线段树维护 01 序列然后二分吗......(可以不用 012, 直接是 0 表示小于等于 mid 的值, 1 表示大于 mid 的值)
哎我要是没看错题这题我是不是做不出来啊
代码
- #include <bits/stdc++.h>
- #define enter putchar('\n')
- #define space putchar(' ')
- #define pii pair<int,int>
- #define fi first
- #define se second
- #define MAXN 100005
- #define pb push_back
- #define mp make_pair
- #define eps 1e-8
- //#define ivorysi
- using namespace std;
- typedef long long int64;
- typedef double db;
- template<class T>
- void read(T &res) {
- res = 0;T f = 1;char c = getchar();
- while(c <'0' || c> '9') {
- if(c == '-') f = -1;
- c = getchar();
- }
- while(c>= '0' && c <= '9') {
- res = res * 10 + c - '0';
- c = getchar();
- }
- }
- template<class T>
- void out(T x) {
- if(x <0) {x = -x;putchar('-');}
- if(x>= 10) out(x / 10);
- putchar('0' + x % 10);
- }
- struct node {
- int cnt[2],l,r,cov;
- }tr[MAXN * 4];
- int a[MAXN],N,M;
- int op[MAXN],L[MAXN],R[MAXN],num,Q;
- void cover(int u,int v) {
- tr[u].cov = v;
- memset(tr[u].cnt,0,sizeof(tr[u].cnt));
- tr[u].cnt[v] = tr[u].r - tr[u].l + 1;
- }
- void push_down(int u) {
- if(tr[u].cov != -1) {
- cover(u <<1,tr[u].cov);
- cover(u << 1 | 1,tr[u].cov);
- tr[u].cov = -1;
- }
- }
- void update(int u) {
- for(int i = 0 ; i <= 1 ; ++i) {
- tr[u].cnt[i] = tr[u << 1].cnt[i] + tr[u << 1 | 1].cnt[i];
- }
- }
- void build(int u,int l,int r) {
- tr[u].l = l;tr[u].r = r;
- tr[u].cov = -1;
- if(l == r) {
- cover(u,a[l]> num);
- return;
- }
- int mid = (l + r)>> 1;
- build(u <<1,l,mid);
- build(u << 1 | 1,mid + 1,r);
- update(u);
- }
- int C[2];
- void Query(int u,int l,int r) {
- if(tr[u].l == l && tr[u].r == r) {
- for(int i = 0 ; i <= 1 ; ++i) C[i] += tr[u].cnt[i];
- return;
- }
- push_down(u);
- int mid = (tr[u].l + tr[u].r)>> 1;
- if(r <= mid) Query(u <<1,l,r);
- else if(l> mid) Query(u <<1 | 1,l,r);
- else {Query(u << 1,l,mid);Query(u << 1 | 1,mid + 1,r);}
- }
- void Cover(int u,int l,int r,int v) {
- if(r < l) return;
- if(tr[u].l == l && tr[u].r == r) {
- cover(u,v);
- return;
- }
- push_down(u);
- int mid = (tr[u].l + tr[u].r)>> 1;
- if(r <= mid) Cover(u <<1,l,r,v);
- else if(l> mid) Cover(u <<1 | 1,l,r,v);
- else {Cover(u << 1,l,mid,v);Cover(u << 1 | 1,mid + 1,r,v);}
- update(u);
- }
- bool check(int mid) {
- num = mid;build(1,1,N);
- for(int i = 1 ; i <= M ; ++i) {
- C[0] = C[1] = 0;
- Query(1,L[i],R[i]);
- int l = L[i];
- if(!op[i]) {
- for(int j = 0 ; j <= 1 ; ++j) {
- Cover(1,l,l + C[j] - 1,j);
- l += C[j];
- }
- }
- else {
- for(int j = 1 ; j>= 0 ; --j) {
- Cover(1,l,l + C[j] - 1,j);
- l += C[j];
- }
- }
- }
- C[0] = C[1] = 0;
- Query(1,Q,Q);
- return C[0];
- }
- void Solve() {
- 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(L[i]);read(R[i]);
- }
- read(Q);
- int L = 1,R = N;
- while(L <R) {
- int mid = (L + R)>> 1;
- if(check(mid)) R = mid;
- else L = mid + 1;
- }
- out(L);enter;
- }
- int main() {
- #ifdef ivorysi
- freopen("f1.in","r",stdin);
- #endif
- Solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2733840.html