首页 > 其他分享 >SNOI 2020 排列 题解

SNOI 2020 排列 题解

时间:2024-10-10 11:03:21浏览次数:8  
标签:int 题解 mn tr adic SNOI stmn 2020 NV

https://www.luogu.com.cn/problem/P6795

我一直很注重思考过程。这是做题的根本。

初看 T3,一个比较显然的贪心思路是,向外扩张合并连续段。

由此清晰地发现,从 1 到 N,被左边的数切分成若干“剩余”连续段,连续段内部,在右边的排列一定是连续的,右边的答案实际上已经确定。

并且这些连续段的延伸方向一定是由内向外。

关键在于如何对待跨越左边和右边的连续段,它决定了我们如何排列右边的“剩余”连续段。我们有必要考虑左边右边如何贡献。

对左边而言,当且仅当红框位置能贡献。形式化地说,记 a 离散化后的数组为 b,当且仅当 b[p~K] 是连续段,p 能作为左端点贡献。

取出所有 b[p~K],它们代表的值域区间从右到左记为 [li,ri]。

当一个端点变化时,一定是要加入当中的连续段的。比如下面那个绿块。

但是恰在变化之前,有一段端点不变的时间,这段时间内加入是任意的。比如上面那个绿块,它不是恰好变化时加入的,而是在下面那个绿块加入前加入的。

什么时候加入最优?我们有必要计算一个时刻 [li,ri] 加入的贡献。比如,假设此时有一些 l 不变的连续段,考虑加入小于 l 的一些绿块。显然,这些绿块中,每个绿块贡献相同。

(参考 DaiRuiChen007)

如果当前在这些 l 不变的连续段中,最右边的那个,贡献无疑是 1。

否则,如果上一个连续段的右端点与当前右端点间,没有应加入的绿块,贡献为上一个加一。

否则,若只有一段应加入的绿块,贡献为 2,否则为 1。

算出哪个地方加入最优后,构造是自然的。

你可能要问一个时刻左右端点都有任务怎么办。答案是先加入贡献更大的。证明:贡献小的端点(的贡献位置)一定是贡献大的端点的子集。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdlib>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T adic){a=max(a,adic);}
template<class T> void cmin(T&a,T adic){a=min(a,adic);}

const int NV=2e5;

namespace seg{
    struct SEGN{
        int mn,mnc,tad;
    } tr[NV*4+5];
    void doadd(int x,int z){
        tr[x].mn+=z;
        tr[x].tad+=z;
    }void dn(int x){
        if(tr[x].tad){
            doadd(x*2,tr[x].tad);
            doadd(x*2+1,tr[x].tad);
            tr[x].tad=0;
        }
    }void up(int x){
        tr[x].mn=min(tr[x*2].mn,tr[x*2+1].mn);
        tr[x].mnc=0;
        if(tr[x].mn==tr[x*2].mn) tr[x].mnc+=tr[x*2].mnc;
        if(tr[x].mn==tr[x*2+1].mn) tr[x].mnc+=tr[x*2+1].mnc;
    }void add(int x,int l,int r,int ql,int qr,int z){
        if(ql<=l&&r<=qr) return doadd(x,z);
        int mid=l+r>>1;
        dn(x);
        if(ql<=mid) add(x*2,l,mid,ql,qr,z);
        if(mid<qr) add(x*2+1,mid+1,r,ql,qr,z);
        up(x);
    }void build(int x,int l,int r){
        int mid=l+r>>1;
        tr[x].mn=0;
        tr[x].tad=0;
        tr[x].mnc=r-l+1;
        if(l!=r){
            build(x*2,l,mid);
            build(x*2+1,mid+1,r);
        }
    }
}

