2021“MINIEYE杯”中国大学生算法设计超级联赛（4）

评测机出锅的一场，导致最后一个半小时无效时间，应该很快就能补完吧。

补完了。

[1001 Calculus]

solution

题面：给出一个函数 ，问

$$\lim_{n \to \infty} \sum_{i=1}^n f(i)$$

是否收敛。

其中 为 集合中函数的加法复合。​ 为一​​常数。

做法：注意这些集合的函数在 时的级数都是发散的，于是判一下 即可。时间复杂度 。

//2021.8.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    char str[100+10];
    inline void MAIN(){
        res T=read();
        while(T--){
            scanf("%s",str+1);
            res n=int(strlen(str+1));
            res fl=0;
            for(res i=1;i<=n;i++){
                if(str[i]<='9'&&str[i]>='0')if(str[i]!='0'){fl=1;break;}
            }
            if(fl)puts("NO");
            else puts("YES");
        }
    }
}

[1002 Kanade Loves Maze Designing]

solution

题面：一棵树，每个点有颜色，设 为 到 ​ 最短路径上的颜色个数，，对每个 ，输出 分别 和 的答案。​

做法：数据范围允许 ，所以暴力就结束了。时间复杂度 。

也没想更好的做法。

//2021.8.4 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
    int n;
    int a[N][N];
    vector<int> G[N];
    int c[N];
    int fl[N];
    void dfs(res x,res fax,const res &I,res sum){
        res FL=0;
        if(!fl[c[x]])fl[c[x]]=1,sum++,FL=1;
        a[I][x]=sum;
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dfs(tox,x,I,sum);
        }
        if(FL)fl[c[x]]=0;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read();
            for(res i=1;i<=n;i++)vector<int>().swap(G[i]);
            for(res i=2;i<=n;i++){
                res p=read();
                G[p].pb(i),G[i].pb(p);
            }
            for(res i=1;i<=n;i++)c[i]=read();
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)a[i][j]=0;
            for(res i=1;i<=n;i++)fl[i]=0;
            for(res i=1;i<=n;i++)dfs(i,0,i,0);
            const int O=19560929;
            for(res i=1;i<=n;i++){
                res nwO=1,ret=0;
                kcz=1000000007;
                for(res j=1;j<=n;j++)add(ret,mul(a[i][j],nwO)),nwO=mul(nwO,O);
                printf("%d ",ret);
                kcz=1000000009,ret=0,nwO=1;
                for(res j=1;j<=n;j++)add(ret,mul(a[i][j],nwO)),nwO=mul(nwO,O);
                printf("%d\n",ret);
            }
        }
    }
}

[1003 Cycle Binary]

solution

题面：一个 串可以被拆成 的形式，其中 是 的前缀， 为 重复 次。一个串的价值为找到一个 ，使 最大时的 。问长度为 的所有 串的价值和。

做法：设 ​​​​​​ 为长度为 ​​​​​​ 的非整周期 ​​​​​​ 串个数，经过手玩发现，最后答案是 ​​​​​​​​。下面先证明这件事（考场上我就没证了）。

为了方便说明，我们先定义以下规定：

​ 1. ​​ 为一字符串，​ 为其长度，​​ ​为把 的第 个字符到第 个字符取出来构成的新字符串，特别地，当 ，。

​ 2. 若 ​ 和整数 ​ 满足 ​，且对于所有的 ​ ，都有 ​，则称 ​ 为串 ​ 的周期。特别地，当 ​ 时，则称 ​ 是 ​ 的整周期，称 ​ 为整周期串。

​ 3. 定义 表示 的所有周期组成的集合， 表示 。

接下来我们就先来证明一个重要引理：

Periodicity Lemma：若 ，且 ，则 ​。

Proof：不妨设 ​

我们定义 ​，写出 ​​​ 的 OGF，即​​

$$S_p(x)=\sum_n S[n\mod p]x^n\\\\ =P(x)+P(x)x^p+...\\\\ =\frac{P(x)}{1-x^p}$$

其中 。

同理，我们写出 ​。

两者做差，得到

$$S_p(x)-S_q(x)\\\\ =\frac{1-x^{\gcd(p,q)}}{(1-x^p)(1-x^q)}(\frac{(1-x^q)P(x)-(1-x^p)Q(x)}{1-x^{\gcd(p,q)}})$$

注意到 ​

那么 ​，于是

$$\deg \lbrace \frac{(1-x^q)P(x)-(1-x^p)Q(x)}{1-x^{\gcd(p,q)}} \rbrace \leq p+q-1-\gcd(p,q)$$

而由于 ​ 为 ​ 的周期，有

$$\begin{align*} &\sum_{n=0}^{|S|-1} (S[n\mod p]-S[n\mod q])x^n\\ &=\sum_{n=0}^{|S|-1} (S[n\mod p+\lfloor\frac{n}{p}\rfloor\cdot p]-S[n\mod q+\lfloor\frac{n}{q}\rfloor\cdot q])x^n\\ &=\sum_{n=0}^{|S|-1}(S[n]-S[n])x^n\\ &=0 &\end{align*}$$

这意味着 的前 次的系数都为 ​，而

$$\deg \lbrace \frac{(1-x^q)P(x)-(1-x^p)Q(x)}{1-x^{\gcd(p,q)}} \rbrace < p+q-\gcd(p,q)\leq n$$

这便意味着

$$\begin{align*} &\frac{(1-x^q)P(x)-(1-x^p)Q(x)}{1-x^{\gcd(p,q)}}=0\\ &\implies S_p(x)-S_q(x)=0\\ &\iff S_p(x)=S_q(x)\\ &\iff s_p(i)=s_q(i) &\end{align*}$$

