Mex 构造题 (P6852 )
给出一些限制,需要还原一个排列,限制形如:[L,R]
v
,表示排列
[L,R]
的Mex 为
v。
给出任意一种构造方案.
∣P∣≤105
## 分析
分析 Mex 值为
v
的限制,能够提供两种信息,一种是这段区间中
1~v−1
全部存在,一种是不存在
v
考虑一个数字
x
的存在位置有哪些限制,不难发现,所有
v≥x
的限制都会对这个值得位置产生限制。
其实就是所有
v≥x
的限制的交集。区间并不好维护,区间交要好维护的多。
从下到大确定
x
的位置,可以发现可选区间单增,可以直接填数,能保证最优。
注意 Mex 的第二条限制,可以考虑用线段树或者 set
维护哪些地方没有被占用。
🔗 Source Hash:
cd0335b18b194a0c8b26917fc8002d25916234fe72491f9ae27db52a007aa665
Build Logs
Build Log - Filtered
================================================
📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes
• All build status and error messages are kept intact
🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]
================================================
html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「杂题记录」Mex.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「杂题记录」Mex.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT:
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.
====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../54f6dcc2d0.pdf.md', '-o', 'cache/54f6dcc2d0.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT:
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawInline (Format "html") ""
[INFO] [makePDF] Temp dir:
.../[temp]
[INFO] [makePDF] Command line:
xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
("TEXINPUTS",".../[temp]
("TEXMFOUTPUT",".../[temp]
("SHELL","/bin/bash")
("PWD",".../[user]/projects/blog")
("HOME",".../[user]
("LANG","zh_CN.UTF-8")
("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
\PassOptionsToPackage{space}{xeCJK}
\documentclass[
]{article}
\usepackage{xcolor}
\usepackage[a4paper,margin=2cm]{geometry}
\usepackage{amsmath,amssymb}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\usepackage{iftex}
\ifPDFTeX
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
\usepackage{unicode-math} % this also loads fontspec
\defaultfontfeatures{Scale=MatchLowercase}
\defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
\usepackage{lmodern}
\ifPDFTeX\else
% xetex/luatex font selection
\setmainfont[]{Latin Modern Roman}
\ifXeTeX
\usepackage{xeCJK}
\setCJKmainfont[]{AR PL UKai CN}
\fi
\ifLuaTeX
\usepackage[]{luatexja-fontspec}
\setmainjfont[]{AR PL UKai CN}
\fi
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{setspace}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
\KOMAoptions{parskip=half}}
\makeatother
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
% \usepackage{xeCJK}
% \setCJKmainfont{AR PL UKai CN}
% \usepackage{unicode-math}
\setmathfont{Latin Modern Math}
\usepackage{bookmark}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same}
\hypersetup{
pdftitle={「杂题记录」Mex},
pdfauthor={Jiayi Su (ShuYuMo)},
hidelinks,
pdfcreator={LaTeX via pandoc}}
\title{「杂题记录」Mex}
\author{Jiayi Su (ShuYuMo)}
\date{2021-01-19 15:35:06}
\begin{document}
\maketitle
\setstretch{1.3}
Mex 构造题 (P6852 )
给出一些限制,需要还原一个排列,限制形如:\([L, R]\) \(v\) ,表示排列
\([L, R]\) 的Mex 为 \(v\)。 给出任意一种构造方案. \(|P|\le 10^5\) \#\#
分析
分析 Mex 值为 \(v\) 的限制,能够提供两种信息,一种是这段区间中
\(1\)\textasciitilde{}\(v - 1\) 全部存在,一种是不存在 \(v\)
考虑一个数字 \(x\) 的存在位置有哪些限制,不难发现,所有 \(v\ge x\)
的限制都会对这个值得位置产生限制。
其实就是所有 \(v\ge x\)
的限制的交集。区间并不好维护,区间交要好维护的多。
从下到大确定 \(x\)
的位置,可以发现可选区间单增,可以直接填数,能保证最优。
注意 Mex 的第二条限制,可以考虑用线段树或者 set 维护哪些地方没有被占用。
\end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
restricted \write18 enabled.
entering extended mode
(.../input.tex
LaTeX2e <2023-11-01> patch level 1
L3 programming layer <2024-01-22>
(.../article.cls
Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
(.../[system]
(.../xcolor.sty
(.../color.cfg)
(.../xetex.def)
(.../[system]
(.../geometry.sty
(.../keyval.sty)
(.../ifvtex.sty
(.../iftex.sty)))
(.../amsmath.sty
For additional information on amsmath, use the `?' option.
(.../amstext.sty
(.../amsgen.sty))
(.../amsbsy.sty)
(.../amsopn.sty))
(.../amssymb.sty
(.../amsfonts.sty))
(.../unicode-math.sty
(.../expl3.sty
(.../l3backend-xetex.def))
(.../unicode-math-xetex.sty
(.../xparse.sty)
(.../l3keys2e.sty)
(.../fontspec.sty
(.../fontspec-xetex.sty
(.../fontenc.sty)
(.../fontspec.cfg)))
(.../fix-cm.sty
(.../ts1enc.def))
(.../unicode-math-table.tex)))
(.../lmodern.sty)
(.../xeCJK.sty
(.../ctexhook.sty)
(.../xtemplate.sty)
(.../xeCJK.cfg))
(.../upquote.sty
(.../textcomp.sty))
(.../microtype.sty
(.../etoolbox.sty)
(.../microtype-xetex.def)
(.../microtype.cfg))
(.../setspace.sty)
(.../parskip.sty
(.../kvoptions.sty
(.../ltxcmds.sty)
(.../kvsetkeys.sty)))
(.../bookmark.sty
(.../hyperref.sty
(.../kvdefinekeys.sty)
(.../pdfescape.sty
(.../pdftexcmds.sty
(.../infwarerr.sty)))
(.../hycolor.sty)
(.../auxhook.sty)
(.../nameref.sty
(.../refcount.sty)
(.../gettitlestring.sty))
(.../pd1enc.def)
(.../intcalc.sty)
(.../puenc.def)
(.../url.sty)
(.../bitset.sty
(.../bigintcalc.sty))
(.../atbegshi-ltx.sty))
(.../hxetex.def
(.../stringenc.sty)
(.../rerunfilecheck.sty
(.../atveryend-ltx.sty)
(.../uniquecounter.sty)))
(.../bkm-dvipdfm.def))
(.../xurl.sty)
No file input.aux.
*geometry* driver: auto-detecting
*geometry* detected driver: xetex
(.../mt-LatinModernRoman.cfg)
Package hyperref Warning: Rerun to get /PageLabels entry.
(.../omllmm.fd)
(.../umsa.fd)
(.../mt-msa.cfg)
(.../umsb.fd)
(.../mt-msb.cfg) [1]
(.../input.aux) )
Output written on .../input.pdf (1 page).
Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
Package hyperref Warning: Rerun to get /PageLabels entry.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
restricted \write18 enabled.
entering extended mode
(.../input.tex
LaTeX2e <2023-11-01> patch level 1
L3 programming layer <2024-01-22>
(.../article.cls
Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
(.../[system]
(.../xcolor.sty
(.../color.cfg)
(.../xetex.def)
(.../[system]
(.../geometry.sty
(.../keyval.sty)
(.../ifvtex.sty
(.../iftex.sty)))
(.../amsmath.sty
For additional information on amsmath, use the `?' option.
(.../amstext.sty
(.../amsgen.sty))
(.../amsbsy.sty)
(.../amsopn.sty))
(.../amssymb.sty
(.../amsfonts.sty))
(.../unicode-math.sty
(.../expl3.sty
(.../l3backend-xetex.def))
(.../unicode-math-xetex.sty
(.../xparse.sty)
(.../l3keys2e.sty)
(.../fontspec.sty
(.../fontspec-xetex.sty
(.../fontenc.sty)
(.../fontspec.cfg)))
(.../fix-cm.sty
(.../ts1enc.def))
(.../unicode-math-table.tex)))
(.../lmodern.sty)
(.../xeCJK.sty
(.../ctexhook.sty)
(.../xtemplate.sty)
(.../xeCJK.cfg))
(.../upquote.sty
(.../textcomp.sty))
(.../microtype.sty
(.../etoolbox.sty)
(.../microtype-xetex.def)
(.../microtype.cfg))
(.../setspace.sty)
(.../parskip.sty
(.../kvoptions.sty
(.../ltxcmds.sty)
(.../kvsetkeys.sty)))
(.../bookmark.sty
(.../hyperref.sty
(.../kvdefinekeys.sty)
(.../pdfescape.sty
(.../pdftexcmds.sty
(.../infwarerr.sty)))
(.../hycolor.sty)
(.../auxhook.sty)
(.../nameref.sty
(.../refcount.sty)
(.../gettitlestring.sty))
(.../pd1enc.def)
(.../intcalc.sty)
(.../puenc.def)
(.../url.sty)
(.../bitset.sty
(.../bigintcalc.sty))
(.../atbegshi-ltx.sty))
(.../hxetex.def
(.../stringenc.sty)
(.../rerunfilecheck.sty
(.../atveryend-ltx.sty)
(.../uniquecounter.sty)))
(.../bkm-dvipdfm.def))
(.../xurl.sty)
(.../input.aux)
*geometry* driver: auto-detecting
*geometry* detected driver: xetex
(.../mt-LatinModernRoman.cfg)
(.../omllmm.fd)
(.../umsa.fd)
(.../mt-msa.cfg)
(.../umsb.fd)
(.../mt-msb.cfg) [1]
(.../input.aux) )
Output written on .../input.pdf (1 page).
Transcript written on .../input.log.