namespace xm{
    int N,K,a[NV+5],adic[NV+5],stmx[NV+5],stmn[NV+5],\
        bli[NV+5],bl[NV+5],br[NV+5],rk[NV+5],\
        vl[NV+5],vr[NV+5],vpl[NV+5],vpr[NV+5];
    void _(){
        scanf("%d%d",&N,&K);
        for(int i=1;i<=K;++i){
            scanf("%d",a+i);
            adic[i]=a[i];
        }

        std::sort(adic+1,adic+K+1);
        adic[K+1]=N+1;
        for(int i=1;i<=K;++i) rk[adic[i]]=i;
        for(int i=1,c=0;i<=K;++i)
            if(i==1||adic[i]>adic[i-1]+1){
                bli[i]=++c;
                bl[c]=br[c]=i;
            }else{
                bli[i]=c;
                br[c]=i;
            }
        for(int i=K,l=N+1,r=0,lal=N+1,lar=0,wl=0,wr=0;i;--i){
            cmin(l,rk[a[i]]);
            cmax(r,rk[a[i]]);
            if(r-l==K-i){
                if(l<lal) wl=0;
                else if(bli[r]!=bli[lar]) wl=(lar==br[bli[r]-1]);
                if(r>lar) wr=0;
                else if(bli[l]!=bli[lal]) wr=(lal==bl[bli[l]+1]);
                ++wl;
                ++wr;
                if(wl>vl[l]){
                    vl[l]=wl;
                    vpl[l]=i;
                }
                if(wr>vr[r]){
                    vr[r]=wr;
                    vpr[r]=i;
                }
                lal=l;
                lar=r;
            }
        }
        int ac=K;
        for(int i=K,l=N+1,r=0,lal=N+1,lar=0;i;--i){
            cmin(l,rk[a[i]]);
            cmax(r,rk[a[i]]);
            if(r-l==K-i){
                if(lal!=N+1){
                    for(int j=lal-1;j>=l+1;--j)
                    for(int k=adic[j]-1;k>adic[j-1];--k)
                        a[++ac]=k;
                    for(int j=lar+1;j<=r-1;++j)
                    for(int k=adic[j]+1;k<adic[j+1];++k)
                        a[++ac]=k;
                }
                lal=l;
                lar=r;
                const int wl=vpl[l]==i?vl[l]:0,wr=vpr[r]==i?vr[r]:0;
                if(wl>wr){
                    if(wl) for(int k=adic[l]-1;k>adic[l-1];--k) a[++ac]=k;
                    if(wr) for(int k=adic[r]+1;k<adic[r+1];++k) a[++ac]=k;
                }else{
                    if(wr) for(int k=adic[r]+1;k<adic[r+1];++k) a[++ac]=k;
                    if(wl) for(int k=adic[l]-1;k>adic[l-1];--k) a[++ac]=k;
                }
            }
        }
        ll ans=0;
        seg::build(1,1,N);
        *stmx=*stmn=0;
        for(int i=1;i<=N;++i){
            while(*stmx&&a[stmx[*stmx]]<a[i]){
                seg::add(1,1,N,*stmx==1?1:stmx[*stmx-1]+1,stmx[*stmx],-a[stmx[*stmx]]);
                --*stmx;
            }
            while(*stmn&&a[stmn[*stmn]]>a[i]){
                seg::add(1,1,N,*stmn==1?1:stmn[*stmn-1]+1,stmn[*stmn],a[stmn[*stmn]]);
                --*stmn;
            }
            seg::add(1,1,N,stmx[*stmx]+1,i,a[i]);
            seg::add(1,1,N,stmn[*stmn]+1,i,-a[i]);
            seg::add(1,1,N,1,i,-1);
            ans+=seg::tr[1].mnc;
            stmx[++*stmx]=stmn[++*stmn]=i;
        }
        printf("%lld\n",ans);
        for(int i=1;i<=N;++i) printf("%d ",a[i]);
        puts("");
    }
}

int main(){
    xm::_();
    return 0;
}

标签:int,题解,mn,tr,adic,SNOI,stmn,2020,NV
From: https://www.cnblogs.com/Zaunese/p/18455884

