[HEOI2016/TJOI2016]排序

链接：https://www.luogu.org/problemnew/show/P2824

题解：

思路非常奇特的一道题

第一次做应该很难想出来。。

考虑一个序列只有0/1

那么将区间排序就只需将0/1放在最前面/最后面即可，这个显然是可以用线段树来维护的

那么考虑原题

我们可以先二分答案，然后将比这个数大的数标记为1，比这个数小的数标记为0

另外注意线段树建造的时候要将x和lazy值初始化

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
#define mid (h+t)/2
struct re
{
    int x,h,t,lazy;
}p[maxn*5];
int n,m,a[maxn],bb[maxn],b[maxn],c[maxn],d[maxn],f[maxn],goal;
void updata(int x)
{
    p[x].x=p[x*2].x+p[x*2+1].x;
}
void build(int x,int h,int t)
{
    p[x].h=h; p[x].t=t; p[x].x=0; p[x].lazy=0;
    if (h==t)
    {
        p[x].x=f[h]; return;
    }
    build(x*2,h,mid); build(x*2+1,mid+1,t);
    updata(x);
}
void down(int x)
{
   if (p[x].lazy)
   {
     p[x].x=(p[x].t-p[x].h+1)*(p[x].lazy-1);
     if (p[x].h!=p[x].t)
     {
       p[x*2].lazy=p[x].lazy;
       p[x*2+1].lazy=p[x].lazy;
     }
     p[x].lazy=0;
  }
}
void change(int x,int h,int t,int sum)
{
    down(x);
    if (p[x].h>t||p[x].t<h) return;
    if (h<=p[x].h&&p[x].t<=t)
    {
        p[x].lazy=sum; down(x);
        return;
    }
    change(x*2,h,t,sum); change(x*2+1,h,t,sum);
    updata(x);
}
int query(int x,int h,int t)
{
    down(x);
    if (p[x].h>t||p[x].t<h) return(0);
    if (h<=p[x].h&&p[x].t<=t)
    {
        return(p[x].x);
    }
    return(query(x*2,h,t)+query(x*2+1,h,t));
}
bool check(int x)
{
    for (int i=1;i<=n;i++)
      if (a[i]>=x) f[i]=1; else f[i]=0;
    build(1,1,n);
    for (int i=1;i<=m;i++)
    {
        if (bb[i]==0)
        {
          int x=query(1,c[i],d[i]);
          change(1,d[i]-x+1,d[i],2);
          change(1,c[i],d[i]-x,1);    
        }
        else
        {
          int x=query(1,c[i],d[i]);
          change(1,c[i]+x,d[i],1);
          change(1,c[i],c[i]+x-1,2);    
        }
    }
    if (query(1,goal,goal)) return(true); else return(false);
}
int main()
{
    freopen("noip.in","r",stdin);
    freopen("noip.out","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for (int i=1;i<=m;i++)
    {
        cin>>bb[i]>>c[i]>>d[i];
    }
    cin>>goal;
    memcpy(b,a,sizeof(a));
    int h=1,t=n;
    sort(b+1,b+n+1);
    while (h<t)
    {
      int midd=(h+t+1)/2;
      if (check(b[midd])) h=midd; else t=midd-1;    
    }
    cout<<b[h];
}