同时根据裴蜀定理，有 ，因此就得到

$$\begin{align*} &S[i]=s_p(i)=s_p(i+p\cdot u)\\ &=s_q(i+p\cdot u)=s_q(i+p\cdot u+q\cdot v)\\ &=s_q(i+\gcd(p,q))=S[i+\gcd(p,q)] &\end{align*}$$

于是就证明 也是 的一个周期了。

证明了引理之后，我们再回头来看这道题。

我们枚举长度 ​，猜测此时长度为 ​ 的非整周期 ​ 串构成的 ​ 最大的 ​ 一定是 ​ 在长度为 ​ 时取到。如果不是，那么就存在一个更小的 ​ 满足题目条件。

若 ​，根据 Periodicity Lemma，就说明 ​​ 也是 的一个周期，而 ，说明长度为 ​ 的串并不是非整周期串，矛盾​。

若 ​，由 ​，就会得到 ​。此时再观察我在最开始给出的答案式子，我们发现此时的 ​ 前的系数都为 ​ 了，而剩下来的 ​ 正好是长度大于 ​​ 的所有串，而且它们的 ​ 刚好只能为 ​。

于是我们终于证明了最开始式子的正确性了。

接下来想如何求解，这其实是平凡的数论题了。

​​​​ 是非整周期串，直接求似乎不容易，我们考虑求长度为 ​​​​ 的整周期串，然后再用 ​​​​ 减掉。而整周期串就相当于它的一个子串重复若干遍，那就等于找到一个非整周期串，然后重复若干次即可。于是 ​​​​。移项之后，就有 ​​​​，这就已经可以杜教筛了，因为 ​​​​ 可以整除分块，而需要用到的端点值与杜教筛求出的是一致的，于是就成功了。时间复杂度 ​​​。

而我们考场上是用了一次莫反，​注意到 ​​​ 后，容易想到莫反，即 ​​​​，然后还是杜教筛，似乎毫无区别。。。

当然复杂度可以优化到 ​​，这是基于 Dirichlet 双曲线法 可以轻松做到的。

下面代码当然是杜教筛了，另一种做法我就没实现过。

//2021.8.4 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    int prim[N],tot,vis[N],f[N],pw[N];
    const int HashMod=100007;
    struct HashTable{
        struct E{
            int nxt,v,val;
            E() {}
            E(res nxt,res v,res val):nxt(nxt),v(v),val(val) {}
        }edge[300000+10];
        int head[HashMod],cnt,now,non;
        inline void ADD(const res &u,const res &v,const res &w){
            edge[++cnt]=E(head[u],v,w),head[u]=cnt;
        }
        inline int Query(const res &x){
            res s=x%HashMod;
            for(res i=head[s];i;i=edge[i].nxt)if(edge[i].v==x)return edge[i].val;
            return -1;
        }
        inline void Hash(const res &x,const res &k){
            res s=x%HashMod;
            ADD(s,x,k);
        }
    }F;
    inline int getF(const res &n){
        if(n<=N-10)return f[n];
        res o=F.Query(n);
        if(o!=-1)return o;
        RG LL ret=qpow(2,n+1)-2;
        for(res l=2,r,t;l<=n;l=r+1)r=n/(t=n/l),ret-=1ll*(r-l+1)*getF(t);
        ret=(ret%kcz+kcz)%kcz;
        F.Hash(n,int(ret));
        return int(ret);
    }
    inline void MAIN(){
        for(res i=2;i<=N-10;i++){
            if(!vis[i])prim[++tot]=i;
            for(res j=1;j<=tot&&prim[j]*i<=N-10;j++){
                vis[prim[j]*i]=1;
                if(i%prim[j]==0)break;
            }
        }
        pw[0]=1;
        for(res i=1;i<=N-10;i++)pw[i]=Add(pw[i-1],pw[i-1]);
        for(res i=1;i<=N-10;i++){
            f[i]=Add(pw[i],kcz-f[i]);
            for(res j=i+i;j<=N-10;j+=i)add(f[j],f[i]);
            add(f[i],f[i-1]);
        }
        res T=read();
        while(T--){
            res n=read();
            RG LL ans=qpow(2,n);
            for(res l=1,r,t;l<=n;l=r+1)r=n/(t=n/l),ans+=1ll*(t-1)*(getF(r)-getF(l-1));
            printf("%lld\n",(ans%kcz+kcz)%kcz);
        }
    }
}

[1004 Display Substring]

solution

题面：​ 个字母有各自的价值，一个字符串的价值定义为它的字符价值之和。给定字符串，问它的本质不同的子串中第 ​​ 小价值。

做法：看到本质不同子串想到 ​ (毕竟我不会 ​)。直接似乎不好处理。于是我们二分第 ​​​ 小价值，在后缀树上统计小于等于该价值的字符串有多少个就可以了。而这个统计我们还需要在每个节点二分一次，即预处理好每个节点的一个 endpos ，然后记录出现范围，拿这个二分就好了，这里用前缀和维护就可以 ​ 计算一个串的价值了。时间复杂度 ​。