相关文章

  • 题解:CF1007D Ants
    题目传送门每只蚂蚁只走一对点肯定是不劣的,由此想到2-sat。限制条件是:若\((a,b)\)和\((c,d)\)两条链相交,则不能同时选。直接建图肯定是爆炸的。用树剖可以将\((a,b)\)这条链划分成\(O(\logn)\)个区间。因为同一条链的区间不交,限制条件变为若两个区间相交,则这两个点不......
  • BUUCTF_MISC题解析(6,8)
    6.乌镇峰会种图把打开的图片放进010editor,拉到最末尾就可以发现flag 8.N种方法解决打开文件是KEY.exe点击打不开,运行不了(exe文件是二进制文件),所以把他拉到010editor打开,data:image/jpg;base64,iVBORw0KGgo......gg==发现是base编码的形式,开头的提示说明是jpg格式的图片,......
  • 2020年华为杯数学建模竞赛C题论文和代码
    面向康复工程的脑电信号分析和判别模型    摘          要:脑电信号的识别和分类是脑机接口技术中非常重要的一环,使用者无需通过复杂训练就可以获得较高的识别准确率,具有稳定的锁时性和高时间精度特性。本文使用基于监督学习的随机森林,SVM算法,半监督学习S3VM......
  • 2020年华为杯数学建模竞赛D题论文和代码
    无人机集群协同对抗摘          要:本文针对非线性约束条件下红蓝双方无人机集群协同对抗的最优规划问题,结合贪婪队形、非线性规划、内点法、蒙特卡洛方法和全联立正交配置有限元法,构建了无人机集群协同对抗推演模型。针对问题一,构建了基于蒙特卡洛法的蓝方突防......
  • P6309 题解
    很经典但是很好的题目。/qiang标签:线段树。数轴上有一些关键点,不同的关键点可能在同一坐标。关键点的坐标均为整数。支持两种操作:删去/添加一些关键点。取一个点。使得它与\([l,r]\)范围内所有关键点的距离最小。求最小距离。\(\text{关键点的坐标数}\le3\times......
  • 深度学习No module named ‘torchvision.transforms.functional_tensor‘问题解决
    问题在进行深度学习训练过程中出现ModuleNotFoundError:Nomodulenamed'torchvision.transforms.functional_tensor'报错,多方查阅资料后得到了解决方案。关于我的环境:CUDA==12.1torch==2.4.1GPU==4090D原先进行深度学习用的CUDA11.3,torch1.2.1,但是在训练时出现nvrtc......
  • AGC005 题解
    目录A-STringB-MinimumSumC-TreeRestoringA-STring用栈模拟一下即可,具体的,当栈顶出现形如ST时,将其弹出。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llRead(){ intsig=1; llnum=0; charc=getchar(); while(!isdigit(c))......
  • 2024年江西省职业院校技能大赛高职组“数据库运行与管理“竞赛样题解析答案
    2024年江西省职业院校技能大赛高职组"数据库运行与管理"竞赛样题解析答案文章目录2024年江西省职业院校技能大赛高职组"数据库运行与管理"竞赛样题解析答案模块A:数据库理论模块B:数据库设计与运维`任务一参考答案:``任务二参考答案:`模块C:数据库查询与分析`模块C参考答案:`......
  • [NOIP2006 提高组] 作业调度方案 题解
    题目描述我们现在要利用 m 台机器加工 n 个工件,每个工件都有 m 道工序,每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。每个工件的每个工序称为一个操作,我们用记号 j-k 表示一个操作,其中 j 为 1 到 n 中的某个数字,为工件号;k 为 ......
  • NewStar CTF 2024 week1 题解
    1.base题目给了以下内容:Thisisabasequestion!4C4A575851324332474E324547554B494A5A4446513653434E564D444154545A4B354D45454D434E4959345536544B474D5134513D3D3D3D观察给出的字符串发现,字符串由数字0-9以及字母A-F组成,于是推测这可能是一个base16编码,于是将其解码,......