首页 > 其他分享 >Collecting Numbers II

Collecting Numbers II

时间:2024-07-31 12:28:11浏览次数:10  
标签:Collecting ll pos II Numbers && ans vx vy

原题链接

题解

如果一个 \(k\) ,其前面没有出现过 \(k-1\) ,那么回合数+1,我们令这样的数叫做断点

因此交换两个数 \(l,r\) 不会影响 \([1,l-1],[r+1,n]\) 内的断点

code

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;

ll a[200005];
ll pos[200005];

void solve()
{
    ll n,m;
    cin>>n>>m;

    for(ll i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        pos[x]=i;
        a[i]=x;
    }

    ll ans=1;
    for(ll i=2;i<=n;i++) ans+=pos[i-1]>pos[i];

    while(m--)
    {
        ll x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);
        ll vx=a[x],vy=a[y];
        if(vx>1&&pos[vx-1]>x&&pos[vx-1]<y) ans--;
        if(vx<n&&pos[vx+1]>x&&pos[vx+1]<y) ans++;
        if(vy>1&&pos[vy-1]>x&&pos[vy-1]<y) ans++;
        if(vy<n&&pos[vy+1]>x&&pos[vy+1]<y) ans--;
        if(abs(vx-vy)==1)
        {
            if(vx>vy) ans--;
            else ans++;
        }
        swap(a[x],a[y]);
        swap(pos[vx],pos[vy]);

        cout<<ans<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TT=1;
    //cin>>TT;
    while(TT--) solve();
    return 0;
}

标签:Collecting,ll,pos,II,Numbers,&&,ans,vx,vy
From: https://www.cnblogs.com/pure4knowledge/p/18334378

相关文章

  • 文件解析漏洞总结(IIS,NGINX,APACHE)
    目录一、IIS解析漏洞IIS6.X方式一:目录解析方式二:畸形文件解析IIS7.X利用条件环境配置下载链接:二、Nginx解析漏洞2.1:nginx_parsing利用条件利用姿势2.2:CVE-2013-4547影响版本利用姿势三、Apache解析漏洞3.1:apache_parsing利用姿势3.2:CVE-2017-15715影响版......
  • UCOSIII的中断和时间管理
    前言UCOSIII(也称为µC/OS-III)的中断管理是其实时操作系统(RTOS)功能的重要组成部分。中断是CPU的一种常见特性,用于向CPU通知异步事件的发生,使得CPU能够暂停当前正在执行的程序,转而执行中断服务程序(ISR)。在UCOSIII中,中断管理涉及多个方面,包括中断嵌套、中断服务程序的编写、临界......
  • Bracket Sequences II
    原题链接题解一个合法的括号序列,满足长度为偶数前缀和处处不小于0左括号等于右括号数量code#include<bits/stdc++.h>#definelllonglong#definelowbit(x)((x)&(-x))usingnamespacestd;constllinf=1e18;constllmod=1e9+7;llqpow(lla,lln){......
  • LeetCode - #107 二叉树的层序遍历 II
    文章目录前言1.描述2.示例3.答案关于我们前言我们社区陆续会将顾毅(Netflix增长黑客,《iOS面试之道》作者,ACE职业健身教练。)的Swift算法题题解整理为文字版以方便大家学习与阅读。LeetCode算法到目前我们已经更新到105期,我们会保持更新时间和进度(周一、......
  • 字符串——1.反转字符串II
    力扣题目链接给定一个字符串s和一个整数k,从字符串开头算起,每计数至2k个字符,就反转这2k个字符中的前k个字符。如果剩余字符少于k个,则将剩余字符全部反转。如果剩余字符小于2k但大于或等于k个,则反转前k个字符,其余字符保持原样。示例:输入:s="abcdefg",k=......
  • 【IEEE-CPS独立出版,高录用,该出版社检索快速且稳定!收稿主题大,管理、计算机相关主题皆可
    2024年创新与信息管理国际会议(ICIIM2024)为第四届管理科学和软件工程国际学术会议(ICMSSE2024)的分会,主会由ACM珠海分会,广州番禺职业技术学院主办;全国区块链行业产教融合共同体承办,将于2024年9月6-8日于广州召开。会议旨在为从事管理与信息工程领域的专家学者、工程技术人员、......
  • nii转dicom及修改dicom信息
    importnibabelimportnumpyasnpimportpydicomimportosfromtqdmimporttqdmdefconvertNsave(arr,file_dir,index=0,slice_thickness=1.0,pixel_spacing=(1.0,1.0)):"""`arr`:parameterwilltakeanumpyarraythatrepresents......
  • 算法笔记|Day10栈与队列II
    算法笔记|Day10栈与队列II☆☆☆☆☆leetcode150.逆波兰表达式求值题目分析代码☆☆☆☆☆leetcode239.滑动窗口最大值题目分析代码☆☆☆☆☆leetcode347.前K个高频元素(待补充)题目分析代码☆☆☆☆☆leetcode150.逆波兰表达式求值题目链接:leetcode150.......
  • yii2代码封装
    1、批量更新某个字段/***@throwsCDbException*@throwsCException*updatexxxTablesetcolumn1=casepk*whenwhenData1thencaseData1*...*END*whereidin(1,2,3...)*/publicfunctionbatc......
  • Allegro17.4 “.brd“ 转 ASCII
    1.找到`Cadence\SPB_Data`文件夹(一般在Allegro的安装目录下可以找到),添加到系统变量`HOME=xxx\Cadence\SPB_Data`。2.文件夹里面的文件全部拷入到`X:\xxx\Cadence\SPB_Data\pcbenv`目录下面。3.重启Allegro后,即可看到菜单栏新增了`BatchConversion`。4.点击Batc......