//2021.8.4 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n;
    LL k;
    struct Sam{
        int vis[26],par,len,pos;
        inline void init(){
            memset(vis,0,sizeof(vis));
            par=len=pos=0;
        }
    }sam[N];
    int cnt,las,rt;
    inline void init(){
        cnt=las=rt=1,sam[1].init();
    }
    inline void extend(const res &x,const res &I){
        res p=las,np=++cnt;
        sam[np].init(),sam[np].len=sam[p].len+1,sam[np].pos=I;
        for(;p&&!sam[p].vis[x];p=sam[p].par)sam[p].vis[x]=np;
        if(!p)sam[np].par=rt;
        else {
            res q=sam[p].vis[x];
            if(sam[q].len==sam[p].len+1)sam[np].par=q;
            else {
                res nq=++cnt;
                sam[nq].pos=0;
                memcpy(sam[nq].vis,sam[q].vis,sizeof(sam[nq].vis));
                sam[nq].par=sam[q].par;
                sam[nq].len=sam[p].len+1;
                sam[q].par=sam[np].par=nq;
                for(;p&&sam[p].vis[x]==q;p=sam[p].par)sam[p].vis[x]=nq;
            }
        }
        las=np;
    }
    char str[N];
    int c[N];
    int sum[N];
    vector<int> G[N];
    int mx[N];
    LL dfs(res x,const res &lim){
        RG LL s=0;
        if(x!=1){
            if(mx[x]<=lim)s=sam[x].len-sam[sam[x].par].len;
            else {
                res l=sam[x].pos-sam[x].len+1,r=sam[x].pos-sam[sam[x].par].len,ret=-1;
                while(l<=r){
                    res mid=(l+r)>>1;
                    if(sum[sam[x].pos]-sum[mid-1]<=lim)r=mid-1,ret=mid;
                    else l=mid+1;
                }
                if(ret==-1);
                else s=sam[x].pos-sam[sam[x].par].len-ret+1;
            }
        }
        for(auto tox:G[x])s+=dfs(tox,lim);
        return s;
    }
    inline bool ck(const res &lim){
        return dfs(1,lim)<k;
    }
    int buc[N],pos[N];
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),k=Read(),init(),scanf("%s",str+1);
            for(res i=1;i<=n;i++)extend(str[i]-'a',i);
            for(res i=0;i<26;i++)c[i]=read();
            for(res i=1;i<=n;i++)sum[i]=sum[i-1]+c[str[i]-'a'];
            for(res i=0;i<=n;i++)buc[i]=0;
            for(res i=1;i<=cnt;i++)buc[sam[i].len]++,vector<int>().swap(G[i]);
            for(res i=1;i<=n;i++)buc[i]+=buc[i-1];
            for(res i=cnt;i;i--)pos[buc[sam[i].len]--]=i;
            for(res i=cnt;i>1;i--){
                res p=pos[i],fa=sam[p].par;
                G[fa].pb(p);
                if(!sam[fa].pos)sam[fa].pos=sam[p].pos;
                mx[p]=sum[sam[p].pos]-sum[sam[p].pos-sam[p].len];
            }
            res l=0,r=sum[n],ret=-1;
            while(l<=r){
                res mid=(l+r)>>1;
                if(ck(mid))l=mid+1;
                else r=mid-1,ret=mid;
            }
            printf("%d\n",ret);
        }
    }
}

[1005 Didn’t I Say to Make My Abilities Average in the Next Life?!]

solution

题面：给你一个序列 ​，每次询问一个区间 ​，随机选取 ​，此时贡献是 ​，问贡献的期望。

做法：首先，这个贡献是可以拆开来的，于是我们分别算 和 ​。下面先算 。​

我们先用单调栈维护出每个点能管到的区间，记为 ​。

对于区间 而言，若一个点的 ，那么它的贡献显然是 。于是，我们写得更精确一点，若一个点 满足 ，则它的贡献为 。

这个东西看起来不太好直接维护。那我们考虑一种特殊情况，若 ，这个东西能快速维护吗？

我们发现是可以的。当 的时候，，那 影响的便是 ，而这个东西，我们可以讨论一下。一方面， 的 ，此时我们要维护的正是 ，这可以用一棵可持久化线段树维护 的情况，将每个点插入 里，那这个东西就可以用 求出来的值减去 的值来得到。另一方面， 的 ，我们如上，只不过维护的是 ，仍可以用一棵可持久化线段树维护。

我们现在会维护 的情况了。若 呢？我们找到 的最大值位置 ，此时在 左边的在 右边的数的 ​ 不可能越过 ，那就等价于 了。右半部分同理。求 亦同理。于是，我们就在 的时间复杂度内， 的空间复杂度内解决了这个问题。

官方题解是离线的，实际做法差不多，离线下来后就等价于 了，同理维护。

