P2824 [HEOI2016/TJOI2016]排序

一道十分神奇的线段树题,做法十分的有趣.

• 前置芝士

  1.线段树:一个十分基础的数据结构,在这道题中起了至关重要的作用.
  2.一种基于01串的神奇的二分思想:在模拟赛中出现了这道题,可以先去做一下,这样可能有助于理解.

• 具体做法

  可以发现sort是非常慢的,每次多要\(O(N\log_2N)\),最后的时间复杂度为\(O(MN\log_2N)\),肯定是会T的,而且sort这个东西也不是很好去维护.可以发现,最后需要查询的数只有一个,于是就可以想到离线的做法.\(N\)虽然不小,但其实并不算大,\(O(N\log^2_2N)\)是可以过的,那么有没有这样的方法呢,那自然是有的,所以就要用到01串的一种神奇的用法了.
  对于每一次sort的时间复杂度为\(O(N\log_2N)\),那么如果这时一个01串呢,可以发现这样的时间复杂度就可以变为\(O(N)\),而且这时区间覆盖,再用线段树维护就只要\(O(\log_2N)\).
  
  (如这样一个01序列,灰色为1,白色为0,只要查询出区间的和,将最后的这几个覆盖为1,前面覆盖为0,这样为升序,降序同理)
  这样就出现了一种单调性,可以发现如果将这个序列中大于等于最终答案的数改为1,小于改为0,那么最后在答案位置的数就一定是1了,反之则一定是0,所以就可以二分答案了,最终的时间复杂度为\(O(M\log^2_2N)\).(二分为\(O(\log_2N)\),每一次check需要\(O(M\log_2N)\))

• 代码

#include<bits/stdc++.h>
#define rap(i,first,last) for(int i=first;i<=last;++i)
//线段树标准define
#define Lson (now<<1)
#define Rson (now<<1|1)
#define Middle ((left+right)>>1)
#define Left Lson,left,Middle
#define Right Rson,Middle+1,right
#define Now nowleft,nowright
using namespace std;
const int maxN=1e5+7;
int N,M,Q;
int L[maxN],R[maxN];
int arr[maxN];
bool UD[maxN];
struct Lazy//lazy标记
{
    int cover;
    bool covercheck;//用一个bool型标记这个位置需不需要cover
};
struct Tree//这是一颗资瓷区间覆盖和区间查询和的线段树
{
    int sum;
    Lazy lazy;
}tree[maxN*4];
void PushUp(int now)
{
    tree[now].sum=tree[Lson].sum+tree[Rson].sum;//合并左右子树
}
void Build(int k,int now=1,int left=1,int right=N)//建树
{
    tree[now].lazy.covercheck=0;
    if(left==right)
    {
        tree[now].sum=(arr[left]>=k);//在大于等于k时的值为1,小于为0
        return;
    }
    Build(k,Left);
    Build(k,Right);
    PushUp(now);
}
void Down(int now,int left,int right,int cover)//修改这棵树
{
    tree[now].sum=(right-left+1)*cover;
    tree[now].lazy.covercheck=1;
    tree[now].lazy.cover=cover;
}
void PushDown(int now,int left,int right)//下传标记
{
    if(tree[now].lazy.covercheck)//有标记才下传
    {
        Down(Left,tree[now].lazy.cover);
        Down(Right,tree[now].lazy.cover);
        tree[now].lazy.covercheck=0;
    }
}
void UpData(int nowleft,int nowright,int cover,int now=1,int left=1,int right=N)//区间覆盖部分
{
    if(nowright<left||right<nowleft)return;
    if(nowleft<=left&&right<=nowright)
    {
        Down(now,left,right,cover);//直接修改
        return;
    }
    PushDown(now,left,right);//下传标记
    UpData(Now,cover,Left);//修改左子树
    UpData(Now,cover,Right);//修改右子树
    PushUp(now);//合并
}
int Query(int nowleft,int nowright,int now=1,int left=1,int right=N)//查询区间和
{
    if(nowright<left||right<nowleft)return 0;
    if(nowleft<=left&&right<=nowright)//直接返回
    {
        return tree[now].sum;
    }
    PushDown(now,left,right);//下传标记
    //值为左右子树的值之和
    int result=Query(Now,Left)+Query(Now,Right);
    PushUp(now);//需要合并
    return result;
}
bool check(int middle)//check的部分
{
    Build(middle);//将大于等于middle我改为1,小于为0
    int num;
    rap(i,1,M)
    {
        num=Query(L[i],R[i]);//其中1的个数
        if(UD[i])
        {
            //降序修改
            UpData(L[i],L[i]+num-1,1);//前num个为1
            UpData(L[i]+num,R[i],0);//后面的为0
        }
        else
        {
            //升序同理
            num=R[i]-L[i]+1-num;
            UpData(L[i],L[i]+num-1,0);
            UpData(L[i]+num,R[i],1);
        }
    }
    return Query(Q,Q);//返回最终位置的值
}
int getanswer()//二分答案
{
    int left=1,right=N;//因为这是一个排列,所以这个数是在1~N的范围内
    int answer=-1;
    while(left<=right)
    {
        if(check(Middle))
        {
            //如果可以就记录答案,并且修改left
            answer=Middle;
            left=Middle+1;
        }
        else
        {
            //不可以就修改right
            right=Middle-1;
        }
    }
    return answer;//返回最终答案
}
int main()
{
    //离线做法
    scanf("%d%d",&N,&M);
    rap(i,1,N)scanf("%d",&arr[i]);
    rap(i,1,M)scanf("%d%d%d",&UD[i],&L[i],&R[i]);
    scanf("%d",&Q);
    printf("%d",getanswer());//输出答案
    return 0;
}

一种神奇的思路.

P2824 [HEOI2016/TJOI2016]排序

原文：https://www.cnblogs.com/Sxy_Limit/p/12198528.html