洛谷 P2824 【HEOI2016/TJOI2016】排序题解

2020-2-29 xiaoh

题意

给定有 $n$ 个正整数的序列 $a$ ( $1\leq n\leq 10^5$ ),且 $a$ 为 $1$ ~ $n$ 的一个排列.接下来给定 $m$ 个操作( $1\leq m\leq 10^5$ ),第 $i$ 个操作为将区间 $[a_l,a_r]$ 按照升序/降序排列.求最终在第 $q$ 个位置上的数.

题解

本题是个人认为出的相当好的一道题,思路非常的精妙.
由于对于所有数进行排序是 $O(n\log n)$ 的,所以不可能依次进行排序,所以考虑二分进行处理.假设当前二分的值为 $x$ ,则将所有小于 $x$ 的数全部设为 $0$ ,其余的都设为 $1$ .显然,我们可以用线段树来维护,并且用 $O(\log n)$ 的复杂度进行维护.在所有的 $m$ 个操作结束后,我们只要检查第 $q$ 个位置上的数,若为 $1$ 则说明答案比 $x$ ,反之则比 $x$ 小.时间复杂度 $O(n\log^2 n)$ .

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=200010;
int n,m,q;
int a[MAXN];
struct node{
    int l,r;
    int num0,num1;
    int tag;
}f[MAXN*4];
int b[MAXN];
int pos;
inline int len(register int p)
{
    return f[p].r-f[p].l+1;
}
inline void pushup(register int p)
{
    f[p].num0=f[p<<1].num0+f[p<<1|1].num0;
    f[p].num1=f[p<<1].num1+f[p<<1|1].num1;
}
inline void pushdown(register int p)
{
    if(f[p].tag==1)
    {
        f[p<<1].num0=len(p<<1),f[p<<1].num1=0;
        f[p<<1|1].num0=len(p<<1|1),f[p<<1|1].num1=0;
        f[p<<1].tag=f[p<<1|1].tag=1;
    }
    else if(f[p].tag==2)
    {
        f[p<<1].num1=len(p<<1),f[p<<1].num0=0;
        f[p<<1|1].num1=len(p<<1|1),f[p<<1|1].num0=0;
        f[p<<1].tag=f[p<<1|1].tag=2;
    }
    f[p].tag=0;
}
void init(register int p)
{
    f[p].tag=0;
    if(f[p].l==f[p].r)
    {
        if(b[f[p].l]==0) f[p].num0=1,f[p].num1=0;
        else f[p].num1=1,f[p].num0=0;
        return;
    }
    init(p<<1),init(p<<1|1);
    pushup(p);
}
void modify(register int p,register int l,register int r,register int type)
{
    if(f[p].l>=l&&f[p].r<=r)
    {
        if(type==0) f[p].num0=len(p),f[p].num1=0,f[p].tag=1;
        else f[p].num1=len(p),f[p].num0=0,f[p].tag=2;
        return;
    }
    pushdown(p);
    register int mid=(f[p].l+f[p].r)>>1;
    if(l<=mid) modify(p<<1,l,r,type);
    if(r>mid) modify(p<<1|1,l,r,type);
    pushup(p);
}
int query(register int p,register int l,register int r,register int type)
{
    if(f[p].l>=l&&f[p].r<=r) return (type==0)? f[p].num0:f[p].num1;
    pushdown(p);
    register int ret=0;
    register int mid=(f[p].l+f[p].r)>>1;
    if(l<=mid) ret+=query(p<<1,l,r,type);
    if(r>mid) ret+=query(p<<1|1,l,r,type);
    return ret;
}
void build(register int p,register int l,register int r)
{
    f[p].l=l,f[p].r=r;
    if(l==r) return;
    register int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
struct node2{
    int l,r;
    int type;
}op[MAXN];
inline bool check(register int x)
{
    for(register int i=1;i<=n;i++) b[i]=(a[i]>=x);
    init(1);
    for(register int i=1;i<=m;i++)
    {
        register int l=op[i].l,r=op[i].r;
        register int x=query(1,l,r,0);
        if(op[i].type==0) modify(1,l,l+x-1,0),modify(1,l+x,r,1);
        else modify(1,l,r-x,1),modify(1,r-x+1,r,0);
    }
    return query(1,q,q,1);
}
int main()
{
    read(n),read(m);
    for(register int i=1;i<=n;i++) read(a[i]),assert(a[i]>=1&&a[i]<=n);
    for(register int i=1;i<=m;i++) read(op[i].type),read(op[i].l),read(op[i].r);
    read(q);
    build(1,1,n);
    register int l=0,r=n+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    write(l),putchar('\n');
	return 0;
}

后记

经过本题的折磨考验,我终于知道线段树的常数有多可怕了o(╥﹏╥)o硬生生删了几个无用的操作,加上一堆的inline和register,才终于卡过去了……不得不说,常数真是个万恶的东西啊……