//2021.8.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
const int M=N*21*2;
namespace MAIN{
    int n,m;
    int a[N];
    inline Pair operator + (const RG Pair &x,const RG Pair &y){
        return mp(Add(x.fi,y.fi),Add(x.se,y.se));
    }
    inline Pair operator - (const RG Pair &x,const RG Pair &y){
        return mp(Add(x.fi,kcz-y.fi),Add(x.se,kcz-y.se));
    }
    struct TR{
        int L[N],R[N],val[M],vali[M],valx[M];
        int tr[N<<2];
        inline int merge(const res &x,const res &y){
            return R[x]-L[x]>R[y]-L[y]?x:y;
        }
        int find(res rt,res l,res r,const res &L,const res &R){
            if(L<=l&&r<=R)return tr[rt];
            res mid=(l+r)>>1,ret=0;
            if(L<=mid)ret=find(rt<<1,l,mid,L,R);
            if(R>mid)ret=merge(ret,find(rt<<1|1,mid+1,r,L,R));
            return ret;
        }
        int rtl[N],rtr[N],tot,ls[M],rs[M];
        void build(res &rt,res pre,res l,res r,const res &p,const res &y,const res &z,const res &w){
            rt=++tot,ls[rt]=ls[pre],rs[rt]=rs[pre],val[rt]=Add(val[pre],y),vali[rt]=Add(vali[pre],z),valx[rt]=Add(valx[pre],w);
            if(l==r)return;
            res mid=(l+r)>>1;
            if(p<=mid)build(ls[rt],ls[pre],l,mid,p,y,z,w);
            else build(rs[rt],rs[pre],mid+1,r,p,y,z,w);
        }
        void build(res rt,res l,res r){
            if(l==r){tr[rt]=l;return;}
            res mid=(l+r)>>1;
            build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
            tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]);
        }
        inline void init(){
            tot=0,build(1,1,n);
            for(res i=1;i<=n;i++){
                res x=mul(mul(R[i]-i+1,i-L[i]+1),a[i]),y=mul(a[i],i);
                build(rtl[i],rtl[i-1],1,n,L[i],mul(R[i]-i+1,a[i]),mul(R[i]-i+1,y),x);
                build(rtr[i],rtr[i-1],1,n,R[i],mul(i-L[i]+1,a[i]),mul(i-L[i]+1,y),x);
            }
        }
        int query(res rt,res l,res r,const res &L,const res &R){
            if(!rt)return 0;
            if(L<=l&&r<=R)return valx[rt];
            res mid=(l+r)>>1,ret=0;
            if(L<=mid)ret=query(ls[rt],l,mid,L,R);
            if(R>mid)add(ret,query(rs[rt],mid+1,r,L,R));
            return ret;
        }
        Pair g(res rt,res l,res r,const res &L,const res &R){
            if(!rt)return mp(0,0);
            if(L<=l&&r<=R)return mp(val[rt],vali[rt]);
            res mid=(l+r)>>1;
            RG Pair ret=mp(0,0);
            if(L<=mid)ret=g(ls[rt],l,mid,L,R);
            if(R>mid)ret=ret+g(rs[rt],mid+1,r,L,R);
            return ret;
        }
        inline int solve(const res &l,const res &r){
            res p=find(1,1,n,l,r),ret=mul(a[p],mul(r-p+1,p-l+1));
            RG Pair aqua;
            if(p!=l){
                add(ret,Add(query(rtl[p-1],1,n,l,n),kcz-query(rtl[l-1],1,n,l,n)));
                if(l!=1)aqua=g(rtl[p-1],1,n,1,l-1)-g(rtl[l-1],1,n,1,l-1),add(ret,Add(mul(aqua.fi,1-l+kcz),aqua.se));
            }
            if(p!=r){
                add(ret,Add(query(rtr[r],1,n,1,r),kcz-query(rtr[p],1,n,1,r)));
                if(r!=n)aqua=g(rtr[r],1,n,r+1,n)-g(rtr[p],1,n,r+1,n),add(ret,Add(mul(aqua.fi,r+1),kcz-aqua.se));
            }
            return ret;
        }
    }t[2];
    //t[0] max
    //t[1] min
    int st[N],top;
    int inv[N];
    inline void MAIN(){
        inv[0]=inv[1]=1;
        for(res i=2;i<=N-10;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        res T=read();
        while(T--){
            n=read(),m=read();
            for(res i=1;i<=n;i++)a[i]=read();
            st[top=0]=0;
            for(res i=1;i<=n;i++){
                while(top&&a[st[top]]<a[i])top--;
                t[0].L[i]=st[top]+1,st[++top]=i;
            }
            st[top=0]=0;
            for(res i=1;i<=n;i++){
                while(top&&a[st[top]]>a[i])top--;
                t[1].L[i]=st[top]+1,st[++top]=i;
            }
            st[top=0]=n+1;
            for(res i=n;i;i--){
                while(top&&a[st[top]]<=a[i])top--;
                t[0].R[i]=st[top]-1,st[++top]=i;
            }
            st[top=0]=n+1;
            for(res i=n;i;i--){
                while(top&&a[st[top]]>=a[i])top--;
                t[1].R[i]=st[top]-1,st[++top]=i;
            }
            t[0].init(),t[1].init();
            while(m--){
                res l=read(),r=read();
                printf("%d\n",mul(Add(t[0].solve(l,r),t[1].solve(l,r)),mul(inv[r-l+1],inv[r-l+2])));
            }
        }
    }
}

[1006 Directed Minimum Spanning Tree]

solution

题面：给个有向图，求出以每个点为根的外向树的最小生成树。

做法：出模板题是我没想到的。

考场上因为榜的原因也没去思考这个东西。实际上队友的翻译并不完全精确，理论上翻译成最小树形图那大家就都懂了。然后 它这里的范围就告诉你要实现 Tarjan 曾经提出的 Edmond’s Algorithm 的优化做法。那就赶紧去学习一下了。

Tarjan 提出的做法和本来的基本类似，仍旧是考虑缩点，只不过利用可并堆来维护入边边权，于是就可以做到 或者 了，这看的是可并堆的实现。

我写的当然是左偏树了。

