小南量来了，大家快跑啊！！！！！！！！！！

D - Kontrwywiad

这个题很简单。

E - Dwukolorowe drzewo

这个题我不会。

F - Prognoza pogody

这个题把 \(p\) 串复制一遍，原问题就变成了找一个 \((i,j)\) 使得 \(\text{diff}(p_{[i,i+m-1]},t_{[j,j+m-1]})\) 最小。我们枚举一个 \((i',j')\)，一旦它们不同，那么 \((i,j)\) 的 \(\text{diff}\) 都会加一，其中 \(i=i'-d+1,j=j'-d+1,d\in[1,m]\)。直接前缀和就做完了。

我的笔漏墨了，我手上全部都是墨水。
我现在很生气。

小丑都会做的问题。

给定 \(n\) 个区间 \([l_i,r_i]\)，给定 \(Q\) 个询问 \([L_j,R_j]\)，每次询问编号在 \([L_j,R_j]\) 范围内的区间并集长度是多少。可以离线。

对于一个 \(x\) 来说，它被询问 \([L,R]\) 覆盖，当且仅当 \(g_R(x)\geq L\)。其中，\(g_R(x)\) 代表，只考虑编号 \(\leq R\) 的区间时，覆盖 \(x\) 的编号最大的区间编号是多少。可以扫描线，按编号从小到大加入区间，每次将 \([l_i,r_i]\) 覆盖成 \(i\)。查询就是查询线段树（显然要用线段树）上 \(\geq L\) 的位置有多少个。发现要用吉司机线段树。

我们尝试对于 \(L\) 也离线！！！使用数颜色段的方法。用 set 维护连续段和其出现的最后时间。