#CW42. 排列检查(check)
排列检查(check)
题目背景
小 W 正在检查一批由小 Z 生成的排列。为了让检查结果稳定可复核,他使用一个固定的单调栈过程,并把所有询问的答案压缩成一个数。
题目描述
给定一个长度为 的排列 。维护一个初始为空的递增单调栈 和计数器 。依次处理 :
- 若 为空,或栈顶小于 ,将 压入栈中;
- 否则弹出栈顶,并令 加一,然后继续检查当前的 。
定义排列的逆序对数 为 。
若处理结束时 等于 ,则称这个排列是合格的。
输入不会直接给出 。每个询问给出差分序列:规定 ,输入的第 个数是 。保证还原出的 是 的排列。
输入格式
第一行一个正整数 ,表示询问个数。
接下来 行描述询问。每行先给出一个正整数 ,随后给出 个整数 ,其中 ,且 。
对于全部数据,保证 ,,所有询问的 之和不超过本题所在子任务给出的限制;还原出的序列是 的排列,并且 。
输出格式
若第 个排列合格,记 ;否则记 。输出
$$\left(\sum_{i=1}^{t} 131^i \cdot ans_i\right) \bmod 993244853\text{。}$$样例 1 输入
2
3 1 1 1
3 1 2 -1
样例 1 输出
140020951
样例 1 解释
两组差分分别还原为排列 和 。前者没有逆序对,单调栈弹出次数为 ;后者有一个逆序对,单调栈恰好弹出一次,因此两组排列都合格。代入题目中的压缩公式得到 。
样例 2 输入
2
3 3 -2 1
3 3 -2 1
样例 2 输出
234808068
样例 3 输入
2
3 1 1 1
3 3 -2 1
样例 3 输出
241614566
样例 4 输入
2
3 3 -2 1
3 1 1 1
样例 4 输出
133214453
样例 5 输入
1
3 1 1 1
样例 5 输出
8585347
子任务
本题采用子任务捆绑计分。一个子任务中的所有测试点全部通过后,才能获得该子任务的分值;各子任务之间相互独立。
| 子任务 | 测试点 | 额外限制 | 分值 |
|---|---|---|---|
| 1 | 所有询问满足 ,且 | 10 | |
| 2 | 所有询问满足 ,且 | 15 | |
| 3 | 所有询问满足 ,且 | 20 | |
| 4 | 所有询问满足 ,且 | 25 | |
| 5 | 无额外限制, | 30 |
数据范围
除特别说明外,所有数据满足 、、,并且还原出的 是 的排列。所有测试点中 。