Codeforces Round 967 (Div. 2) D. Longest Max Min Subsequence

假设我们要选a[j]为答案数组b[i],从i从1~m(m为a数组中不同数的个数)

建立一个suf数组,代表以i开头的后缀有多少个不同且在b[1~i-1]中未出现过的的个数,预处理suf,发现后续我们怎么选数改变suf,suf都始终单调不递增,我们选择的j位置满足suf[j]>=m-i+1。那么枚举b的每个位置,二分每个位置找出j的范围即可。在这个范围内我们奇数选最大,偶数选最小。难点在于

1.每选择一个数,suf如何改变。选择的这个数的最后一个位置之前的所有的suf-1,这个我们用线段树模拟每个位置减去的数,二分时减去这个值即可。

2.数不能选重复。每选定一个数,把这个数出现的所有位置包含的线段树的点的最大值改为最小,最小值改为最大,保证不可能再选。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=3e5+10;
int T,n,m,a[N],suf[N],wz[N];
struct node{int l,r,val,jian,maxx,max_pos,minn,min_pos;
}t[N*4];
struct nod{int zb,qz;
};
void init()
{
}
void build(int p,int l,int r)
{t[p].l=l,t[p].r=r;t[p].jian=0;if(l==r){t[p].val=suf[l];t[p].maxx=t[p].minn=a[l];t[p].max_pos=t[p].min_pos=l;return ;}int mid=(l+r)/2;build(p*2,l,mid);build(p*2+1,mid+1,r);if(t[p*2].maxx>=t[p*2+1].maxx){t[p].maxx=t[p*2].maxx;t[p].max_pos=t[p*2].max_pos;}else{t[p].maxx=t[p*2+1].maxx;t[p].max_pos=t[p*2+1].max_pos;}if(t[p*2].minn<=t[p*2+1].minn){t[p].minn=t[p*2].minn;t[p].min_pos=t[p*2].min_pos;}else{t[p].minn=t[p*2+1].minn;t[p].min_pos=t[p*2+1].min_pos;}
}
int ask(int p,int x)
{if(t[p].l==t[p].r) return t[p].jian;int mid=(t[p].l+t[p].r)/2;if(x<=mid) return t[p].jian+ask(p*2,x);else return t[p].jian+ask(p*2+1,x);
}
void change(int p,int l,int r)
{if(t[p].l>=l&&t[p].r<=r) {t[p].jian+=1; return ;}int mid=(t[p].l+t[p].r)/2;if(l<=mid) change(p*2,l,r);if(r>mid) change(p*2+1,l,r);
}
nod ask1(int p,int l,int r)
{nod tmp,tmp1;tmp.qz=0;if(t[p].l>=l&&t[p].r<=r){tmp.zb=t[p].max_pos;tmp.qz=t[p].maxx;return tmp;}int mid=(t[p].l+t[p].r)/2;if(l<=mid) tmp=ask1(p*2,l,r);if(r>mid){tmp1=ask1(p*2+1,l,r);if(tmp1.qz>tmp.qz) return tmp1;}return tmp;
}
nod ask2(int p,int l,int r)
{nod tmp,tmp1;tmp.qz=1e9;if(t[p].l>=l&&t[p].r<=r){tmp.zb=t[p].min_pos;tmp.qz=t[p].minn;return tmp;}int mid=(t[p].l+t[p].r)/2;if(l<=mid) tmp=ask2(p*2,l,r);if(r>mid){tmp1=ask2(p*2+1,l,r);if(tmp1.qz<tmp.qz) return tmp1;}return tmp;
}
void change1(int p,int k)
{if(t[p].l==t[p].r) {t[p].maxx=0; t[p].minn=1e9; return ;}int mid=(t[p].l+t[p].r)/2;if(k<=mid) change1(p*2,k);else change1(p*2+1,k);if(t[p*2].maxx>=t[p*2+1].maxx){t[p].maxx=t[p*2].maxx;t[p].max_pos=t[p*2].max_pos;}else{t[p].maxx=t[p*2+1].maxx;t[p].max_pos=t[p*2+1].max_pos;}if(t[p*2].minn<=t[p*2+1].minn){t[p].minn=t[p*2].minn;t[p].min_pos=t[p*2].min_pos;}else{t[p].minn=t[p*2+1].minn;t[p].min_pos=t[p*2+1].min_pos;}
}
void solve()
{cin>>n;init();vector<int> c[n+2];for(int i=1;i<=n;i++){cin>>a[i];c[a[i]].emplace_back(i);}suf[n+1]=a[n+1]=0;map<int,int> b;for(int i=n;i>=1;i--){suf[i]=suf[i+1];if(!b[a[i]]){b[a[i]]=1;suf[i]++;wz[a[i]]=i;}}m=suf[1];build(1,1,n+1);vector<int> ans;int last=0;for(int i=1;i<=m;i++){int l=1,r=n+1,pos;while(l<=r){int mid=(l+r)/2;if(suf[mid]-ask(1,mid)<m-i+1) {pos=mid; r=mid-1;}else l=mid+1;}pos--;int poss;if(i&1) poss=ask1(1,last+1,pos).zb;else poss=ask2(1,last+1,pos).zb;ans.emplace_back(a[poss]);change(1,1,wz[a[poss]]);last=poss;for(int j:c[a[poss]])change1(1,j);}cout<<ans.size()<<endl;for(auto i : ans)cout<<i<<" ";cout<<endl;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie();cin>>T;while(T--) solve();
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/92706.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/92706.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux运维新手的修炼手扎之第27天

mysql服务1 主从复制集群&#xff1a;多主机集群【复制】负载过大解决方案&#xff1a;横向扩展[增加服务器节点分散负载]、纵向扩展[提升单机硬件性能]复制工作原理&#xff1a;前提&#xff1a;基础数据一样&#xff0c;主节点上有同步数据用的账号主角色【二进制日志、binlo…

【Linux】Linux增删改查命令大全(附频率评级)

Linux增删改查命令大全&#xff08;附频率评级&#xff09;* 《Linux命令全景手册&#xff1a;增删改查全场景解析&#xff08;含136个高频命令&#xff09;》 按使用频率★分级 | 测试/运维/开发均适用 | 附思维导图下载一、命令全景表&#xff08;增删改查频率评级&#xff0…

SwiftUI 登录页面键盘约束冲突与卡顿优化全攻略

网罗开发&#xff08;小红书、快手、视频号同名&#xff09;大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等方…

建筑物实例分割数据集-9,700 张图片 城市规划与发展 灾害评估与应急响应 房地产市场分析 智慧城市管理 地理信息系统(GIS) 环境影响评估

建筑物实例分割数据集-9,700 张图片&#x1f4e6; 已发布目标检测数据集合集&#xff08;持续更新&#xff09;&#x1f3e2; 建筑物实例分割数据集介绍&#x1f4cc; 数据集概览包含类别&#x1f3af; 应用场景&#x1f5bc; 数据样本展示使用建议&#x1f31f; 数据集特色&am…

LeetCode 刷题【36. 有效的数独】

36. 有效的数独 自己做 解&#xff1a;多层for class Solution { public:bool isValidSudoku(vector<vector<char>>& board) {int hight board.size(); //长if (hight 0)return true;int wide board[0].size(); //宽//判断一行是否出现重复bool…

Java 日志从入门到精通:告别日志混乱

作为一名 Java 开发者&#xff0c;你是否曾在生产环境故障排查时面对过这样的困境&#xff1a;系统报错却找不到关键日志&#xff0c;日志文件大到无法打开&#xff0c;或者日志内容杂乱无章根本无法定位问题&#xff1f;日志作为系统运行的 “黑匣子”&#xff0c;其重要性不言…

系统开发 Day1

前端开发 目的&#xff1a; 开发一个平台&#xff08;网站&#xff09; - 前端开发&#xff1a;HTML CSS JavaScript - web框架&#xff1a;接受请求和处理 - MySQL数据库&#xff1a;存储数据的地方快速上手&#xff1a;基于Flask Web框架快速搭建一个网站 深度学习&#xff…

机器视觉任务(目标检测、实例分割、姿态估计、多目标跟踪、单目标跟踪、图像分类、单目深度估计)常用算法及公开数据集分享

本文按目标检测、实例分割、姿态估计、多目标跟踪、单目标跟踪、图像分类、单目深度估计七个任务分类&#xff0c;融合数据集介绍、评价指标及推荐算法&#xff0c;方便查阅&#xff1a; 一、目标检测 目标检测任务需定位图像中目标的边界框&#xff08;bounding box&#xff0…

MongoTemplate中setOnInsert与set方法的深度解析

MongoTemplate中setOnInsert与set方法的深度解析 在Spring Data MongoDB的MongoTemplate中&#xff0c;setOnInsert和set方法都是在更新文档时使用的&#xff0c;但它们在处理upsert操作&#xff08;即&#xff0c;如果文档不存在则插入&#xff0c;存在则更新&#xff09;时扮…

利用OJ判题的多语言优雅解耦方法深入体会模板方法模式、策略模式、工厂模式的妙用

在线评测系统&#xff08;Online Judge, OJ&#xff09;的核心是判题引擎&#xff0c;其关键挑战在于如何高效、安全且可扩展地支持多种编程语言。在博主的项目练习过程中&#xff0c;借鉴了相关设计模式实现一种架构设计方案&#xff0c;即通过组合运用模板方法、策略、工厂等…

[FOC电机控制]霍尔传感器于角度问题

如果电机有1对极(p1&#xff0c;那么每旋转一圈的机械角度&#xff0c;电气角度会转动一圈&#xff08;360&#xff09;。如果电机有2对极(p2&#xff0c;那么每旋转一圈的机械角度&#xff0c;电气角度会转动两圈&#xff08;720&#xff09;。

阿里云 Flink

阿里云 Flink 是阿里云基于Apache Flink打造的企业级实时计算平台&#xff0c;旨在为用户提供高效、稳定、易用的流处理与批处理能力&#xff0c;帮助企业快速构建实时数据处理链路&#xff0c;支撑实时业务决策。核心特性流批一体计算继承 Apache Flink “流批一体” 的核心优…

企业级高性能web服务器

1 web服务基础 1.1 正常情况的单次web服务访问流程&#xff1a; 正常情况下&#xff0c;单次 Web 服务访问流程从用户在客户端发起请求开始&#xff0c;到最终在客户端展示内容结束&#xff0c;涉及客户端、网络传输、服务器端等多个环节&#xff0c;以下是详细过程&#xff…

免费PDF编辑软件 pdf24-creator 及其安装包

最近发现了一款还算是不错的PDF编辑和阅读软件 pdf24-creator&#xff0c;官方下载网站为&#xff1a;https://tools.pdf24.org/zh/creator&#xff0c;但是官方下载如果没有魔法的话&#xff0c;下载速度很慢&#xff0c;比百度网盘下载还满&#xff0c;因此我把它分享到网盘。…

openvela之ADB

ADB&#xff08;Android Debug Bridge&#xff09;是一款功能丰富的命令行工具&#xff0c;旨在实现开发工作站与设备&#xff08;如模拟器、实体设备&#xff09;之间的通信。通过 ADB&#xff0c;开发者可以便捷地在设备上执行命令、传输文件、调试应用等。本文将详细介绍 AD…

如何控制需求交付节奏

有效控制需求的交付节奏&#xff0c;其核心在于将产品开发过程从一个不可预测的、时快时慢的混乱状态&#xff0c;转变为一套产出稳定、流程顺畅、步调可持续的系统化交付机制。要成功构建这套机制&#xff0c;实现有节奏的价值交付&#xff0c;必须综合运用五大关键策略&#…

汇编中常用寄存器介绍

X86-32位寄存器 4个数据寄存器&#xff1a;EAX、EBX、ECX和EDX; 2个变址和指针寄存器&#xff1a;ESI和EDI; 2个指针寄存器&#xff1a;ESP和EBP; 1个指令指针寄存器&#xff1a;EIP; 6个段寄存器&#xff1a;ES、CS、SS、DS、FS和GS; 1个标志寄存器&#xff1a;EFlags。 在X8…

SOMGAN:用自组织映射改善GAN的模式探索能力

论文信息 论文题目:Improving mode exploring capability ofgenerative adversarial nets by self-organizing map(利用自组织映射提高生成对抗网络的模式探索能力) 期刊:Neurocomputing 摘要:生成对抗网络(GANs)的出现将生成模型的研究推向了一个新的高潮。支持这一进步…

《汇编语言:基于X86处理器》第12章 复习题和练习

本篇记录了《汇编语言&#xff1a;基于X86处理器》第12章 复习题和练习的笔记。12.6复习题和练习12.6.1 简答题1.假设有二进制浮点数1101.01101&#xff0c;如何将其表示为十进制分数之和?答&#xff1a;1101.01101(1x)(1x)(0x)(1x)(0x)(1x)(1x)(1x)(1x) 13.406252.为什么十进…

ApacheCon Asia 2025 中国开源年度报告:Apache Doris 国内第一

上周刚落下帷幕的 ApacheCon Asia 2025 中&#xff0c;一个数据让所有人都为之震撼&#xff1a;全球 Apache 基金会项目 OpenRank 排行榜中&#xff0c;Apache Doris 位居第二&#xff0c;在中国 Apache 项目中更是稳居第一。 这个排名意味着什么&#xff1f;在 Apache 基金会管…