4998 题解

div.1 的题，然后打完 div.2 的沃去订了一下。 发现这道题竟然是 qoj 的，还没有写过 qoj 的 tj，故有此文。

首先我们看这个回文串到底给了我们什么信息：

对于一个回文串，正着读和反着读是一样的,即一个回文串 $s$，有 $s_i=s_{n-i+1}(1\le i\le n)$。

实际上操作 1 给的是所有相等的信息。

既然所有的都是相等的，不会出现不等的，那我们不妨构造 1 个 全是 a 的字符串。此时只有长度不同的两串才会回答 Not equal，所以实际上我们只需用判断 Unknown 和 Equal 即可。

然后我们使用并查集来维护每个点，然后将必须相等的位置放进一个集合，但这显然会超时。

我们考虑利用哈希来维护每个点在并查集中的根，合并是不断二分，找到最近的两个哈希值不同的节点合并。合并时用启发式合并优化，且用线段树维护区间的哈希值。

根据颜色段均摊，我们合并的次数不超过 $\mathcal O(n\log n)$，然后多了二分的 $\log n$。查询时只需要考虑两个区间的哈希值是否相等即可。所以说总的时间复杂度就是 $\mathcal O(n\log^2 n+q\log n)$。

附上沃的代码（偷懒了没有用线段树二分所以说实际上是 $\mathcal O(n\log^3 n+q\log n)$，险过）：

#include<bits/stdc++.h>
#define int long long
using namespace std;

constexpr int N=1e5+5,P=131,mod=1145141923;
int n,q,opt,l1,r1,l2,r2;
int p[N];

class segment{
public:
    class node{ public: int pre,suf,len; node operator + (const node &no) const{ return {(no.pre*p[len]%mod+pre)%mod,(no.suf+suf*p[no.len]%mod)%mod,len+no.len};}}tr[4*N];
    void push_up(int pos){ tr[pos]=tr[2*pos]+tr[2*pos+1];}
    void build(int pos,int l,int r){
        if(l==r) return tr[pos]={l,l,1},void();
        int mid=(l+r)>>1;
        build(2*pos,l,mid);
        build(2*pos+1,mid+1,r);
        push_up(pos);
    }
    void update(int pos,int l,int r,int x,int k){
        if(l==r) return tr[pos]={k,k,1},void();
        int mid=(l+r)>>1;
        if(x<=mid) update(2*pos,l,mid,x,k);
        else update(2*pos+1,mid+1,r,x,k);
        push_up(pos);
    }
    node query(int pos,int l,int r,int x,int y){
        if(x<=l&&r<=y) return tr[pos];
        int mid=(l+r)>>1;
        if(y<=mid) return query(2*pos,l,mid,x,y);
        else if(x>mid) return query(2*pos+1,mid+1,r,x,y);
        else return query(2*pos,l,mid,x,y)+query(2*pos+1,mid+1,r,x,y);
    }
}T;

class dsu{
public:
    int f[N],siz[N];
    vector<int>id[N];
    void init(){ for(int i=1;i<=n;i++) f[i]=i,siz[i]=1,id[i].push_back(i);}
    int find(int x){ return x==f[x]?x:f[x]=find(f[x]);}
    void merge(int u,int v){
        u=find(u),v=find(v);
        if(u==v) return;
        if(siz[u]>siz[v]) swap(u,v);
        f[u]=v,siz[v]+=siz[u];
        for(int i:id[u]){
            T.update(1,1,n,i,v);
            id[v].push_back(i);
        }
        id[u].clear();
    }
}D;

void combine(int l,int r){
    int lc=(l+r)>>1,rc=((l+r)>>1)+(!((r-l+1)&1)),len=((r-l+1)>>1)+((r-l+1)&1);
    for(;1;){
        int bl=1,br=len,ans=-1;
        for(;bl<=br;){
            int mid=(bl+br)>>1;
            auto ln=T.query(1,1,n,lc-mid+1,lc),rn=T.query(1,1,n,rc,rc+mid-1);
            if(ln.pre!=rn.suf) ans=mid,br=mid-1;
            else bl=mid+1;
        }
        if(ans==-1) return;
        D.merge(lc-ans+1,rc+ans-1);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    freopen("palindrome.in","r",stdin);
    freopen("palindrome.out","w",stdout);
    p[0]=1;
    for(int i=1;i<N;i++) p[i]=(p[i-1]*P)%mod;
    cin>>n>>q;
    D.init(); T.build(1,1,n);
    for(;q--;){
        cin>>opt>>l1>>r1;
        if(opt==1) combine(l1,r1);
        else{
            cin>>l2>>r2;
            if(r1-l1!=r2-l2) cout<<"Not equal\n";
            else{
                auto s1=T.query(1,1,n,l1,r1),s2=T.query(1,1,n,l2,r2);
                if(s1.pre==s2.pre&&s1.suf==s2.suf) cout<<"Equal\n";
                else cout<<"Unknown\n";
            }
        }
    }
}