Luogu P2824 [HEOI2016/TJOI2016]排序线段树+脑子

你的名字 2021-11-17 15:28 262阅读 0赞

只会两个$log$的$qwq$

--------------------

我们二分答案：设答案为$ans$，则我们把$a\[i\]<=ans$全部设成$0$，把$a\[i\]>ans$全部设成$1$，扔到线段树里，这样区间排序（升序）就是求出$\[l,r\]$中$0$（或$1$）的个数$cnt$，然后对区间$\[l,l+cnt-1\]$赋值为$0$,对$\[l+cnt,r\]$赋值为$1$。最后查一下所求位置是$0$还是$1$来决定上下界改变方向。

#include<cstdio>
    #include<iostream>
    #define R register int
    #define ls (tr<<1)
    #define rs (tr<<1|1)
    using namespace std;
    inline int g() {
        R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
        do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
    }
    const int N=100010;
    int tg[N<<2],d[N<<2],op[N],l[N],r[N];
    int a[N],n,m,k;
    inline void build(int tr,int l,int r,int vl) { tg[tr]=-1;
        if(l==r) {d[tr]=(int)a[l]>vl; return;} R md=l+r>>1;
        build(ls,l,md,vl),build(rs,md+1,r,vl); d[tr]=d[ls]+d[rs];
    }
    inline void spread(int tr,int l,int r) { if(!~tg[tr]) return ; R md=l+r>>1;
        tg[ls]=tg[rs]=tg[tr]; d[ls]=(md-l+1)*tg[tr],d[rs]=(r-md)*tg[tr]; tg[tr]=-1;
    }
    inline void change(int tr,int l,int r,int LL,int RR,int vl) {
        if(LL<=l&&r<=RR) {tg[tr]=vl,d[tr]=(r-l+1)*vl; return ;} spread(tr,l,r); R md=l+r>>1;
        if(LL<=md) change(ls,l,md,LL,RR,vl); if(RR>md) change(rs,md+1,r,LL,RR,vl); d[tr]=d[ls]+d[rs];
    }
    inline int query(int tr,int l,int r,int LL,int RR) {
        if(LL<=l&&r<=RR) return d[tr]; spread(tr,l,r); R md=l+r>>1,ret=0;
        if(LL<=md) ret+=query(ls,l,md,LL,RR); if(RR>md) ret+=query(rs,md+1,r,LL,RR); return ret;
    }
    inline int ck(int vl) {
        build(1,1,n,vl); for(R i=1;i<=m;++i) {
            R t=query(1,1,n,l[i],r[i]); if(!t||t==r[i]-l[i]+1) continue;
            if(!op[i]) change(1,1,n,l[i],r[i]-t,0),change(1,1,n,r[i]-t+1,r[i],1);
            else change(1,1,n,l[i],l[i]+t-1,1),change(1,1,n,l[i]+t,r[i],0);
        } return query(1,1,n,k,k);
    }
    signed main() {
    #ifdef JACK
        freopen("NOIPAK++.in","r",stdin);
    #endif
        n=g(),m=g(); for(R i=1;i<=n;++i) a[i]=g(); 
        for(R i=1;i<=m;++i) op[i]=g(),l[i]=g(),r[i]=g();
        k=g(); R LL=1,RR=n; while(LL<RR) { 
            R md=LL+RR>>1; if(ck(md)) LL=md+1; else RR=md;
        } printf("%d\n",LL); 
    }

--------------------

2019.07.03

转载于:https://www.cnblogs.com/Jackpei/p/11128420.html