//2021.8.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
const LL IN=4e13;
namespace MAIN{
    int n,m;
    int fa[N];
    inline int find(res x){
        while(x!=fa[x])x=fa[x]=fa[fa[x]];
        return x;
    }
    struct E{
        int u,v;
        LL w;
        E() {}
        E(res u,res v,RG LL w):u(u),v(v),w(w) {}
        inline void init(){
            u=read(),v=read(),w=read();
        }
    }edge[N];
    struct Left{
        struct TR{
            int l,r,dis;
            LL val,laz;
            inline void init(const res &I){
                l=r=dis=0,laz=0,val=edge[I].w;
            }
        }tr[N];
        int rt[N];
        inline void change(const res &x,const RG LL &v){
            if(!x)return;
            tr[x].val+=v,tr[x].laz+=v;
        }
        inline void pushdown(const res &x){
            if(!tr[x].laz)return;
            change(tr[x].l,tr[x].laz),change(tr[x].r,tr[x].laz),tr[x].laz=0;
        }
        int merge(res x,res y){
            if(!x||!y)return x|y;
            if(tr[x].val>tr[y].val||(tr[x].val==tr[y].val&&x>y))swap(x,y);
            pushdown(x),tr[x].r=merge(tr[x].r,y);
            if(tr[tr[x].l].dis<tr[tr[x].r].dis)swap(tr[x].l,tr[x].r);
            tr[x].dis=tr[tr[x].r].dis+1;
            return x;
        }
        inline void pop(const res &x){
            pushdown(x),rt[tr[x].l]=rt[tr[x].l],rt[tr[x].r]=tr[x].r,rt[x]=merge(tr[x].l,tr[x].r);
        }
    }A;
    int ine[N];
    vector<int> G[N];
    LL ans[N];
    void dfs(res x,RG LL s){
        if(G[x].empty())ans[x]=(s>=IN?-1:s);
        else for(auto tox:G[x])dfs(tox,s-A.tr[ine[tox]].val);
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),m=read();
            res nn=n;
            for(res i=1;i<=m;i++)edge[i].init();
            for(res i=1;i<=n<<1;i++)A.rt[i]=ine[i]=0,fa[i]=i,vector<int>().swap(G[i]);
            for(res i=1;i<=n;i++)edge[++m]=E(i%n+1,i,IN);
            for(res i=1;i<=m;i++)A.tr[i].init(i),A.rt[edge[i].v]=A.merge(A.rt[edge[i].v],i);
            res x=1;
            while(A.rt[x]){
                res i=A.rt[x],y=find(edge[i].u);
                A.rt[x]=A.merge(A.tr[i].l,A.tr[i].r);
                if(x==y)continue;
                ine[x]=i;
                if(!ine[edge[i].u])x=y;
                else for(res z=++n;x!=z;x=find(edge[ine[x]].u)){
                    fa[find(x)]=z,G[z].pb(x);
                    if(A.rt[x])A.change(A.rt[x],-A.tr[ine[x]].val);
                    A.rt[z]=A.merge(A.rt[z],A.rt[x]);
                }
            }
            RG LL ret=0;
            for(res i=1;i<=n;i++)ret+=A.tr[ine[i]].val;
            dfs(n,ret);
            for(res i=1;i<=nn;i++)printf("%lld\n",ans[i]);
        }
    }
}

[1007 Increasing Subsequence]

solution

题面：求一个排列的极大上升子序列的数量。

做法：看到这个问题，容易先写出一个 dp，即 表示 ​ 且以 结尾的极大上升子序列的数量，转移就是找到每一个小于 且它到 位置中间没有一个比它大且比 小的数。这个转移的正确性是容易证明的，毕竟我们求的是极大上升子序列。直接转移就是 的，我们想优化这个过程。

我在考场上开始想的是单调栈，后来发现实际转移的点直接与 ​​ 有关，除非我维护每个 ​​ 的单调栈。然后我感觉这不太可做，就改变了下转移式。即设 ​​ 表示 ​​​​​，​于是改写转移式为

$$f_{a_i}=\sum_{j=1}^{a_i-1} f_j\cdot[p_j=\max(p_j,...,p_{a_i-1})]$$

这样转移式至少是段连续的区间，比起之前看似容易不少。而后面那个判断式实际上是后缀最大值，这就有个标准的线段树二分做法了。

我们记录 ​ 表示线段树上 ​ 节点所代表的区间的最大值，​ 表示 ​ 节点在考虑它右儿子对左儿子有影响的情况下，左儿子的 ​。这就有个经典的做法，设 ​ 表示 ​ 节点在考虑后缀最大值为 ​ 的情况下的 ​，那样转移就是讨论当前区间最大值与 ​ 的关系然后看如何递归进线段树，这具体可以我代码。而 就是 ​​ ​，于是就在 的复杂度内完成这些维护。那查询就是个标准的线段树查询了。总时间复杂度 。

这个做法大概比标算的分治好一点，毕竟我可以修改。

//2021.8.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n;
    struct T{
        int sf,mx,cnt;
        inline void init(){
            sf=mx=cnt=0;
        }
    }tr[N<<2];
    int calc(res rt,res l,res r,res suf){
        if(l==r){
            if(tr[rt].mx>suf)return tr[rt].sf;
            return 0;
        }
        res mid=(l+r)>>1;
        if(tr[rt<<1|1].mx<suf)return 0+calc(rt<<1,l,mid,suf);
        return Add(tr[rt].cnt,calc(rt<<1|1,mid+1,r,suf));
    }
    void modify(res rt,res l,res r,const res &p,const res &v,const res &I){
        if(l==r){tr[rt].sf=v,tr[rt].mx=I;return;}
        res mid=(l+r)>>1;
        if(p<=mid)modify(rt<<1,l,mid,p,v,I);
        else modify(rt<<1|1,mid+1,r,p,v,I);
        tr[rt].mx=max(tr[rt<<1].mx,tr[rt<<1|1].mx);
        tr[rt].cnt=calc(rt<<1,l,mid,tr[rt<<1|1].mx);
    }
    int rmx;
    int query(res rt,res l,res r,const res &L,const res &R){
        res mid=(l+r)>>1,ret=0;
        if(l==r){
            if(tr[rt].mx>rmx)ret=tr[rt].sf,rmx=tr[rt].mx;
            return ret;
        }
        if(L<=l&&r<=R){
            ret=calc(rt,l,r,rmx),rmx=max(rmx,tr[rt].mx);
            return ret;
        }
        if(R>mid)ret=query(rt<<1|1,mid+1,r,L,R);
        if(L<=mid)add(ret,query(rt<<1,l,mid,L,R));
        return ret;
    }
    int a[N],f[N];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read();
            for(res i=1;i<=n<<2;i++)tr[i].init();
            res ans=0;
            for(res i=1;i<=n;i++){
                rmx=0;
                res x=read(),y=query(1,1,n,1,x-1);
                if(!y)y=1;
                modify(1,1,n,x,y,i),a[i]=x,f[i]=y;
            }
            res mx=0;
            for(res i=n;i;i--)if(mx<a[i])mx=a[i],add(ans,f[i]);
            printf("%d\n",ans);
        }
    }
}

