题解 THUWC2025 Day1 T1 排列

cjh20090318 · 2025-01-14 20:59:38 · 题解

纪念我 Day1 场上唯一做出来的一道题。

题意

有 m 条限制，每条限制 l,r,o，区间 [l,r] 单调递增或递减，请构造出一组长度为 n 的排列满足尽可能多的限制。

数据范围 1 \le n,m \le 10^6。

时间限制 3s，空间限制 512MB。

分析

构造题，但是很传统。

你只需要确定每一个值和前面的大小关系就可以构造出一个合法排列。

上面这个东西是原题，FZUOJ#9481. 逆序对 inv，这个东西自己去看不赘述。

这个数据范围乍一看就很单调队列或者数据结构优化 DP。

接着难点就在于确定大小关系了，这个东西只需要 DP 转移记录一下上一个决策点就可以了。

对于每一个 l=r 的限制对构造方案没有任何影响可以直接忽略。剩下就是 l<r 的情况，对于递增和递减的条件分别开两个线段树区间加区间查即可。

时间复杂度 O(n \log n)，常数有点略大 pretest 跑了 1.2s，但是时限 3s 就不需要管了。