题解 P7134 【小 H 的序列】

· · 题解

作为出题人过来发个题解.

首先很抱歉比赛时被暴力艹过去了,现在数据已经加强(时限也对应开大),欢迎大家用更奇怪的暴力来艹过.

分块.

对于整块的修改,直接用珂朵莉树维护每个值的出现次数;对于散块的修改,遍历从上次作为散块以来的所有修改,记录每个出现过的数最后变成了哪个数即可.注意散块修改细节实现的时候不能用并查集:比如依次进行1\gets2,3\gets1两个操作,并查集会记录为1~\text{and}~3\gets2.所以只能保存每一个数最后被修改成了什么,而不能记录中间过程.清空也请注意复杂度保持在\sqrt n以内.

每一块最多从第一次修改到第m次,参考珂朵莉树的证明可以发现每次修改时每块内的值的种类数期望是\log n的,所以散块总复杂度的期望大致是m\sqrt n\log n的.

对于询问,散块暴力整块珂朵莉树.

总复杂度大概是n\sqrt n\log n乘巨大的常数.不是很会分析,如果哪位大佬能仔细证一下的话就多谢了.

#include <algorithm>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;

typedef long long ll;

/* ---- read() & rlong() - begin ---- */
#define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048576,stdin),p0==p1)?EOF:*p0++)
char buf[1048576],*p0,*p1;
inline int read() {
    int r=0; char c=gc(); while (c<48||c>57) c=gc();
    while (c>47&&c<58) {r=(r<<3)+(r<<1)+(c^48); c=gc();} return r;
}
#undef gc
/* ---- read() & rlong() -- end ----- */

const int q=188; int p[35505],tim,val[35505],fat[35505],cnt[35505];
int upl[35505],upr[35505],upu[35505],upv[35505],upw[35505];
struct txb {
    int w; mutable int t;
    inline txb (int _w):w(_w),t(0) {}
    inline txb (int _w,int _t):w(_w),t(_t) {}
    bool operator <(const txb &op) const {return w<op.w;}
};
typedef set<txb>::iterator sit;
struct bxt {
    int l,r; vector<int> g; set<txb> s;

    inline void clear() {
        vector<int> e; int f;
        for (int i=l;i<=r;++i) {
            if (!fat[val[i]]) {
                f=val[i];
                for (auto j:g) if (f>=upu[j]&&f<=upv[j])
                    f=upw[j]; fat[val[i]]=f;
            }
            e.push_back(val[i]); val[i]=fat[val[i]];
        }
        for (auto i:e) fat[i]=0; g.clear();
    }

    inline void flatten(int u,int v,int w) {
        int t=0; g.push_back(tim);
        sit spl=s.lower_bound(txb(u)),spr=s.upper_bound(txb(v));
        if (spl==spr) return;
        for (sit i=spl;i!=spr;++i) t+=i->t;
        s.erase(spl,spr); spl=s.lower_bound(txb(w));
        if (spl->w==w) spl->t+=t; else s.insert(txb(w,t));
    }

    inline void update(int a,int b,int u,int v,int w) {
        clear(); s.clear();
        for (int i=l;i<=r;++i) {
            if (i>=a&&i<=b&&val[i]>=u&&val[i]<=v) val[i]=w;
            ++cnt[val[i]];
        }
        for (int i=l;i<=r;++i) if (cnt[val[i]]) {
            s.insert(txb(val[i],cnt[val[i]])); cnt[val[i]]=0;
        }
    }
} b[405];

inline int mjly(int u,int v) {return u<v?u:u-v;}

inline int ksm(int u,int v,int w) {
    int r=1; while (v) {
        if (v&1) r=(ll)u*r%w;
        u=(ll)u*u%w; v>>=1;
    }
    return r;
}

inline void update(int l,int r,int u,int v,int w) {
    if (p[l]==p[r]) b[p[l]].update(l,r,u,v,w);
    else {
        b[p[l]].update(l,r,u,v,w); b[p[r]].update(l,r,u,v,w);
        for (int i=p[l]+1;i<p[r];++i) b[i].flatten(u,v,w);
    }
}

inline int powmk(int l,int r,int t,int k) {
    int w=0;
    if (p[l]==p[r]) {
        b[p[l]].clear();
        for (int i=l;i<=r;++i) w=mjly(w+ksm(val[i],t,k),k);
        return w;
    }
    b[p[l]].clear(); b[p[r]].clear();
    for (int i=l;p[i]==p[l];++i) w=mjly(w+ksm(val[i],t,k),k);
    for (int i=r;p[i]==p[r];--i) w=mjly(w+ksm(val[i],t,k),k);
    for (int i=p[l]+1;i<p[r];++i)
        for (auto j:b[i].s) w=(w+(ll)j.t*ksm(j.w,t,k))%k;
    return w;
}

int main() {
    int n,m,l,r,t,k,a=0; n=read(); m=read(); p[0]=p[n+1]=-1;
    for (int i=1;i<=n;i+=q) {
        for (int j=0;j<q&&i+j<=n;++j) {
            p[i+j]=i/q; ++cnt[val[i+j]=read()];
        }
        b[p[i]].l=i; b[p[i]].r=min(i+q-1,n);
        for (int j=b[p[i]].l;j<=b[p[i]].r;++j) if (cnt[val[j]]) {
            b[p[i]].s.insert(txb(val[j],cnt[val[j]])); cnt[val[j]]=0;
        }
    }
    for (;tim<m;++tim) {
        if (read()) {
            l=read(); r=read(); t=read(); k=read();
            a^=powmk(l,r,t,k);
        }
        else {
            upl[tim]=read(); upr[tim]=read();
            upu[tim]=read(); upv[tim]=read(); upw[tim]=read();
            update(upl[tim],upr[tim],upu[tim],upv[tim],upw[tim]);
        }
    }
    printf("%d",a);
    return 0;
}