[1008 Lawn of the Dead]

solution

题面：给一个 ​ 的方格图，有 ​ 个位置有地雷不能踩，每次可以到 ​ 或 ​​，问可以到达的点有几个。

做法：注意到斜对角的地雷会让它俩夹的那个右上的地方变成地雷，这是所有情况的本质。而第零列和第零行可以看做全是地雷，最终情况就是这样反复变地雷。考虑一行行维护，可用线段树也可用 set ，不过线段树好写很多，不用什么讨论。

下面代码使用线段树维护线段右端点的，时间复杂度 。

坑：注意两端区间是可以合并的，所以不要急着插入到线段树里，需要在外面先合并线段再插入。

//2021.8.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,m,k;
    vector<int> a[N];
    struct TR{
        int cov[N<<2],laz[N<<2];
        inline void INIT(){
            for(res i=1;i<=m<<2;i++)cov[i]=0,laz[i]=-1;
        }
        inline void change(const res &rt,const res &v){
            cov[rt]=laz[rt]=v;
        }
        inline void pushdown(const res &rt){
            if(laz[rt]==-1)return;
            change(rt<<1,laz[rt]),change(rt<<1|1,laz[rt]),laz[rt]=-1;
        }
        void modify(res rt,res l,res r,const res &L,const res &R,const res &v){
            if(L<=l&&r<=R){change(rt,v);return;}
            pushdown(rt);
            res mid=(l+r)>>1;
            if(L<=mid)modify(rt<<1,l,mid,L,R,v);
            if(R>mid)modify(rt<<1|1,mid+1,r,L,R,v);
        }
        int query(res rt,res l,res r,const res &p){
            if(l==r)return cov[rt];
            pushdown(rt);
            res mid=(l+r)>>1;
            if(p<=mid)return query(rt<<1,l,mid,p);
            return query(rt<<1|1,mid+1,r,p);
        }
        inline void init(){
            change(1,0);
        }
    }A[2];
    Pair aqua[N];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),m=read(),k=read();
            for(res _=0;_<=1;_++)A[_].INIT();
            for(res i=1;i<=n;i++)vector<int>().swap(a[i]);
            for(res i=1;i<=k;i++){
                res x=read(),y=read();
                a[x].pb(y);
            }
            for(res i=1;i<=n;i++)sort(a[i].begin(),a[i].end());
            RG LL ans=0;
            if(a[1].empty())A[1].init();
            else ans+=m-a[1][0]+1,A[1].modify(1,1,m,a[1][0],m,m);
            for(res i=2;i<=n;i++){
                res d=i&1;
                A[d].init();
                res ax=0;
                res y=A[d^1].query(1,1,m,1);
                if(y>0)aqua[++ax]=mp(1,y);
                for(auto x:a[i]){
                    y=A[d^1].query(1,1,m,x+1);
                    if(y>0)aqua[++ax]=mp(x,y);
                    else aqua[++ax]=mp(x,x);
                }
                if(!ax)continue;
                res l=aqua[1].fi,r=aqua[1].se;
                for(res j=2;j<=ax;j++){
                    if(r+1>=aqua[j].fi)r=max(r,aqua[j].se);
                    else A[d].modify(1,1,m,l,r,r),ans+=r-l+1,l=aqua[j].fi,r=aqua[j].se;
                }
                A[d].modify(1,1,m,l,r,r),ans+=r-l+1;
            }
            printf("%lld\n",1ll*n*m-ans);
        }
    }
}

[1009 License Plate Recognition]

solution

题面：给你个车牌号，输出每个字母或数字或汉字的左右端点在第几列。车牌号由点阵中的 “#” 给出。

做法：注意到除了汉字外，其它的都是一行连续的。于是先判完其他的再判汉字即可。

//2021.8.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
    char str[N];
    int vis[N],al[11],ar[11];
    inline int getr(res x){
        while(!vis[x])x--;
        return x;
    }
    inline int getl(res x){
        while(vis[x])x--;
        return x+1;
    }
    inline void MAIN(){
        res Case=read();
        for(res T=1;T<=Case;T++){
            for(res i=1;i<=100;i++)vis[i]=0;
            for(res i=1;i<=30;i++){
                scanf("%s",str+1);
                for(res j=1;j<=100;j++)vis[j]|=(str[j]=='#');
            }
            al[7]=101;
            for(res i=6;i;i--)ar[i]=getr(al[i+1]-1),al[i]=getl(ar[i]);
            ar[0]=getr(al[1]-1);
            al[0]=1;
            while(!vis[al[0]])al[0]++;
            printf("Case #%d:\n",T);
            for(res i=0;i<=6;i++)printf("%d %d\n",al[i],ar[i]);
        }
    }
}

[1010 Pony Running]

solution

题面：​ 的网格图，每个点都有 ​​ 的概率分别向相邻的四个位置（可以出去）移动，保证 ​。有 ​ 次操作，要么是修改一个位置的 ​，要么是询问从每个点出发到界外的期望步数和。

