The 2020 ICPC Asia Macau Regional Contest J.Jewel Grab 线段树+双向链表模拟

思路

对于每个位置的宝石，分别维护 p r e [ i ] pre[i] pre[i](同色前一宝石所在位置)和 n x t [ i ] nxt[i] nxt[i](同色后一宝石所在位置)。 注意到 k k k很小，那么对于每次询问，我们可以从开始点往后找，查询当前点是否有同色点位于前面且位于 [ s , n ] [s,n] [s,n]内，有的话比较大小，决定是否跳过。 对于区间单点维护操作，我们需要对 p r e pre pre和 n x t nxt nxt进行更新，更新的过程类似于单链表，每个颜色单独构成一条链：

1. 删除原有元素(讨论：元素位于序列头部、尾部、中间)。
2. 添加新元素(讨论头插、尾插、中插) 为了更快的查找插入元素的位置，我们可以对每个颜色维护一个std::set，然后通过二分查找找位置插入。

对于查询操作和求和操作，显然可以使用线段树进行加速。我们对宝石的值维护一个区间和线段树，对每个点的 p r e pre pre节点维护一个区间最大值线段树，当最大值为 − 1 -1 −1时就表示区间内无重复颜色。如果查询到一段区间无重复颜色，显然可以直接选择整个区间。对于有重复颜色的区间，我们在线段树上二分查找有重复颜色节点的下一节点，并根据值的大小决定是否进行更新即可。

#include 
#define int long long

const int N = 2e5 + 10;

int c[N], v[N];
int pre[N], nxt[N], last[N], his[N];

namespace SegmentTree{
    int tree[N