[HEOI2016/TJOI2016]排序

· · 个人记录

传送门

一个巨佬非常有借鉴意义的思路：

先抛开题目，我们将序列变成01序列，那我们可以怎么做？

很显然，如果[l,r]要降序，那么我们就将[l,l+len-1]标记为1，[l+len,r]标记为0（len表示[l,r]内1的个数），升序同理

这可以用线段树轻易维护

回归题目：

我们考虑二分 询问位置上的数值（设为mid）

我们将所有大于等于mid的数更改为1，小于mid的更改为0

然后按照题目给出的排序，用刚才01序列的排序方法，完完整整做一次排序

那么如果最后在q位置上的数为1，代表 mid>=ans

否则 mid<ans

最后就可以二分出一个答案

时间复杂度：O(log^2_n*m)

常数稍微大点，不过4s还是稳过的

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
using namespace std;
inline int reads()
{
    int sign=1,re=0; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') sign=-1; c=getchar();}
    while('0'<=c&&c<='9'){re=re*10+(c-'0'); c=getchar();}
    return sign*re;
}
int n,m,Q,a[100005];
struct qs
{
    int ty,l,r;
}q[100005];
int l,r;
namespace Seg_Tree
{
    #define ls (now<<1)
    #define rs ((now<<1)|1)
    struct Tree
    {
        int cnt,tag;
    }tr[400005];
    inline void push_up(int now)
    {
        tr[now].cnt=tr[ls].cnt+tr[rs].cnt;
    }
    inline void push_down(int now,int l,int r)
    {
        int mid=(l+r)>>1;
        if(tr[now].tag)
        {
            tr[ls].tag=tr[rs].tag=tr[now].tag;
            if(tr[now].tag==1) tr[ls].cnt=(mid-l+1),tr[rs].cnt=(r-mid);
            else tr[ls].cnt=tr[rs].cnt=0;
            tr[now].tag=0;
        }
    }
    void buildtree(int now,int l,int r,int num)
    {
        tr[now].tag=0;
        if(l==r)
        {
            tr[now].cnt=(a[l]>=num);
            return;
        }
        int mid=(l+r)>>1;
        buildtree(ls,l,mid,num); buildtree(rs,mid+1,r,num);
        push_up(now);
    }
    void modify(int now,int l,int r,int L,int R,int nw)
    {
        if(L>R) return;
        if(L<=l&&r<=R)
        {
            (nw==1)?tr[now].cnt=(r-l+1):tr[now].cnt=0;
            tr[now].tag=nw;
            return;
        }
        int mid=(l+r)>>1; push_down(now,l,r);
        if(L<=mid) modify(ls,l,mid,L,R,nw);
        if(mid<R) modify(rs,mid+1,r,L,R,nw);
        push_up(now);
    }
    int query(int now,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R) return tr[now].cnt;
        int mid=(l+r)>>1,re=0; push_down(now,l,r);
        if(L<=mid) re+=query(ls,l,mid,L,R);
        if(mid<R) re+=query(rs,mid+1,r,L,R);
        return re;
    }
    bool point_query(int now,int l,int r)
    {
        if(l==r) return tr[now].cnt;
        int mid=(l+r)>>1; push_down(now,l,r);
        if(Q<=mid) return point_query(ls,l,mid);
        else point_query(rs,mid+1,r);
    }
} using namespace Seg_Tree;
inline bool work(int mid)
{
    buildtree(1,1,n,mid);
    for(int i=1;i<=m;i++)
    {
        int cnt=query(1,1,n,q[i].l,q[i].r);
        if(q[i].ty)
        {
            modify(1,1,n,q[i].l,q[i].l+cnt-1,1);
            modify(1,1,n,q[i].l+cnt,q[i].r,-1);
        }
        else
        {
            modify(1,1,n,q[i].r-cnt+1,q[i].r,1);
            modify(1,1,n,q[i].l,q[i].r-cnt,-1);
        }
    }
    return point_query(1,1,n);
}
int main()
{
    n=reads(); m=reads();
    for(int i=1;i<=n;i++) a[i]=reads();
    for(int i=1;i<=m;i++) q[i].ty=reads(),q[i].l=reads(),q[i].r=reads();
    Q=reads();
    r=n+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(work(mid)) l=mid;
        else r=mid;
    }
    printf("%d\n",l);
    return 0;
}