Luogu

BZOJ

分析

二分答案+线段树。

二分答案 $mid$ ,然后将 $\geq mid$ 的数设为 $1$ ,$<mid$ 的数设为 $0$ 。

考虑如何对一个 $0/1$ 序列排序。显然可以用线段树结合区间求和、区间赋值做到 $O(\log n)$ 排序。

那么模拟所有 $m$ 个操作,如果最后位置 $q$ 上的数是 $1$ 就说明 $mid$ 可行。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;
struct node { int op,l,r; } o[N];
int a[N];

struct Segment_Tree {
    int sumv[N<<2],setv[N<<2];
    
#define ls (o<<1)
#define rs (o<<1|1)
    
    inline void pushup(int o) { sumv[o]=sumv[ls]+sumv[rs]; }
    inline void pushdown(int o,int l,int r) {
        if (setv[o]!=-1) {
            int mid=(l+r)>>1;
            setv[ls]=setv[rs]=setv[o];
            sumv[ls]=setv[o]*(mid-l+1),sumv[rs]=setv[o]*(r-mid);
            setv[o]=-1;
        }
    }
    
    inline void build(int o,int l,int r,int x) {
        if (l==r) { sumv[o]=(a[l]>=x),setv[o]=-1; return; }
        int mid=(l+r)>>1;
        build(ls,l,mid,x); build(rs,mid+1,r,x);
        pushup(o),setv[o]=-1;
    }
    inline void assign(int o,int l,int r,int ql,int qr,int v) {
        if (ql>r||qr<l) return; //!
        if (ql<=l&&r<=qr) { sumv[o]=v*(r-l+1),setv[o]=v; return; }
        int mid=(l+r)>>1; pushdown(o,l,r);
        if (ql<=mid) assign(ls,l,mid,ql,qr,v);
        if (qr>mid) assign(rs,mid+1,r,ql,qr,v);
        pushup(o);
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql>r||qr<l) return 0; //!
        if (ql<=l&&r<=qr) return sumv[o];
        int mid=(l+r)>>1,rt=0; pushdown(o,l,r);
        if (ql<=mid) rt+=query(ls,l,mid,ql,qr);
        if (qr>mid) rt+=query(rs,mid+1,r,ql,qr);
        pushup(o); return rt;
    }
    
#undef ls
#undef rs
    
} T;

inline int check(int mid,int k) {
    T.build(1,1,n,mid);
    for (re int i=1;i<=m;++i) {
        int l=o[i].l,r=o[i].r,s=T.query(1,1,n,l,r);
        if (o[i].op) T.assign(1,1,n,l+s,r,0),T.assign(1,1,n,l,l+s-1,1);
        else T.assign(1,1,n,l,r-s,0),T.assign(1,1,n,r-s+1,r,1);
    }
    return T.query(1,1,n,k,k);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=m;++i) o[i].op=read(),o[i].l=read(),o[i].r=read();
    int k=read(),L=1,R=n;
    while (L<R) {
        int mid=(L+R+1)>>1;
        if (check(mid,k)) L=mid;
        else R=mid-1;
    }
    printf("%d\n",L);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 39 PM