原题链接 排序

题目大意

给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部升序或降序排序，最后询问第 $q$ 位置上的数字。$n,m≤10^5$

题目分析

如果用sort排序每次排序时间复杂度$nlogn$，总时间复杂度$O(mn\log n)$，那么成功$TLE$。

考虑$01$序列排序？
对于这个问题，我们可以使用线段树来维护。
查询一段区间内的$1$的个数记为$cnt$，
如果是升序，就将这段区间的$[r-cnt+1, r]$都更改为1，将$[l, r-cnt]$更改为$0$。
降序则将$[l, l+cnt-1]$更改为1，将$[l+cnt,r]$更改为$0$。
这样我们就成功地把排序转化为了区间查询和区间修改。

然后二分答案，把小于mid的值设为0，大于mid值设为1，然后就可以得出答案。这样时间复杂度$O(m\log n\log n)$

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
struct node
{
    int l,r,cnt,lazy;    //lazy=1 是表示这个区间所有值应该为1 
}tree[N<<2];             //lazy=-1是表示这个区间所有值应该为0
int n,m,k;
int a[N];
struct Q
{
    int op,l,r;
}q[N];
void pushup(int u)
{
    tree[u].cnt=tree[u<<1].cnt+tree[u<<1|1].cnt;
}
void build(int u,int l,int r,int x)
{
    tree[u]={l,r};
    if(l==r)
    {
        tree[u].cnt=int(a[l]>=x);
        tree[u].lazy=0;
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid,x);
    build(u<<1|1,mid+1,r,x);
    pushup(u);
}
void pushdown(int u)
{
    if(tree[u].lazy==0) return;
    tree[u<<1].cnt=(tree[u<<1].r-tree[u<<1].l+1)*int(tree[u].lazy==1);
    tree[u<<1|1].cnt=(tree[u<<1|1].r-tree[u<<1|1].l+1)*int(tree[u].lazy==1);
    tree[u<<1].lazy=tree[u].lazy;
    tree[u<<1|1].lazy=tree[u].lazy;
    tree[u].lazy=0;
}
void modify(int u,int l,int r,int x)
{
    if(l>r) return;
    if(tree[u].l>=l&&tree[u].r<=r)
    {
        tree[u].cnt=(tree[u].r-tree[u].l+1)*x;
        if(x) tree[u].lazy=1;
        else tree[u].lazy=-1;
        return;
    }
    pushdown(u);
    int mid=tree[u].l+tree[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,x);
    if(r>mid) modify(u<<1|1,l,r,x);
    pushup(u);
}
int query(int u,int l,int r)
{
    if(tree[u].l>=l&&tree[u].r<=r) return tree[u].cnt;
    pushdown(u);
    int mid=tree[u].l+tree[u].r>>1;
    int v=0;
    if(l<=mid) v=query(u<<1,l,r);
    if(r>mid) v+=query(u<<1|1,l,r);
    return v;
}
bool check(int mid)
{
    memset(tree,0,sizeof tree);
    build(1,1,n,mid);
    for(int i=1;i<=m;i++)
    {
        int l=q[i].l,r=q[i].r,cnt=query(1,l,r);
        if(q[i].op) modify(1,l,cnt+l-1,1),modify(1,cnt+l,r,0);
        else modify(1,l,r-cnt,0),modify(1,r-cnt+1,r,1);
    }
    return query(1,k,k);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&q[i].op,&q[i].l,&q[i].r);
    scanf("%d",&k);
    int l=1,r=n;

    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
    return 0;
}

记录

窗口的星星 做了一上午，吃个午饭到现在才把这个题搞定，难受的是不用scanf结果还$TLE$一个点，我写的线段树咋这么慢-。-

cin 10.06s TLE一个点
scanf 9.40s AC
scanf+$O_2$ 4.93s AC