做法：出题人利用 整了个麻烦的做法，我们大概率是不用的，虽然这个做法有其它推广价值。

我们容易写出 转移式。暴力消元显然是 ，但这又是网格图消元，有两种经典的做法就来了（可以参考王修涵的集训队论文）。

一种是注意到系数矩阵是 ，而 Band 的长度通过对矩阵的不同编号可以是 的。根据 的特性，每次沿着对角线按 的长度消第一列，那复杂度就是 ，最坏即 。

另一种方法是考虑到当我知道四个点的 值时，根据转移式，我可以直接推出剩下的那个点的 值。于是理论上我们真正用到的元只有 个，那暴力消元的复杂度就是 了，最坏情况也是 ​ 。

但似乎主元法会遇到一些困难，因为这里的 可以为 ​​​，这导致一些位置的 值不能用我选取的主元合理递推表示，如果一直添加不能表示的点，那主元个数就无法保障了。我暂时也没想到解决方案，只能留个坑了。

所以代码只能是 了。

//2021.8.7 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=400+10;
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
namespace MAIN{
    int p[N][N],g[N][N];
    int pr[N][N][4],PR[N][N][4];
    int ans[N];
    inline int gauss(const res &n,const res &band){
        res ret=0;
        for(res i=1;i<=n;i++){
            if(!g[i][i]){
                for(res j=i+1,sz=min(n,i+band);j<=sz;j++){
                    if(g[j][i]){
                        swap(g[i],g[j]);
                        break;
                    }
                }
            }
            if(!g[i][i])continue;
            res INV=qpow(g[i][i]);
            for(res j=i+1,sz=min(n,i+band);j<=sz;j++){
                res div=mul(g[j][i],INV);
                for(res k=i,SZ=min(n,i+band*2);k<=SZ;k++)add(g[j][k],kcz-mul(div,g[i][k]));
                add(g[j][n+1],kcz-mul(div,g[i][n+1]));
            }
        }
        for(res i=n;i;i--){
            ans[i]=g[i][n+1];
            for(res j=i+1,SZ=min(n,i+band*2);j<=SZ;j++)add(ans[i],kcz-mul(g[i][j],ans[j]));
            ans[i]=mul(ans[i],qpow(g[i][i]));
            add(ret,ans[i]);
        }
        return ret;
    }
    inline void MAIN(){
        res n=read(),m=read(),q=read();
        for(res i=1;i<=n;i++)for(res j=1;j<=m;j++)for(res k=0;k<=3;k++)pr[i][j][k]=read();
        res fl=0;
        if(n<m){
            fl=1;
            for(res i=1;i<=n;i++)for(res j=1;j<=m;j++)for(res k=0;k<=3;k++)PR[j][i][k]=pr[i][j][k];
            for(res i=1;i<=n;i++)for(res j=1;j<=m;j++)for(res k=0;k<=3;k++)pr[i][j][k]=PR[i][j][k];
            swap(n,m);
        }
        for(res i=1;i<=n;i++)
            for(res j=1;j<=m;j++){
                res id=(i-1)*m+j;
                p[id][id]=1;
                for(res k=0;k<=3;k++){
                    res ni=i+dx[k],nj=j+dy[k];
                    if(ni&&nj&&ni<=n&&nj<=m)p[id][(ni-1)*m+nj]=Add(kcz-pr[i][j][k],0);
                }
                p[id][n*m+1]=1;
            }
        while(q--){
            res opt=read();
            if(opt==1){
                if(!fl){
                    res x=read(),y=read();
                    for(res k=0;k<=3;k++)pr[x][y][k]=read();
                    res id=(x-1)*m+y;
                    for(res k=0;k<=3;k++){
                        res ni=x+dx[k],nj=y+dy[k];
                        if(ni&&nj&&ni<=n&&nj<=m)p[id][(ni-1)*m+nj]=Add(kcz-pr[x][y][k],0);
                    }
                }
                else {
                    res y=read(),x=read();
                    for(res k=0;k<=3;k++)pr[x][y][k]=read();
                    res id=(x-1)*m+y;
                    for(res k=0;k<=3;k++){
                        res ni=x+dx[k],nj=y+dy[k];
                        if(ni&&nj&&ni<=n&&nj<=m&&pr[x][y][k])p[id][(ni-1)*m+nj]=Add(kcz-pr[x][y][k],0);
                    }
                }
            }
            else {
                for(res i=1;i<=n*m;i++)for(res j=1;j<=n*m+1;j++)g[i][j]=p[i][j];
                printf("%d\n",gauss(n*m,min(n*m,2*m+1)));
            }
        }
    }
}

[1011 Travel on Tree]

solution

题面：给出一棵树，有边权，每次询问 ，要你初始自己定在一个点，然后从这个点开始走，走遍 ​ 编号的点，问走过的路的总边权。

做法：好题！为什么说是好题，只是希望…理智粉

这题的 做法并不能让他成为一道好题，但去掉 ​ 后是真的秒。

带 的做法是平凡的。询问 ​，容易想到虚树，那答案就是虚树上边权之和的两倍。但显然暴力的复杂度是 ​ 的，因为它没有保证区间长度之和。为了减少信息量的浪费，容易想到用莫队合理利用信息。因为我习惯于写只增加的回滚莫队，所以我一直在考虑如何增加一个点。你会发现增加一个点 是不太容易的，大致有以下几种情况。

1. 与虚树根的 是一个新的点（ 或其他点）。
2. 与虚树根的 ​ 是虚树根，但 不在虚树的任意一条路径上。
3. 与虚树根的 是虚树根，但 ​ 在虚树的一条路径上。

