场上把时间都花在 C 题上了，其实 D 比 C 简单，就是一个贪心。 首先 $a_1$ 未确定是平凡的，把所有未确定的数都填为 $1$ 一定最优。$a_1=1$ 同理。 贪心，从前往后依次考虑每一位。我们称 $a_i$ 为 $i$ 指向的位置。分类讨论： 1. 第 $i$ 位还未确定：我们希望第 $i$ 位指向的位置填…

线段树优化建图太老套了，这里提供一个 ST 表优化建图。 开四个 ST 表，表示这个区间内的所有点到达区间的左/右端点、区间的左/右端点到达这个区间内的所有点。每个列车只需连 $O(1)$ 条边。 点数为 $O(n\log n)$，边数为 $O(n\log n+m)$，常数略大，但是能做 $m=10^6$，代码也很好写…

## 题目大意 给定 $n \times n$ 的矩阵 $A$，其中每行每列都是 $1,...,n$ 的排列，且每个位置有一个权值 $c_{i,j}\in \{0,1\}$。你需要选择恰好 $n$ 个位置，使得每行每列恰有一个位置被选择，且所有没被选的位置要么比同行同列被选择的位置都大，要么比同行同列被选择的位置都小。…

不考虑容斥，从上往下扫描线。 将所有点按照横坐标排序，从大到小加入每个点，每次只统计下边界横坐标在 $[x_{i-1},x_i)$ 的所有正方形，考虑其上边界所在的位置。 先将加入的所有点按 $y$ 排序（可以插入排序）。画图发现有两种情况： 1. 对一个点 $(x_i,y_i)$，单调栈求出每个点左边第一个 $x #…

## 题目大意 有 $n$ 个桶，每个桶中有 $a_i$ 千克水，其中恰有一个桶装有 $0.179$ 千克毒药。你可以进行以下两种操作任意次： 1. 选择两个桶比较，返回哪个更重或一样重； 2. 从桶 $A$ 向桶 $B$ 中倒任意多的水，要求 $A$ 确定不含毒药。 $q$ 次修改，加入或删除一个重量为 $x$ 的桶…

## 题目大意： 给定一个长为 $n$ 的数组 $c$，维护一个长为 $n$ 的数组 $a$，起初全为 $0$。有 $q$ 次区间加操作，若操作后 $a_i c_i$ 则 $a_i \gets c_i$。求所有操作后 $a$ 数组的值。 ## 思路： 使用**换维扫描线**的技巧，对序列扫描线，维护操作序列。则题目转化…

感觉思路都对，实在找不出错误了 WA #29#36#37 ```cpp #include #include #include #define N 100005 #define INF 0x3f3f3f3f3f3f3f3f #define LL long long using namespace std; int n,m…