最近都是各种校内模拟赛，好久没写题解了。题意题解用线段树维护列，每个线段树记录这个区间内：最左边一列每个方块所属的集合最右边所属的集合四联通颜色块个数，即答案合并时对中间两列遍历所有行，如果两块颜色相同就用并查集把两个集合给合并起来，并将答案 $-1$ 。#include<bits/stdc++.h>
#define fi first
#define se second
#def...
题意挺简单的自己去看吧~题解因为有开闭两种区间，所以对每两个数中间也建一个点，总的点数即为 $2N$ 。维护一个长度为 $2N$ 的 $0/1$ 序列，支持区间覆盖，区间翻转操作。令 $T=[l,r]$ （$l,r$ 为新编的点）：U T：覆盖 $[l,r]$ 为 $1$I T：覆盖 $[0,l-1],[r+1,2N]$ 为 $0$D T：覆盖 $[l,r]$ 为 $0$C T：翻转整个区间...
题意有 $n(\le 5\times 10^5)$ 个区间，要从中选出 $m(\le 2\times 10^5)$ 个区间，要求存在一个点被覆盖了 $m$ 次，求最大区间长度与最小区间长度差值 的最小值。题解贪心，将所有区间按长度从小到大排序，答案一定是一段连续的区间。所以可以用线段树维护覆盖的次数，然后尺取法不断取被覆盖次数最大为 $m$ 的一段并更新答案。需要离散化预处理。需要注意区间长...
题意给出一个 $1..n(\le 10^5)$ 的全排列，有 $m(\le 10^5)$ 次操作，每次把 $[l,r]$ 中的数升序或降序排列。最后询问第 $q$ 个数是多少。题解只有最后一次询问，所以可以把操作离线处理。先考虑对一个 $0/1$ 串进行操作。升序排序就是把所有的 $1$ 挪到后面，降序就是挪到前面，可以用线段树解决。可以二分答案 $mid$ ，然后将 $< mid$ ...
这似乎是个很经典的题，但因为我很菜所以现在才做。显然，一个 $\le 10^{5}$ 的数最多经过 $6$ 次开方就一定可以变成 $1$ ，所以我们可以用线段树对每次询问进行单点修改，如果区间最大值 $\le 1$ 就不需要进行修改了。这样最多每个数修改 $6$ 次，查询直接区间查询，总时间复杂度是 $O(n\times \log n + 6n)$ 。struct Tree{
ll ...