第一种情况是容易处理的，只要在原树上处理好，那贡献就是 。

第二三种情况只在于判断后者条件，毕竟第三种情况是没有贡献的。而后者条件的判断似乎就是想在虚树找一条链去包含 ​，而链包含 ​ 是可以利用 ​ 序的，即在每一个节点处记录它的一个儿子最深的 ​，然后在构造虚树的时候将虚树节点的 ​ 序排序好，那我们就可以找 ​ 的前驱与后继来判断了。同时我们也能借此算出贡献，因为第二种情况的贡献是 ​​​ 与它到根的路径上的第一个在虚树的节点的距离，那我们分别对前驱后继取 ​，那较深的那个点就是我们想找的点（这个证明可以手动画图讨论，大概只有三类情况）。

于是我们就做好了添加一个点的所有预备工作。

那我们看一下这个复杂度，找前驱后继，还要插入一个点到虚树的 序里，似乎用平衡树是平凡的，但带个 ，这个 真的可以优化掉吗？

这就是我个人的 stereotype 了，我常以为添加一个信息会比删去一个信息来得容易，而这题却恰恰相反。实际上，若我们用一个 list 来维护 序的话，找前驱后继，删除，这些操作会显得相当的简单，而这个的复杂度也就被降到 。凑巧，我们回滚莫队能只添加也能只删除，于是就成功在 ​ 的复杂度内完成了这道题。

希望这道题能改变我一些问题的思考方向！

（代码实现比较参考 std 了属于是，因为开始没懂它是怎么去 的

//2021.8.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
const int S=256;
namespace MAIN{
    int n,m;
    struct E{
        int next,to,val;
        E() {}
        E(res next,res to,res val):next(next),to(to),val(val) {}
    }edge[N<<1];
    int head[N],cnt;
    inline void addedge(const res &u,const res &v,const res &w){
        edge[++cnt]=E(head[u],v,w),head[u]=cnt;
        edge[++cnt]=E(head[v],u,w),head[v]=cnt;
    }
    int dfn[N],idx,pos[N],dep[N],lg[N];
    int pre[N],nxt[N];
    int dis[N],tot;
    int tmp;
    void dfs(res x,res fax){
        pos[dfn[x]=++idx]=x,dep[x]=dep[fax]+1;
        nxt[pre[x]=tmp]=x,tmp=x;
        for(res i=head[x];i;i=edge[i].next){
            res tox=edge[i].to;
            if(tox==fax)continue;
            dis[tox]=dis[x]+edge[i].val,tot+=edge[i].val,dfs(tox,x),pos[++idx]=x;
        }
    }
    int lca[N][21];
    inline int get_lca(const res &u,const res &v){
        res l=dfn[u],r=dfn[v];
        if(l>r)swap(l,r);
        res d=lg[r-l+1],x=lca[l][d],y=lca[r-(1<<d)+1][d];
        return dep[x]<dep[y]?x:y;
    }
    struct Que{
        int l,r,id;
        Que() {}
        Que(res l,res r,res id):l(l),r(r),id(id) {}
        inline bool operator < (const RG Que &B) const {
            return l/S!=B.l/S?l<B.l:r>B.r;
        }
    }que[N];
    Pair st[N];
    int top;
    inline void add(){
        tot=st[top].se;
        res x=st[top].fi;
        pre[nxt[nxt[pre[x]]=x]]=x,top--;
    }
    inline void del(const res &x){
        st[++top]=mp(x,tot);
        res l=pre[x],r=nxt[x];
        if(l&&r)tot-=dis[x]-max(dis[get_lca(l,x)],dis[get_lca(x,r)]),pre[nxt[l]=r]=l;
        else {
            res plca=get_lca(nxt[0],pre[0]);
            pre[nxt[l]=r]=l;
            res clca=get_lca(nxt[0],pre[0]);
            if(clca==plca){
                if(l)tot-=dis[x]-dis[get_lca(l,x)];
                else tot-=dis[x]-dis[get_lca(x,r)];
            }
            else tot-=dis[x]+dis[clca]-2*dis[plca];
        }
    }
    int ans[N];
    inline void MAIN(){
        for(res i=2;i<=N-10;i++)lg[i]=lg[i>>1]+1;
        res Case=read();
        while(Case--){
            n=read(),m=read(),cnt=idx=0;
            for(res i=1;i<=n;i++)head[i]=0;
            for(res i=1;i<n;i++){
                res u=read(),v=read(),w=read();
                addedge(u,v,w);
            }
            tmp=tot=top=0,dfs(1,0),nxt[pre[0]=tmp]=0;
            for(res i=1;i<=idx;i++)lca[i][0]=pos[i];
            for(res j=1;j<=20;j++)for(res i=1;i+(1<<j)-1<=idx;i++){
                res u=lca[i][j-1],v=lca[i+(1<<(j-1))][j-1];
                lca[i][j]=dep[u]<dep[v]?u:v;
            }
            for(res i=1;i<=m;i++){
                res l=read(),r=read();
                que[i]=Que(l,r,i);
            }
            sort(que+1,que+m+1);
            for(res l=1,r=n,i=1;i<=m;i++){
                res L=que[i].l,R=que[i].r,pl=max(1,L/S*S);
                if(l<pl){
                    for(;r<n;r++)add();
                    while(l<pl)del(l),l++;
                }
                while(r>R)del(r),r--;
                while(l<L)del(l),l++;
                ans[que[i].id]=tot*2;
                for(;l>pl;l--)add();
            }
            for(res i=1;i<=m;i++)printf("%d\n",ans[i]);
        }
    }
}