bzoj 4552: [Tjoi2016&Heoi2016]排序

.

题意：一个长度为n的序列，每次将l到r按升序或降序排列，问最后q位置上的数是几。
题解：二分+线段树
二分答案，然后将原序列中大于md的设为1，小于等于的设为0，排序就是将这段区间的一半填0，一半填1。找到最小的使q位置最后为1的就是答案。
代码：

#include<bits/stdc++.h>
using namespace std;

struct tree
{
    int l,r,lc,rc,c,lz;
}tr[200010];
int n,num,q,m,a[100010],c[100010],d[100010];
struct query
{
    int op,l,r;
}b[100010];

void pushup(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc;
    tr[x].c=tr[lc].c+tr[rc].c;
}
void pushdown(int x)
{
    if(~tr[x].lz)
    {
        int lc=tr[x].lc,rc=tr[x].rc;
        if(tr[x].lz)
        {
            tr[lc].c=tr[lc].r-tr[lc].l+1;
            tr[rc].c=tr[rc].r-tr[rc].l+1;
        }
        else
        {
            tr[lc].c=tr[rc].c=0;
        }
        tr[lc].lz=tr[rc].lz=tr[x].lz;
        tr[x].lz=-1;
    }
}
int bt(int l,int r)
{
    int i=++num;
    tr[i].l=l;
    tr[i].r=r;
    tr[i].lc=tr[i].rc=0;
    tr[i].lz=-1;
    if(l<r)
    {
        int md=l+r>>1;
        tr[i].lc=bt(l,md);
        tr[i].rc=bt(md+1,r);
        pushup(i);
    }
    else
    tr[i].c=d[l];
    return i;
}
void chg(int i,int l,int r,int c)
{
    if(l>r)
    return;
    if(tr[i].l==l&&tr[i].r==r)
    {
        tr[i].lz=c;
        tr[i].c=(r-l+1)*c;
        return;
    }
    pushdown(i);
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(r<=md)
    chg(lc,l,r,c);
    else if(l>md)
    chg(rc,l,r,c);
    else
    {
        chg(lc,l,md,c);
        chg(rc,md+1,r,c);
    }
    pushup(i);
}
int get(int i,int l,int r)
{
    if(tr[i].l==l&&tr[i].r==r)
    return tr[i].c;
    pushdown(i);
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(r<=md)
    return get(lc,l,r);
    else if(l>md)
    return get(rc,l,r);
    else
    return get(lc,l,md)+get(rc,md+1,r);
}
int chk(int x)
{
//    printf("%d\n",x);
    for(int i=1;i<=n;i++)
    d[i]=a[i]>x;
    num=0;
    bt(1,n);
    for(int i=0;i<m;i++)
    {
        int l=b[i].l,r=b[i].r,op=b[i].op;
        int s=get(1,l,r);
//        printf("%d\n",s);
        if(op)
        {
            chg(1,l,l+s-1,1);
            chg(1,l+s,r,0);
        }
        else
        {
            chg(1,r-s+1,r,1);
            chg(1,l,r-s,0);
        }
    }/*
    for(int i=1;i<=n;i++)
    printf("%d ",get(1,i,i));
    puts("");*/
    return get(1,q,q);
}
int cmp(int x,int y)
{
    return chk(x);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        c[i]=a[i];
    }
    sort(c+1,c+1+n);
    for(int i=0;i<m;i++)
    scanf("%d%d%d",&b[i].op,&b[i].l,&b[i].r);
    scanf("%d",&q);
    printf("%d",*lower_bound(c+1,c+1+n,0,cmp));
}