Almost Sorted

注意到 $d\leq 5$ ，考虑装态压缩。

由于第 i 个数只与 $[i-d,i+d]$ 有关，所以只用记录 2¹¹ 个状态，剩下的一定不会改变。

すぬけ君の地下鉄旅行

考虑如何优化建图。

首先，对于颜色相同的连通块可以建立一个虚点，让 $(i,col)$ ,即 i 的 col 颜色连向虚点，可以保证点数的数量级为 n+m。

建图时可能要建立多个虚点，用并查集维护。

rep(k,1,1000000)
{
    vector<int> use; mp=CT;
    for(auto [i,j]:same[k])
    {
        fa[find(i)]=find(j);
        use.emplace_back(i),use.emplace_back(j);
    } sort(use.begin(),use.end()),use.erase(unique(use.begin(),use.end()),use.end());
    for(int i:use) if(i==find(i)) mp[i]=++idx;
    for(auto [i,j]:same[k])
    {
        g[mp[find(i)]].emplace_back((pair<int,int>){i,1});
        g[i].emplace_back((pair<int,int>){mp[find(i)],1});
        g[mp[find(j)]].emplace_back((pair<int,int>){j,1});
        g[j].emplace_back((pair<int,int>){mp[find(j)],1});
    }
    for(int i:use) fa[i]=i;
}

Finding a MEX

如果想到了分块，这题就做完了。

把 $度数\geq \sqrt n$ 的点用树状数组维护，剩下的直接遍历查找中位数。

时间复杂度为 $q \sqrt n log_n$ ，但可以过 $(\; 5 \times {10}^{8} \; )$ 。

Binomial coefficients

首先有 $C_{60}^{30} \; = \; 118264581564861424 \geq 10^{15}$ 。

所以答案里的 $min$ { k,n-k } $\leq 30$ 。

枚举 $k,n-k$ , 此时的答案具有单调性。

二分即可。

Showstopper

这题是二分。

我们先把偶数看作0，奇数看作1。

首先，我们要找的这个数并不能二分。因为它大概长这样：

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \dots\dots 010 \dots \dots$

但如果我们做一个前缀和，就变成了这样：

$\;\;\;\;\;\;\;\;\;\;\;\;\; \dots\dots 0000111111 \dots \dots$

此时就具备了单调性。

二分 $check$ 当前 $\leq x$ 的数量奇偶性即可。

最后

提交地址：

https://vjudge.net.cn/contest/615804

密码：

lhf's-goot-problem