首页 > 其他分享 >CF650D Zip-line

CF650D Zip-line

时间:2024-08-12 23:28:19浏览次数:16  
标签:Zip int mid fx while CF650D LIS line op

每次操作会修改一个数,每次要求LIS

暴力做法每次都做修改,重新求一次LIS,复杂度 \(O(n^2logn)\)

考虑每次修改会对答案造成什么影响。设 \(f_i\) 为以 \(i\) 结尾的LIS,设 \(g_i\) 为以 \(i\) 开头的LIS
那么修改前的LIS是 \(ans1=max(f_i+g_i-1)\)
在预处理出修改后的左右两边的 \(f_i’\) 和 \(g_i’\)

可能在修改后,恰好能将两侧的答案接起来,并让答案更长,此时询问的答案为 \(f_i'+g_i'+1\)
否则要判断在修改了当前节点后有没有影响。如果当前位置一定在原来的LIS上,则答案为 \(ans1-1\) ,否则为 \(ans1\) 。

*如何判断是否在LIS的必经点上?
首先,如果\(i\)在LIS上,则\(i\)一定在LIS的第\(f_i\)位。(因为\(f_i\)极大)
所以如果在其他所有满足 \(f_j+g_j-1=ans1\) 的\(j\)中,不存在 \(f_i=f_j\) ,那么它一定在LIS的必经点上。(如果存在 \(f_i=f_j\) ,则当前这一位\(i\)可以被替换成\(j\),不对答案有影响)

所以可以用二分+辅助数组求出 \(f_i\) , \(g_i\) ,\(f_i’\) 和 \(g_i’\) ,开桶统计 \(f_i\) 和出现的位置,判断一下即可。

时间 \(O(nlogn)\) ,可以通过。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=400005;
const int inf=0x3f3f3f3f;
inline int read(){
    int f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return f*x;
}
int n,q;
int a[N];
struct node{
    int x,val,id;
    int f,g;
    bool operator<(const node& p)const{
        return x<p.x;
    }
}op[N];
int f[N],g[N];
int fx[N];
int ans1;
int tong[N],pos[N];
int ans[N];
inline void work1(){  //求出f,g
    for(int i=1;i<=n;i++)fx[i]=inf;
    for(int i=1;i<=n;i++){
        int l=1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(a[i]>fx[mid])l=mid;
            else r=mid-1;
        }
        if(a[i]<=fx[l])l=0;
        f[i]=l+1;
        fx[l+1]=min(fx[l+1],a[i]);
    }
    for(int i=1;i<=n;i++)fx[i]=0;
    for(int i=n;i>=1;i--){
        int l=1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(a[i]<fx[mid])l=mid;
            else r=mid-1;
        }
        if(a[i]>=fx[l])l=0;
        g[i]=l+1;
        fx[l+1]=max(fx[l+1],a[i]);
    }
    for(int i=1;i<=n;i++){
        ans1=max(ans1,f[i]+g[i]-1);
    }
}
inline void work2(){  //处理询问
    for(int i=1;i<=n;i++)fx[i]=inf;
    int now=0;
    for(int i=1;i<=q;i++){
        for(int j=now+1;j<=op[i].x-1;j++){
            fx[f[j]]=min(fx[f[j]],a[j]);
        }
        int l=1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(op[i].val>fx[mid])l=mid;
            else r=mid-1;
        }
        if(op[i].val>fx[l])op[i].f=l;
        else op[i].f=0;
        now=op[i].x-1;
    }
    for(int i=1;i<=n;i++)fx[i]=0;
    now=n+1;
    for(int i=q;i>=1;i--){
        for(int j=now-1;j>=op[i].x+1;j--){
            fx[g[j]]=max(fx[g[j]],a[j]);
        }
        int l=1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(op[i].val<fx[mid])l=mid;
            else r=mid-1;
        }
        if(op[i].val<fx[l])op[i].g=l;
        else op[i].g=0;
        now=op[i].x+1;
    }
    for(int i=1;i<=n;i++){
        if(f[i]+g[i]-1!=ans1)continue;
        tong[f[i]]++;
        if(tong[f[i]]==1)pos[f[i]]=i;
        else pos[f[i]]=0;
    }
}
int main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=q;i++){
        op[i].x=read(),op[i].val=read();
        op[i].id=i;
    }
    sort(op+1,op+1+q);
    work1();
    work2();
    for(int i=1;i<=q;i++){
        int x=op[i].x,id=op[i].id;
        int f1=op[i].f,g1=op[i].g;
        if(pos[f[x]]==x)ans[id]=max(ans1-1,f1+g1+1);
        else ans[id]=max(ans1,f1+g1+1);
    }
    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
    return 0;
}

