TJOI2016&HEOI2016-排序

@zryabc  December 15, 2018

题目

在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。

这个难题是这样子的:给出一个1到n的全排列,现在对这个全排列序列进行m次局部排序,排序分为两种:

• (0,l,r)表示将区间[l,r]的数字升序排序

• (1,l,r)表示将区间[l,r]的数字降序排序

最后询问第q位置上的数字。

思路

第一反应是数据结构强搞,肯定有一个特别强大的数据结构支持区间的排序操作(这样的数据结构也太强了吧。

后来发现其实确实是可以的,但是是一种神仙结构现在还不会。

在指点下,我们的思路成功转到了二分的正轨上但是怎么二分呢?

一般的二分都是二分答案。而答案一定是满足一种单调性,这样我们的问题就从判定最优性转向了判定存在性,在这种条件下,一般的问题解决起来会容易得多。

一些问题,关键是你不会往二分上想,一旦你往二分上想,会发现这其实是一道简单题

​ -----------------某C

但是此题往二分上想了,还是没发现它简单在哪。

究其原因,此题的单调性较难看出。二分什么?二分了答案又能怎么样?答案满足单调性吗?check函数怎么写?

再瞎扯一道别的题:
YCJSOI3071生活品质

Alberta的城市建设时,以矩形方格组成街区。街区由北向南以坐标0到R-1表示,由西到到东以坐标0到C-1表示。

每个街区的生活质量用1到R*C之间不同的数字表示,成为质量排名,其中1最好,而R*C则为最差。

城市规划部门希望所在街区当中找出一块矩形的街区组,其大小为:由北向南为H,由西向东为W,且其质量排名中位数所在的同大小的街区组中最好。

H和W分别是不超过R和C的奇数。在奇数个质量排名中,其中中位数被定义在该街区组中排名第m,且质量排名好于该街区的数目与质量排名差于该街区的数量相等。

这里二分的就不止是答案,而只是<=某个答案是否可行,这样显然的单调性就显示出来了。

再回到此题,我们的思路是否也能转移到这上面来呢?我们枚举一个数,然后check函数的内容是最后q的那个位子是否>=此数,这样答案的单调性就显然了。我们枚举的数越小,check是1的机会就越多,找到最后一个check为1的数,那就是答案了。

用线段树维护check就好了。

#include<bits/stdc++.h>
#define M 100005
#define clr(x,y) memset(x,y,sizeof(x))
#define fa tree[p]
#define lson tree[p<<1]
#define rson tree[p<<1|1]
using namespace std;
int n,m,A[M];
struct node{
    int op,l,r; 
};
node Q[M]; 
int now=0;
struct Seg{
    struct YD{
        int l,r,mark;//此区间是0是1,或者并没有标记
        int cnt;//此区间0的个数 
        int len(){
            return r-l+1;   
        }
    }tree[M<<2];
    void up(int p){
        fa.cnt=lson.cnt+rson.cnt;
    }
    void down(int p){
        if(fa.mark==-1)return;
        lson.mark=rson.mark=fa.mark;
        if(fa.mark==1)lson.cnt=rson.cnt=0;
        else lson.cnt=lson.len(),rson.cnt=rson.len();
        fa.mark=-1;
    }
    void build(int l,int r,int p){
        fa.l=l;fa.r=r;fa.mark=-1;fa.cnt=0;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(l,mid,p<<1);
        build(mid+1,r,p<<1|1);
    }
    void update(int l,int r,int f,int p){
        if(fa.l==l&&fa.r==r){
            fa.mark=f;
            if(f==0)fa.cnt=fa.len();
            else fa.cnt=0;
        }
        else {
            down(p);
            int mid=(fa.l+fa.r)>>1;
            if(r<=mid)update(l,r,f,p<<1);
            else if(l>mid)update(l,r,f,p<<1|1);
            else {
                update(l,mid,f,p<<1);
                update(mid+1,r,f,p<<1|1);
            }
            up(p);
        }
    }
    int query(int l,int r,int p){
        if(fa.l==l&&fa.r==r)return fa.cnt;
        down(p);
        int mid=(fa.l+fa.r)>>1;
        if(r<=mid)return query(l,r,p<<1);
        else if(l>mid)return query(l,r,p<<1|1);
        return query(l,mid,p<<1)+query(mid+1,r,p<<1|1);     
    }
}T;
bool check(int x){
    T.build(1,n,1);
    for(int i=1;i<=n;i++){
        if(A[i]>=x)T.update(i,i,1,1);
        else T.update(i,i,0,1);
    }   
    for(int i=1;i<=m;i++){
        int l=Q[i].l,r=Q[i].r;
        int ct=T.query(l,r,1);
        if(Q[i].op==0){
            if(ct!=0)T.update(l,l+ct-1,0,1);
            if(ct!=r-l+1)T.update(l+ct,r,1,1);
        }
        else {
            ct=r-l+1-ct;
            if(ct!=0)T.update(l,l+ct-1,1,1);
            if(ct!=r-l+1)T.update(l+ct,r,0,1);
        }
    }
    return !T.query(now,now,1);
}
int main(){
    cin>>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",&now);
    int l=1,r=n,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

添加新评论