题解：P12736 [POI 2016 R2] 圣诞灯链 Christmas chain

· · 题解

不用动脑子的简单数据结构做法，思考十分钟代码四十分钟就一发过了。但是时间复杂度稍劣。

题目的条件可以被拆成若干个两个位置相等的条件，暴力拆出来大概是 \mathcal{O}(nm) 的，难以接受。考虑并查集维护的过程，你实际是在维护连通性，其有效合并其实只有 \mathcal{O}(n) 次，暴力做法把多数时间花在了找可以合并的位置上，十分不优。以下称位置/数的颜色是其所属集合。

于是我们有一个基本的 idea：我们要让每次合并的尝试都是有效的，即要保证合并的两个位置的颜色不同。

我们维护位置的颜色序列。操作范围是区间，这就很简单，使用哈希就可以简单二分出两个区间第一个颜色不同的位置。使用树状数组可以简单维护修改和查询。每次找合并的位置，时间是 \mathcal{O}(\log^2{n}) 的。

但是你遇到一个问题：你的区间哈希需要有即时性，也就是你每次合并完集合之后需要把修改的颜色同步回序列上。使用启发式合并即可——启发式合并可以让“修改某个位置的颜色”的操作次数做到 \mathcal{O}(n\log{n})。使用上文的树状数组支持修改哈希即可。

最终时间复杂度是 \mathcal{O}(n\log^2{n}) 的，常数很小，而且数据貌似没把它卡满，比某些写法稍劣的倍增做法跑得快很多。值得注意的是，尽管这道题没有卡单哈希，我仍然建议使用双哈希，代码如下：

// 注意他开了 4.5s 1G.
// 该思路使用 10min 完成思考。 40min coding.
// 不知道能不能过啊 而且我也不知道 hash 这个问题误报概率有多大。可能写得差不多了得加个双 hash
// feed back: 竟然过了！最慢点跑了 780ms 左右，也是独立切上紫题了。看看加个快读什么的跑得有多快吧。
// 这个空间不像是卡满的样子啊，不过想必确实有点难卡满吧。
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef long long LL;

const int N=5e5+10;
const int bas=131,mod=998244353;

inline int& addmod(int &x){ return x>=mod?x-=mod:x; }
inline int Mod(int x){return x>=mod?x-mod:x;}
struct IO{
    char buf[1<<21],*p1,*p2;
    #define gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    inline int read(){
        register int x=0;
        register char c=gc();
        while(c<'0' || c>'9')   c=gc();
        while(c<='9' && c>='0') x=(x<<3)+(x<<1)+c-'0',c=gc();
        return x;
    }
}io;

int n,m,pw[N];
struct BIT{
    int t[N];
    #define lowbit(x) (x&(-x))

    inline void update(int x,int v){
        v=1ll*v*pw[x]%mod;
        for(int i=x;i<=n;i+=lowbit(i))
            addmod(t[i]+=v);
    }
    inline int query(int x){
        int ret=0;
        for(int i=x;i;i-=lowbit(i))
            addmod(ret+=t[i]);
        return ret;
    }
    inline int qrange(int l,int r){
        return Mod(query(r)+mod-query(l-1));
    }
}hsh;
inline bool comp(int l1,int r1,int l2,int r2){
    return 1ll*hsh.qrange(l1,r1)*pw[l2-l1]%mod==hsh.qrange(l2,r2);
}
struct DSU{ // 直接启发式合并
    int bel[N],tab[N];
    vector<int> e[N];
    inline void chg(int u,int fr){
        hsh.update(u,Mod(fr+mod-bel[u]));
        e[bel[u]=fr].push_back(u);
    }
    inline void init(){ for(int i=1;i<=n;i++) chg(i,i); }
    inline void merge(int u,int v){
        assert(bel[u]!=bel[v]); // 应该是不会有问题。
        if(bel[u]!=bel[v]){ // 这个地方写法其实有很多，所以 hash 还是很难卡的。
            u=bel[u],v=bel[v];
            if(e[u].size()<e[v].size())
                swap(u,v);
            for(int i:e[v])
                chg(i,u);
        }
    }
    inline int count(){
        int ans=0;
        for(int i=1;i<=n;i++)
            if(!(tab[bel[i]]++))
                ++ans;
        return ans;
    }
}dsu;
void init(){
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=1ll*bas*pw[i-1]%mod;
    dsu.init();
}
inline void update(int a,int b,int k){
    while(!comp(a,a+k-1,b,b+k-1)){
        int l=0,r=k-1,mid;
        while(l<r){
            mid=(l+r)>>1;
            if(!comp(a,a+mid,b,b+mid))
                r=mid;
            else
                l=mid+1;
        }
        dsu.merge(a+l,b+l);
    }
}
int main(){
    n=io.read(),m=io.read(),init();
    for(int i=1,a,b,k;i<=m;i++){
        a=io.read(),b=io.read(),k=io.read();
        if(a>b) swap(a,b);
        update(a,b,k);
    }
    printf("%d\n",dsu.count());
    return 0;
}