CF1887C Minimum Array

题目链接：https://codeforces.com/problemset/problem/1887/C

题意：

给定一个长度为 \(n\) 的整数序列，共 \(q\) 此操作，每次操作会将序列的一段区间同时加上某个数，求出所有操作产生的新序列中字典序最小的一个。

思路：

由区间加想到差分，要求序列字典序最小及要求其差分数组字典序最小。设当前答案为差分数组 \(dans\)，其为第 \(p\) 次操作之后的差分数组，从第 \(p+1\) 此操作到当前操作的修改数组为 \(d\)（即当前差分数组为 \(a_i=dans_i+d_i\)），可以发现若 \(d\) 中的第一个不为 \(0\) 的数小于 \(0\)，那么字典序就会变小。由于每一次修改只会修改 \(d\) 中的 \(l\) 和 \(r+1\)，那么只需要用 \(set\) 维护这些修改的下标，即可 \(O(\log n)\) 查询第一个不为 \(0\) 的数即可。

代码：

https://codeforces.com/contest/1887/submission/274521362

反思：

看到区间加要想到差分（或线段树）。如果要求多次操作后的结果的最值，那么可以考虑每一次操作在满足什么条件下结果会变大或变小。