OIFC20241102

考试总结

吃到屎了属于是

有价值的trick收获：随机权哈希，利用差分维护哈希值

T1 集合

假设 $S_i$ 表示能覆盖 $i$ 的集合的下标集合，当且仅当 $\forall j\neq i,$ 都有 $S_i\neq S_j$ 的时候， $\{i\}$ 可以搞出

证明大概就是，假如条件不成立，则生成集合中 $i,j$ 要么都在要么都不在，不可能生成 $\{i\}$

否则将不包含 $i$ 的 $S$ 取补集然后取交一定能生出 $\{i\}$

我们不妨考虑一下怎么统计答案，发现啊很难搞，复杂度很不行，基本上都是 $n^2$ 起步了，这题卡的有点狠毒只有小常数 $\log$ （map 是不行的）和线性做法放过去了

考虑一个哈希，最近看到好多哈希统计答案的题了，但是基本上都没想到过用到哈希这一步，哈希之前的部分都想不出，很难受只能说

我们希望我们给每个点 $i$ 赋值的哈希值要能够区间修改，因为我们输入的过程实际是给很多的小区间修改

我们大概的思路是，给每个集合（这里说的是题面里说的集合不是 $S_i$ 那个下标集合）赋予一个随机权值（不随机构造一下应该也可以吧但是会比较复杂）

然后让每个点的哈希值成为所有覆盖它的区间的权值通过一定方式复合而成，但是具体选什么运算是有待思考的：这个运算一定要有可减性因为我们希望快速修改又不希望过分增加复杂度，最好的选择是差分。可减性的常见选择是加法和乘法，乘法肯定是不好的，因为非常快就会爆数据范围，取模数然后就会需要逆元来实现可减性，反正是很麻烦而且很劣的一种做法。至于加法倒是可以，只是取模会有点麻烦。其实还有一个容易被忘记的好选择那就是————

我们考虑用异或。异或的性质真的其实是极好。我们利用差分快速修改最后做一次前缀和即可完成，答案的统计有两种考究方式，一种是按哈希值排序然后看左右有没有相等的元素，另一种是把随机权搞小一点然后用桶子来直接搞，前一种时间会比较紧张，后一种错误率会比较难受，可能会被卡的

然后这道题就做完了，复杂度我们选择排序那就是 $O(n\log n)$ 的样子，桶的话大概是线性的吧。但是实测桶会因为需要取模数被卡哈希冲突，用 unordered_map 会被卡常反而跑不过

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
mt19937_64 rd(time(0));
int hsh[5000005];
int C,T;
void work(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) hsh[i]=0;
    for(int i=1;i<=m;i++){
        int k;
        int val=rd();
        cin>>k;
        for(int j=1;j<=k;j++){
            int l,r;
            cin>>l>>r;
            hsh[r+1]^=val;
            hsh[l]^=val;
        }
    }
    for(int i=1;i<=n;i++) hsh[i]^=hsh[i-1];
    sort(hsh+1,hsh+n+1);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(i>1 and hsh[i-1]==hsh[i]) continue;
        if(i<n and hsh[i+1]==hsh[i]) continue;
        ans++;
    }
    cout<<ans<<"\n";
}
signed main(){
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>C>>T;
    while(T--) work();
}