这份代码在CodeForces上 \(671ms\) 通过。

标签:Zip,int,mid,fx,while,CF650D,LIS,line,op
From: https://www.cnblogs.com/TanHaoren/p/18355924

相关文章

  • OpenCV C++ 霍夫直线变换-Hough Line Transform
    使用OpenCV在C++中实现霍夫直线变换(HoughLineTransform)可以通过以下步骤完成。我们将首先进行边缘检测,然后应用霍夫直线变换来检测图像中的直线。步骤概述读取图像:使用cv::imread读取图像。灰度转换:将图像转换为灰度图。边缘检测:使用Canny边缘检测器。霍夫直线......
  • InnoDB-Online_DDL
    InnoDBOnlineDDL1.OnlineDDL的优势在繁忙的生产环境中提高响应速度和可用性,在这种环境中,使一个表在几分钟或几小时内不可用是不现实的。对于就地操作,在DDL操作期间使用LOCK子句调整性能和并发性之间的平衡的能力。比表复制方法占用更少的磁盘空间和I/O开销2.Online......
  • 轻松搞定 RAR、Zip压缩包密码!Hashcat +john the ripper 亲测好用!
    不需要密码字典,可以用GPU来强行破解,速度非常快。GPU驱动程序要求:Linux上的AMDGPU需要“AMDGPU”(21.50或更高版本)和“ROCm”(5.0或更高版本)Windows上的AMDGPU需要“AMDAdrenalinEdition”(确切地说是Adrenalin22.5.1)IntelCPU需要“IntelCore和IntelXeon......
  • OFtutorial02_commandLineArgumentsAndOptions
    OFtutorial2.CargList类如图包含很多函数,常用的addNote(输出字符串),noParallel(去掉基类中的并行选项),addBoolOption,addOption(增加选项)源码#include"fvCFD.H"#argc即argumentcount的缩写,保存程序运行时传递给主函数的参数个数;argv即argumentvector的缩写,保存程序运行......
  • 开发者们都在讨论Bandizip,你真的不心动吗?
    前言在这个信息爆炸的时代,数据如潮水般涌来,我们的电脑空间似乎永远不够用;每当面对堆积如山的文件,你是否也曾感到头疼不已?别急,小江湖今天就要带你走进一个神奇的世界,那里有一款软件,它如同一位隐世高手,以迅雷不及掩耳之势,轻松解决你的所有烦恼。想象一下,你不再需要为找不到合适......
  • 从零入门AI生图原理&实践 跑通最简的Baseline
    目录下载baseline文件(大约需要2分钟)进入文件夹,打开baseline文件安装环境,然后重启kernel调整prompt,设置你想要的图片风格,依次修改8张图片的描述依次顺序运行剩余的代码块,点击代码框左上角执行按钮,最终获得图片(大约需要20分钟)下载baseline文件(大约需要2分钟)gitlfsinsta......
  • Diffusers中Pipeline的数据类型是怎么设置和转化的,pipeline.dtype和pipeline.from_pre
    参考资料:Diffusers中DiffusionPipeline基类的[源码]众所周知Pipeline是Diffusers中最重要的一个API接口,一直以来我都对这个接口数据结构的获取一知半解,今天看了下源码终于知道了这个API结构的数据类型是如何设置的。直接看代码:@propertydefdtype(self)->torch......
  • 22.python自定义函数(format,zip)
    python自定义函数一、常见的自定义函数已经学过的函数:list、print、set、str、type、tuple、dict、range、input等今天学的函数:format二、实战讲解(一)format函数1、默认显示案例:hz="{}{}".format("dcs","43")print(hz)#dcs43hz="{}".format("dcs","43"......
  • DPDI online在线调度系统介绍
    DPDIonline产品简介DPDIOnline是一款基于Kettle的强大在线任务调度平台,凭借其高效与灵活性,专为调度和监控Kettle客户端生成的ETL任务而设计DPDIOnline功能特性多服务器多版本支持:无缝整合不同服务器和Kettle版本,确保任务执行兼容性和一致性联合开发:由三倍镜成员......
  • 将文本放置在 axvline 旁边
    我需要在图中标记某些值而不更改轴限制,例如,我想要一条垂直线x=pi/2来标记max(cos(x))但我不想找出适当的y限制,我只想我的垂直线从轴的33%到67%。因此,按照matplotlib中的垂直和水平线,我正在使用axvline现在,我想......