P3295

lsj2009 · 2023-11-07 01:30:02 · 题解

Solution

lxl 上课讲的做法，题解区里竟然没有/jy

我们考虑开一个并查集，将所有的 k\in [0,r1-l1] 将 l1+k 和 l2+k merge 在一起。

这样子直接做最差是 \Theta(nq) 的，显然过不去。

考虑优化。我们发现，复杂度浪费在了，有一些点本来已经是相同的了，但是我们又把他 merge 了一遍，所以浪费了大量时间。我们考虑对序列进行哈希，每次二分找到最近的不相同的节点，然后把他们 merge 起来，再把所有和他们位置相同的节点的哈希值改掉。

我们考虑使用线段树动态维护哈希值，并查集启发式合并，由于每个节点都只会被合并 \log 次，然后每次需要花费 \log 的代价更改哈希值，所以复杂度是 \Theta(q\log^2{n})。

这个做法比题解区里大部分做法要强的一点是可以支持在线时时询问和修改，但是常数太大，我的实现在吸氧情况下最慢点跑了 900ms。

Code

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e5+5,MOD=1e9+7;
const ull base=1145141;
ull p[N];
int fa[N],n,m;
vector<int> vec[N];
struct node {
    int l,r; ull val;
}; node tree[N<<2];
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
void push_up(int k) {
    tree[k].val=tree[ls(k)].val*p[tree[rs(k)].r-tree[rs(k)].l+1]+tree[rs(k)].val;
}
void build(int k,int l,int r) {
    tree[k].l=l; tree[k].r=r;
    if(l==r) {
        tree[k].val=l;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    push_up(k);
}
void update(int k,int qx,int val) {
    if(tree[k].l==tree[k].r) {
        tree[k].val=val;
        return;
    }
    if(qx<=tree[ls(k)].r)
        update(ls(k),qx,val);
    else
        update(rs(k),qx,val);
    push_up(k);
}
int query(int k,int ql,int qr) {
    if(ql<=tree[k].l&&tree[k].r<=qr)
        return tree[k].val;
    if(qr<tree[rs(k)].l)
        return query(ls(k),ql,qr);
    else if(ql>tree[ls(k)].r)
        return query(rs(k),ql,qr);
    else
        return query(ls(k),ql,qr)*p[min(tree[k].r,qr)-tree[rs(k)].l+1]+query(rs(k),ql,qr);
}
void init() {
    p[0]=1;
    rep(i,1,n)
        p[i]=p[i-1]*base;
    rep(i,1,n)
        fa[i]=i,vec[i].push_back(i);
    build(1,1,n);
}
int find(int x) {
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int u,int v) {
    u=find(u); v=find(v);
    if(u==v)
        return;
    if(vec[u].size()<vec[v].size())
        swap(u,v);
    for(auto x:vec[v]) {
        update(1,x,u);
        vec[u].push_back(x);
    }
    fa[v]=u;
    vec[v].clear();
}
int get_diff(int l1,int r1,int l2,int r2) {
    int l=1,r=r1-l1+1,ans=-1;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(query(1,l1,l1+mid-1)!=query(1,l2,l2+mid-1))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    return ans;
}
signed main() {
    scanf("%d%d",&n,&m);
    init();
    while(m--) {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        while(true) {
            int val=get_diff(l1,r1,l2,r2);
            if(val==-1)
                break;
            merge(l1+val-1,l2+val-1);
            l1+=val; l2+=val;
        }
    }
    int ans=9;
    bool flag=false;
    rep(i,1,n) {
        if(find(i)==i) {
            if(flag)
                ans=ans*10ll%MOD;
            flag=true;
        }
    }
    printf("%d\n",ans);
    return 0;
}