loj 随机做题

玩一下随机做题好了。

看大火都有难度标识，我也整个好了，打分类似贴吧的，五分制。（ 主要不了解 CF 的评分，而且我评判肯定是相当不准确的

不是自己写出来的会打颗星。

[loj2250]

Tag & Difficulty

Tag: 仙人掌、dp | Difficulty: 三

solution

做法：一般仙人掌的题都是先考虑树上咋做，再不济也能转个圆方树，所以先看看树。

容易想到题意可以转换成选出若干条边不相交链的方案数。这东西直接 dp，即设 表示 的子树内不算父亲边的方案数， 表示 的子树内算父亲边的方案数。转移并不困难，考虑儿子之间匹配情况就行了。

更进一步，我们可以发现考不考虑父亲边的意义都不大。因为对于一个点而言，它考虑父亲边也要拿去匹配，不考虑也可以隐性地放置而不去理睬。也就是说，我们可以大胆地考虑直接匹配儿子，因为如果实质上我们并没有选取这个儿子的父亲边，也可以隐性地认为与它匹配的也没有选取，如果选取了，那对应地也选取了。即设 表示 个元素两两匹配的方案数，其中未匹配的元素处于待匹配状态。这样考虑儿子间的匹配情况的话，选取则是待匹配与待匹配合并，而不选取也有已匹配和待匹配合并来完成双射。转移式很显然了，是 ，于是全部乘起来就算完了。

而仙人掌情况在转换完题意就结束了。环上的边都不能使用，于是去掉所有环上的边，剩下来的连通块都是树，各做一遍就好了。时间复杂度 。

//2022.2.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
int f[N];
namespace MAIN{
    int n,m;
    vector<int> G[N];
    int dfn[N],fa[N],tim,du[N];
    int vis[N];
    int fl;
    void dfs(res x){
        dfn[x]=++tim;
        for(auto tox:G[x]){
            if(tox==fa[x])continue;
            if(!dfn[tox])fa[tox]=x,dfs(tox);
            else if(dfn[tox]>dfn[x]) {
                for(res now=tox;now!=x;now=fa[now]){
                    if(vis[now]){fl=1;return;}
                    vis[now]=1,du[now]-=2;
                }
                du[x]-=2;
            }
            if(fl)return;
        }
    }
    inline void MAIN(){
        n=read(),m=read();
        for(res i=1;i<=n;i++)vector<int>().swap(G[i]),du[i]=vis[i]=fa[i]=dfn[i]=0;
        for(res i=1;i<=m;i++){
            res u=read(),v=read();
            G[u].pb(v),G[v].pb(u);
            du[u]++,du[v]++;
        }
        fl=tim=0,dfs(1);
        if(fl){puts("0");return;}
        res ans=1;
        for(res i=1;i<=n;i++)ans=mul(ans,f[du[i]]);
        printf("%d\n",ans);
    }
}
int main(){
    f[0]=f[1]=1;
    for(res i=2;i<=N-10;i++)f[i]=Add(f[i-1],mul(i-1,f[i-2]));
    res Case=read();
    for(res T=1;T<=Case;T++)MAIN::MAIN();
    return 0;
}

[loj545]

Tag & Difficulty

Tag: 贪心、STL | Difficulty: 思维二，代码实现三

solution

做法：说下我的思路历程。

开始我并没有注意到两个相等的数异或这件事，我先是注意到一定要是 的 最大的和 的 最小的组合，这样减去的会是最多。又因为二进制的特殊性，我也可以证明这样一定是最优的，然后交上去零分。

再想了一下，发现两个相等的数的异或可以更小。于是不加证明地，我猜想每次选择这两种情况中最大的那个一定是最优的，事实证明是这样的，证明也并不复杂。

实现时，不知道为什么 deque 的空间会爆，把其改成 vector 就空间绰绰有余，这是为啥啊。

时间复杂度 或 ，我写的前者。

坑：把所有零先行去掉。

//2022.2.7 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1200000+10;
namespace MAIN{
    int n,m;
    int a[N],b[N];
    inline bool cmpa(const res &x,const res &y){
        return lowbit(x)>lowbit(y);
    }
    inline bool cmpb(const res &x,const res &y){
        return lowbit(x)<lowbit(y);
    }
    map<int,vector<int> > B,A;
    bool va[N],vb[N];
    LL ans;
    inline void MAIN(){
        n=read();
        res nn=0;
        for(res i=1;i<=n;i++){
            res x=read();
            if(x)a[++nn]=x,ans+=lowbit(x);
        }
        n=nn,nn=0;
        m=read();
        for(res i=1;i<=m;i++){
            res x=read();
            if(x)b[++nn]=x;
        }
        m=nn;
        res k=read();
        sort(b+1,b+m+1,cmpb);
        sort(a+1,a+n+1,cmpa);
        for(res i=1;i<=m;i++)B[b[i]].pb(i);
        for(res i=1;i<=n;i++)A[a[i]].pb(i);
        res na=1,nb=1,now=1;
        for(res i=1;i<=k;i++){
            while(va[na]&&na<=n)na++;
            while(vb[nb]&&nb<=m)nb++;
            if(na>n||nb>m)break;
            res ret=-lowbit(b[nb])+lowbit(a[na]);
            while(now<=n&&(va[now]||B[a[now]].empty()||vb[B[a[now]].back()])){
                if(va[now]){
                    A[a[now]].pop_back();
                    while(!B[a[now]].empty()&&vb[B[a[now]].back()])B[a[now]].pop_back();
                    now++;
                }
                else {
                    while(!B[a[now]].empty()&&vb[B[a[now]].back()])B[a[now]].pop_back();
                    if(B[a[now]].empty())now++;
                }
            }
            if(now>n){
                if(ret<=0)break;
                ans-=ret,va[na]=1,vb[nb]=1;
            }
            else {
                res v=lowbit(a[now]);
                if(v>ret){
                    ans-=v,va[now]=1,vb[B[a[now]].back()]=1;
                }
                else {
                    ans-=ret,va[na]=1,vb[nb]=1;
                }
            }
        }
        printf("%lld\n",ans);
    }
}

[loj6073]

Tag & Difficulty

Tag: 可持久化线段树、重链剖分 | Difficulty: 三

solution

做法：太久没写数据结构了，这种题都差点不会了。

首先可以注意到信息是可加减的，即题目所求的可以改成 ，其中 表示该点到根路径上的 和，而 表示那个 。那么我们只要对每个点求出它的 即可。

而对每个点而言，它的 可以由它父亲继承绝大部分，然后加上自己的 。而 的求法是显然的，继续拆成到根的路径，即 。前者和中间的都是容易的，而后者因为 不固定的情况下并不容易求。我们再对 进行转化，可以注意到，对每个 而言，想要求 不一定需要知道 是谁，若在一棵边权几乎全为 的树上，仅将 到根的路径的边权赋上，那么 就等于 到根的路径长度和。更进一步，若干个点与 的 也可以这样处理。这样的话，某点到根的距离我们用重链剖分拆成 段，每一段都是在线段树上连续的一段区间，然后加入一个新的点就等价于链加。发现修改的只有线段树，而这都可以用可持久化线段树来继承。于是就做完了。时间复杂度 。

实现时，可持久化下传标记确实有点麻烦，还是写了标记永久化。（ 主要担心爆空间哦 ）

//2022.2.7 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,q;
    int p[N];
    vector<Pair> G[N];
    LL lastans;
    int ls[N*120],rs[N*120],tot;
    LL sum[N*120],psum[N];
    int tag[N*120];
    int fav[N];
    int dfn[N],low[N],pos[N],sz[N],son[N],idx,top[N],fa[N];
    int Dep[N];
    LL dep[N],dis[N];
    void modify(res &rt,res RT,res l,res r,const res &L,const res &R){
        rt=++tot;
        ls[rt]=ls[RT],rs[rt]=rs[RT],sum[rt]=sum[RT]+psum[min(r,R)]-psum[max(l,L)-1],tag[rt]=tag[RT];
        if(L<=l&&r<=R){tag[rt]++;return;}
        res mid=(l+r)>>1;
        if(L<=mid)modify(ls[rt],ls[RT],l,mid,L,R);
        if(R>mid)modify(rs[rt],rs[RT],mid+1,r,L,R);
    }
    LL query(res rt,res l,res r,const res &L,const res &R){
        if(!rt)return 0ll;
        if(L<=l&&r<=R)return sum[rt];
        res mid=(l+r)>>1;
        RG LL ret=(psum[min(r,R)]-psum[max(l,L)-1])*tag[rt];
        if(L<=mid)ret+=query(ls[rt],l,mid,L,R);
        if(R>mid)ret+=query(rs[rt],mid+1,r,L,R);
        return ret;
    }
    int rt[N];
    void dfs(res x,res fax){
        sz[x]=1,fa[x]=fax;
        for(auto [tox,c]:G[x]){
            if(tox==fax)continue;
            Dep[tox]=Dep[x]+1,dep[tox]=dep[x]+c,fav[tox]=c,dfs(tox,x),sz[x]+=sz[tox];
            if(sz[tox]>sz[son[x]])son[x]=tox;
        }
    }
    void dfs_top(res x,res topx){
        top[pos[dfn[x]=++idx]=x]=topx;
        psum[idx]=psum[idx-1]+fav[x];
        dis[x]=dis[fa[x]]+dep[p[x]];
        if(son[x])dfs_top(son[x],topx);
        for(auto [tox,c]:G[x]){
            if(tox==fa[x]||tox==son[x])continue;
            dfs_top(tox,tox);
        }
        low[x]=idx;
    }
    void dfs(res x){
        rt[x]=rt[fa[x]];
        for(res y=p[x];y;y=fa[top[y]])modify(rt[x],rt[x],1,n,dfn[top[y]],dfn[y]);
        for(auto [tox,c]:G[x]){
            if(tox==fa[x])continue;
            dfs(tox);
        }
    }
    inline int glca(res u,res v){
        for(;top[u]!=top[v];u=fa[top[u]])if(Dep[top[u]]<Dep[top[v]])swap(u,v);
        return dep[u]<dep[v]?u:v;
    }
    inline LL f(const res &u,const res &k){
        RG LL ret=dis[u]+dep[k]*Dep[u];
        for(res x=k;x;x=fa[top[x]])ret-=query(rt[u],1,n,dfn[top[x]],dfn[x])*2;
        return ret;
    }
    inline void MAIN(){
        res typ=read();
        n=read(),q=read();
        for(res i=1;i<n;i++){
            res u=read(),v=read(),w=read();
            G[u].pb(mp(v,w)),G[v].pb(mp(u,w));
        }
        for(res i=1;i<=n;i++)p[i]=read();
        dfs(1,0),dfs_top(1,1),dfs(1);
        while(q--){
            LL u0=Read(),v0=Read(),k0=Read();
            res u,v,k;
            if(typ)u=(int)(u0^lastans),v=(int)(v0^lastans),k=(int)(k0^lastans);
            else u=(int)(u0),v=(int)(v0),k=(int)(k0);
            RG LL ans=f(u,k)+f(v,k);
            res lca=glca(u,v);
            ans-=f(lca,k)*2;
            res X=p[lca];
            ans+=dep[X]+dep[k]-dep[glca(X,k)]*2;
            printf("%lld\n",lastans=ans);
        }
    }
}

[loj2655]

Tag & Difficulty

Tag: 结论 | Difficulty: 二

solution

做法：可以猜一个结论，所有点一定是在 的同一侧时更优，证明也很容易，假设此刻所有点都是 ，而答案显然是 ，若翻转了某个点，则它现在的 只能变得更小， 只能变得更大。若它原本的 本就不是最小和最大，那么翻转一定更不优。若是，比如 是最小，那么翻转之后则将 变成它原本的 ，而 虽然变大了，但由于 ，则新的 一定小于原来的 ，则总答案更不优。同理，我们就证出了这个结论。

但这并不一定是最优的最小花费，但由于边长已经固定了，那么一共只有 种选取矩形四个点的方式，暴力判一下就好了。时间复杂度 。

//2022.2.8 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 n;
#define tup tuple<int,int,int>
    tup a[N];
    int ans=inf;
    int fl[N],Ans[N];
    inline void solve(const res &L,const res &R,const res &U,const res &D){
        res ret=0;
        for(res i=1;i<=n;i++){
            fl[i]=0;
            auto [x,y,c]=a[i];
            if(L<=x&&x<=R&&D<=y&&y<=U);
            else {
                swap(x,y);
                if(L<=x&&x<=R&&D<=y&&y<=U)ret+=c,fl[i]=1;
                else return;
            }
        }
        if(ans>ret){
            for(res i=1;i<=n;i++)Ans[i]=fl[i];
            ans=ret;
        }
    }
    int L,R,U,D;
    inline void MAIN(){
        n=read(),L=inf,R=-inf,U=-inf,D=inf;
        for(res i=1;i<=n;i++){
            res x=read(),y=read(),c=read();
            a[i]=tup(x,y,c);
            if(x>y)swap(x,y);
            L=min(L,x),R=max(R,x),U=max(U,y),D=min(D,y);
        }
        solve(L,R,U,D),solve(D,R,U,L),solve(L,U,R,D),solve(D,U,R,L);
        printf("%lld %d\n",((LL)R-L+U-D)*2,ans);
        for(res i=1;i<=n;i++)printf("%d",Ans[i]);
    }
}

[loj3082*]

Tag & Difficulty

Tag: 线段树、二分 | Difficulty: 五

solution

做法：呃呃，要捋清楚再写出来有点累哦。

首先我们能判断出水流的方向，只要看开孔的两侧谁的水比较高就谁从哪一边流过去（ 当然首先得判断孔高度是否大于水 ），不失一般性地，我们假设水从左往右流。

模拟一下水流的过程，大致可以分为三步。设开孔处为 与 之间，修改成 ，水高为 ，孔高为 。

最开始，左边和 连通的水会一起往左流。连通这里也是容易定义的，即水高一致且比每一个孔都要高。

然后，把所有右边与 相连的坑填满。

最后，把还剩下的水继续推平。

为了方便，我们将这三个步骤抽象成比较合理的形式语言。

设 表示 ， 表示将 的水清空后，要往 中加多少水才能使 的水高变成 ， 表示修改 的水，将其变成执行完 的样子。更形式化地， 可以用后缀最大值表示，即

$$FL(l,r,h)=\sum_{i=l}^r \max(h,\max_{j=i}^{r-1} c_j)$$

接下来将三个步骤表示下。

第一步则是找到 ，使得 连通，即对所有的 ，满足 相等且对所有的 ，有 。同时设 ，并执行 。

第二步则是找到最大的 ，使得 。这步操作即找到会填的所有坑。

第三步我们除了推平，同时要修正第一步的错误，因为 处的水高不一定是 ，所以我们要找出真实的水高。设 处真实的水高为 ，那么它的限制条件就是找到最大的 ，使得 ，然后再执行 。

形式化之后，我们要做的就是维护这三个操作了， 看起来是容易的，而 显得有点怪异。由于是区间操作，我们会想用线段树维护，那么就得考虑中点有什么性质。

根据 的意义，我们可以推出一个式子，即

$$FL(l,r,h)=FL(m+1,r,h)+FL(l,m,\max(h,\max_{j=m}^{r-1}c_j))$$

看起来没啥用，毕竟直接递归这还是寄完了的。但是，通过观察，可以发现一个非常好的性质。

当 时，后者变成了 ，前者似乎没变化，但由于已经大于区间内所有孔高了，那么它一定是全部填到 ，所以前者此时等于 。

当 ，前者没啥变化，但后者直接变成 ，这东西与 无关，那么在线段树上我们对每个区间算好这个东西就可以了。

于是递归永远只用递归一边，那么复杂度就是 。说白了，这东西叫线段树上二分。

修改就直接打标记即可。为了每次都算 ，那么时间复杂度就是 。

最后考虑找这个 ，发现这些东西都具有二分性，且都可以放在线段树上二分，所以总复杂度就是 。

呃呃，代码还在路上，这几天事情比较多，估计要一会儿写。

[loj2829]

Tag & Difficulty

Tag: 贪心 | Difficulty: 二

solution

做法：可以注意到与 的大小与前面考生的选择无关，只与当前考生的选择有关。不妨设往前 是 ，往后是 。

再注意到 的贡献与当前考生的即时选择无关，即若选择往前的人的个数是固定的，那 的贡献也是固定的。设往前的人数为 ，那么 的贡献就是 。发现这东西是单峰的。另一方面，若将所有考生按 排序后，则一定存在一个分界点，分界点前全部选择往前，使得这个式子取到最小。因为 的贡献这样是单调的， 的贡献是单峰的，于是就做完了。算这个 等于动态维护前缀和，树状数组即可。时间复杂度 。

//2022.2.11 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,A,B;
    int tr[N];
    inline void modify(const res &x,const res &y){
        for(res i=x;i<=n;i+=lowbit(i))tr[i]+=y;
    }
    inline int query(const res &x){
        res ret=0;
        for(res i=x;i;i-=lowbit(i))ret+=tr[i];
        return ret;
    }
    int b[N][6];
    Pair a[N];
    inline bool cmp(const RG Pair &x,const RG Pair &y){
        return x.fi-x.se<y.fi-y.se;
    }
    LL sum[N][2];
    inline void MAIN(){
        n=read(),m=read(),A=read(),B=read();
        for(res i=1;i<=m;i++){
            res x;
            char y;
            scanf("%d%c",&x,&y);
            y-='A';
            res ret=0;
            for(res j=y+1;j<2;j++)ret+=b[x][j]^1;
            for(res j=y-1;j>3;j--)ret+=b[x][j]^1;
            if(y==2)modify(x,1);
            if(y==3)modify(x,1);
            a[i]=mp(ret+2*x-query(x),ret+2*(n-x+1)-(query(n)-query(x-1)));
            b[x][y]^=1;
        }
        sort(a+1,a+m+1,cmp);
        for(res i=1;i<=m;i++)sum[i][0]=sum[i-1][0]+a[i].fi;
        for(res i=m;i;i--)sum[i][1]=sum[i+1][1]+a[i].se;
        LL ans=INF;
        for(res i=0;i<=m;i++){
            LL ret=(sum[i][0]+sum[i+1][1])*A+((LL)i*(i-1)+(LL)(m-i)*(m-i-1))/2*B;
            ans=min(ans,ret);
        }
        printf("%lld\n",ans);
    }
}

[loj2000]

Tag & Difficulty

Tag: 莫比乌斯反演、整除分块 | Difficulty: 二

solution

做法：呃呃，一上来就把乘积看成加法了，虽然差不多。

直接推式子就行了，远古题还是比较容易推的。

$$\begin{align*} &\prod_{i=1}^n\prod_{j=1}^m f_{\gcd(i,j)}\\ &\prod_{i=1}^n\prod_{j=1}^m\prod_{d=1}^n f_d^{[\gcd(i,j)=d]}\\ &\prod_{d=1}^nf_d^{\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]}\\ &\prod_{d=1}^nf_d^{\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]}\\ &\prod_{d=1}^nf_d^{\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{p|i,p|j}\mu_p}\\ &\prod_{d=1}^nf_d^{\sum_{p=1}^n \mu_p \lfloor\frac{n}{d\cdot p}\rfloor\lfloor\frac{m}{d\cdot p}\rfloor}\\ &\prod_{p=1}^n \prod_{d|p}^nf_d^{\mu_{\frac{p}{d}} \lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor}\\ &\prod_{p=1}^n (\prod_{d|p}^nf_{\frac{p}{d}}^{\mu_{d}})^{\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor}\\ &\prod_{p=1}^n (g_p)^{\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor}\\ &\end{align*}$$

其中 是 和 的狄利克雷卷积，直接算就是调和级数的 。而指数上的东西显然的整除分块，所以就是预处理 ，单次 。

//2022.2.13 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
int prim[N],vis[N],tot,mu[N],f[N],If[N];
int g[N],sg[N],Ig[N];
namespace MAIN{
    inline void MAIN(){
        res n=read(),m=read();
        res ans=1;
        for(res l=1,r;l<=min(n,m);l=r+1){
            r=min(n/(n/l),m/(m/l));
            ans=mul(ans,qpow(mul(sg[r],Ig[l-1]),int((LL)(n/l)*(m/l)%(kcz-1))));
        }
        printf("%d\n",ans);
    }
}
int main(){
    f[1]=If[1]=mu[1]=1;
    for(res i=2;i<=N-10;i++){
        f[i]=Add(f[i-1],f[i-2]),If[i]=qpow(f[i]);
        if(!vis[i])prim[++tot]=i,mu[i]=-1;
        for(res j=1;j<=tot&&prim[j]*i<=N-10;j++){
            vis[prim[j]*i]=1;
            if(i%prim[j]==0)break;
            mu[prim[j]*i]=-mu[i];
        }
    }
    for(res i=1;i<=N-10;i++)g[i]=1;
    for(res d=1;d<=N-10;d++){
        if(!mu[d])continue;
        for(res i=d;i<=N-10;i+=d){
            g[i]=mul(g[i],mu[d]==1?f[i/d]:If[i/d]);
        }
    }
    sg[1]=g[1];
    for(res i=2;i<=N-10;i++)sg[i]=mul(g[i],sg[i-1]);
    Ig[N-10]=qpow(sg[N-10]);
    for(res i=N-11;i>=1;i--)Ig[i]=mul(Ig[i+1],g[i+1]);
    Ig[0]=1;
    res Case=read();
    for(res T=1;T<=Case;T++)MAIN::MAIN();
    return 0;
}

[loj6182]

Tag & Difficulty

Tag: LCP、动态规划 | Difficulty: 三

solution

做法：先讲点正常的做法。

枚举两串后，设 表示前一个串匹配到 的位置后匹配到 的位置的最小操作次数，那么转移就是

$$f_{i,j}=\min\lbrace f_{i-1,j}+1,f_{i,j-1}+1,f_{i-1,j-1}+[a_i\neq b_j]\rbrace$$

这样复杂度是 的，注意到题目要求的只有 的答案，于是改写 ，即设 表示 ，可以证明 。这样复杂度就是 ，依然不太行。

注意到 的值域也很小，于是再度改写，设 表示最大的 使得 。正确性显然，然后重新整一下转移，即

$$h_{i,j}=\max\lbrace h_{i-1,j-1},h_{i-1,j+1}+1,h_{i-1,j}+1\rbrace+\mathrm{LCP(...,...)}$$

用后缀数组即可维护，于是总复杂度就降到了 。

然后一看其他人代码，会立刻发现有不少求 都是暴力求的，而且快了无数倍，这下呃呃了。

//2022.2.13 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+200+10;
namespace MAIN{
    int str[N];
    char s[N];
    int n,L;
    int rnk[N],buc[N],sa[N],hei[N],fr[N],sc[N],m;
    inline void get_SA(){
        m=10000;
        for(res i=1;i<=n;i++)buc[fr[i]=str[i]]++;
        for(res i=2;i<=m;i++)buc[i]+=buc[i-1];
        for(res i=n;i;i--)sa[buc[fr[i]]--]=i;
        for(res k=1;k<=n;k<<=1){
            res num=0;
            for(res i=n-k+1;i<=n;i++)sc[++num]=i;
            for(res i=1;i<=n;i++)if(sa[i]>k)sc[++num]=sa[i]-k;
            memset(buc,0,sizeof(buc));
            for(res i=1;i<=n;i++)buc[fr[i]]++;
            for(res i=2;i<=m;i++)buc[i]+=buc[i-1];
            for(res i=n;i;i--)sa[buc[fr[sc[i]]]--]=sc[i],sc[i]=0;
            swap(fr,sc);
            fr[sa[1]]=1;
            num=1;
            for(res i=2;i<=n;i++)fr[sa[i]]=(sc[sa[i]]==sc[sa[i-1]]&&sc[sa[i]+k]==sc[sa[i-1]+k])?num:++num;
            if(num==n)break;
            m=num;
        }
    }
    inline void get_hei(){
        res k=0;
        rnk[sa[1]]=1;
        for(res i=2;i<=n;i++)rnk[sa[i]]=rnk[sa[i-1]]+(fr[sa[i]]!=fr[sa[i-1]]||sc[sa[i]]!=sc[sa[i-1]]);
        for(res i=1;i<=n;i++){
            if(rnk[i]==1)continue;
            if(k)k--;
            res j=sa[rnk[i]-1];
            while(j+k<=n&&i+k<=n&&str[i+k]==str[j+k])k++;
            hei[rnk[i]]=k;
        }
    }
    int st[N][21];
    inline void PRE(){
        for(res i=1;i<=n;i++)st[i][0]=hei[i];
        for(res j=1;j<=20;j++)
            for(res i=1;i+(1<<j)-1<=n;i++)
                st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    }
    int Lg[N];
    inline int query_min(res l,res r){
        res k=Lg[r-l];
        return min(st[l][k],st[r-(1<<k)+1][k]);
    }
    inline int LCP(const res &l,const res &r){
        if(l==r)return n-l+1;
        res x=rnk[l],y=rnk[r];
        if(x>y)swap(x,y);
        return query_min(x+1,y);
    }
    inline void pre(){
        for(res i=2;i<=n;i++)Lg[i]=Lg[i>>1]+1;
        get_SA(),get_hei(),PRE();
    }
    int pos[N],le[N];
    int ans[10];
    int f[9][17];
    inline int solve(res I,res J){
        if(le[I]<le[J])swap(I,J);
        res l0=le[I],l1=le[J];
        if(l0<l1-8||l1<l0-8)return 9;
        for(res i=0;i<=8;i++)for(res j=0;j<=16;j++)f[i][j]=-n-10;
        f[0][8]=LCP(pos[I],pos[J]);
        if(l0==l1&&f[0][8]>=l0)return 0;
        for(res i=1;i<=8;i++){
            for(res j=0;j<=16;j++){
                res ret=f[i-1][j]+1;
                if(j!=0)ret=max(ret,f[i-1][j-1]);
                if(j!=16)ret=max(ret,f[i-1][j+1]+1);
                if(ret+j-8<0)continue;
                if(ret<l0&&ret+j-8<l1)ret+=LCP(pos[I]+ret,pos[J]+ret+j-8);
                f[i][j]=ret;
            }
            if(f[i][8+l1-l0]==l0)return i;
        }
        return 9;
    }
    inline void MAIN(){
        L=read();
        for(res i=1;i<=L;i++){
            scanf("%s",s+1);
            res len=(int)strlen(s+1);
            pos[i]=n+1,le[i]=len;
            for(res j=1;j<=len;j++)str[++n]=s[j];
            str[++n]=i;
        }
        pre();
        for(res i=1;i<=L;i++)for(res j=i+1;j<=L;j++)ans[solve(i,j)]++;
        for(res i=1;i<=8;i++)printf("%d ",ans[i]);
        puts("");
    }
}

[loj3025]

Tag & Difficulty

Tag: 模拟、STL | Difficulty: 一

solution

做法：直接模拟就行了，将已经发出信号按楼层高低排序，往下会不会碰到直接判就行了。这些动态排序都可以用各种 STL 维护。时间复杂度 。

//2022.2.13 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;
#define tup tuple<int,int,int>
    tup a[N];
    LL ans[N];
    priority_queue<Pair,vector<Pair>,greater<>> Q;
    int vis[N];
    inline void MAIN(){
        n=read(),m=read();
        for(res i=1;i<=n;i++){
            res t=read(),d=read();
            a[i]=tup(t,i,d);
        }
        sort(a+1,a+n+1);
        res l=1,r=1;
        LL nowt=0;
        while(233){
            while(vis[get<1>(a[l])]&&l<=n)l++;
            if(l>n)break;
            auto [t,i,d]=a[l];
            vector<int> A;
            A.pb(i);
            while(!Q.empty()){
                auto [D,I]=Q.top();
                if(D>d)break;
                A.pb(I),Q.pop();
            }
            LL nt=max(nowt,(LL)t)+d-1;
            nowt=nt+d-1;
            while(r<=n){
                if(get<0>(a[r])>nowt)break;
                auto [T,I,D]=a[r];
                if(D>d||nt+d<T+D)Q.push(mp(D,I));
                else A.pb(I);
                r++;
            }
            for(auto x:A)ans[x]=nowt,vis[x]=1;
        }
        for(res i=1;i<=n;i++)printf("%lld\n",ans[i]);
    }
}

[loj2320]

Tag & Difficulty

Tag: 多项式各种操作、prufer 序列 | Difficulty: 三点五

solution

做法：看到生成树计数，不是矩阵树就是 prufer 序列。我是先考虑的矩阵树定理，然后发现确实不太难构造出边权，所以就遗憾放弃了。于是就考虑 prufer 序列，推一推式子就出来了。

首先可以把连通块看成点， 看成点权，那么连一条边的贡献就是两个端点的点权之积，于是就轻松地写出第一条式子，并用 prufer 序列推导，即

$$\begin{align*} &\sum_T \prod_{(u,v)} (a_ua_v)(\sum d_i^m)(\prod d_i^m)\\ &=\sum_T \prod a_i^{d_i}d_i^m(\sum d_i^m)\\ &=\sum_{\sum d_i=n-2} \frac{(n-2)!}{\prod d_i!} \prod a_i^{d_i+1}(d_i+1)^m(\sum (d_i+1)^m)\\ &=(n-2)!\sum_{\sum d_i=n-2} \prod \frac{a_i^{d_i+1}(d_i+1)^{m+1}}{(d_i+1)!}(\sum (d_i+1)^m)\\ &=(n-2)!\sum_{\sum d_i=n-2} \sum (d_i+1)^m\prod \frac{a_j^{d_j+1}(d_j+1)^{m+1}}{(d_j+1)!}\\ &=(n-2)!\sum_{\sum d_i=n-2} \sum \frac{a_i^{d_i+1}(d_i+1)^{2m+1}}{(d_i+1)!}\prod_{j\neq i} \frac{a_j^{d_j+1}(d_j+1)^{m+1}}{(d_j+1)!}\\ &=(n-2)!\prod a_i\sum_{\sum d_i=n-2} \sum \frac{a_i^{d_i}(d_i+1)^{2m+1}}{(d_i+1)!}\prod_{j\neq i} \frac{a_j^{d_j}(d_j+1)^{m+1}}{(d_j+1)!}\\ &\end{align*}$$

推到这一步可以说是结束了，把前者看成一个多项式，后者看成一个多项式，那么 就是个卷积，即

$$\begin{align*} &A(x)=\sum \frac{(i+1)^mx^i}{i!}\\ &B(x)=\sum \frac{(i+1)^{2m}x^i}{i!}\\ &\end{align*}$$

那么答案就是

$$(n-2)!\prod a_i [x^{n-2}] (\sum \frac{B(a_ix)}{A(a_ix)})(\prod A(a_ix))$$

后者取 后，与前者是一个形式。于是问题就转化成

已知 ，求 。设 ，那么要求的就是 。

这个东西也比较经典了，直接提取系数，即求 。而 也是很简单的东西了，直接分治+FFT ，即模拟通分的过程或者积分。

于是总复杂度 。

不要问我为什么代码这么怪，主要还是之前的多项式板子有点问题，导致边写边改，希望以后能写个正常的板子出来。

//2022.2.13 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    int pos[N],inv[N];
    inline void NTT(poly &A,const res &type,const res &lim){
        for(res i=0;i<lim;i++)if(i<pos[i])swap(A[i],A[pos[i]]);
        for(res mid=1;mid<lim;mid<<=1){
            res wn=qpow(type==1?G:GI,(kcz-1)/(mid<<1));
            for(res j=0;j<lim;j+=mid<<1){
                res w=1;
                for(res k=0;k<mid;k++,w=mul(w,wn)){
                    res x=A[j+k],y=mul(w,A[j+mid+k]);
                    A[j+k]=Add(x,y),A[j+mid+k]=Add(x,kcz-y);
                }
            }
        }
        if(type==-1){
            res INV=qpow(lim,kcz-2);
            for(res i=0;i<=lim;i++)A[i]=mul(A[i],INV);
        }
    }
    inline void NTT(res *A,const res &type,const res &lim){
        for(res i=0;i<lim;i++)if(i<pos[i])swap(A[i],A[pos[i]]);
        for(res mid=1;mid<lim;mid<<=1){
            res wn=qpow(type==1?G:GI,(kcz-1)/(mid<<1));
            for(res j=0;j<lim;j+=mid<<1){
                res w=1;
                for(res k=0;k<mid;k++,w=mul(w,wn)){
                    res x=A[j+k],y=mul(w,A[j+mid+k]);
                    A[j+k]=Add(x,y),A[j+mid+k]=Add(x,kcz-y);
                }
            }
        }
        if(type==-1){
            res INV=qpow(lim,kcz-2);
            for(res i=0;i<=lim;i++)A[i]=mul(A[i],INV);
        }
    }
    inline void derivation(const res *A,res *B,const res &lim){
        for(res i=1;i<lim;i++)B[i-1]=mul(i,A[i]);
        B[lim-1]=0;
    }
    inline void integral(const res *A,res *B,const res &lim){
        for(res i=1;i<lim;i++)B[i]=mul(A[i-1],inv[i]);
        B[0]=0;
    }
    int A[N],B[N],D[N],E[N];
    void getinv(const res *a,res *b,res lim){
        if(lim==1){b[0]=qpow(a[0]);return;}
        getinv(a,b,lim>>1);
        for(res i=0;i<lim;i++)A[i]=a[i],B[i]=b[i];
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(A,1,len),NTT(B,1,len);
        for(res i=0;i<len;i++)A[i]=mul(A[i],mul(B[i],B[i]));
        NTT(A,-1,len);
        for(res i=0;i<lim;i++)b[i]=Add(b[i],Add(b[i],kcz-A[i]));
        for(res i=0;i<len;i++)A[i]=B[i]=0;
    }
    inline void getln(const res *a,res *b,const res &lim){
        derivation(a,D,lim),getinv(a,E,lim);
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(D,1,len),NTT(E,1,len);
        for(res i=0;i<len;i++)D[i]=mul(D[i],E[i]);
        NTT(D,-1,len);
        integral(D,b,lim);
        for(res i=0;i<len;i++)D[i]=E[i]=0;
    }
    int F[N],G[N];
    void getexp(const res *a,res *b,res lim){
        if(lim==1){b[0]=1;return;}
        getexp(a,b,lim>>1);
        getln(b,G,lim);
        for(res i=0;i<lim;i++)F[i]=b[i],G[i]=Add(kcz-G[i],a[i]);
        G[0]=Add(G[0],1);
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(F,1,len),NTT(G,1,len);
        for(res i=0;i<len;i++)F[i]=mul(F[i],G[i]);
        NTT(F,-1,len);
        for(res i=0;i<lim;i++)b[i]=F[i];
        for(res i=0;i<len;i++)F[i]=G[i]=0;
    }
    int a[N];
    poly solve(res l,res r){
        poly P{};
        if(l==r){
            P.pb(1),P.pb(kcz-a[l]);
            return P;
        }
        res mid=(l+r)>>1;
        poly L=solve(l,mid),R=solve(mid+1,r);
        res lim=r-l+2;
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        L.resize(len),R.resize(len);
        NTT(L,1,len),NTT(R,1,len);
        for(res i=0;i<len;i++)P.pb(mul(L[i],R[i]));
        NTT(P,-1,len),P.resize(lim);
        return P;
    }
    int n,m;
    int b[N],c[N],finv[N],d[N];
    inline void MAIN(){
        n=read(),m=read();
        res ret=1;
        for(res i=1;i<=n;i++)a[i]=read(),ret=mul(ret,a[i]);
        for(res i=n-2;i>=1;i--)ret=mul(ret,i);
        poly P=solve(1,n);
        assert(P.size()>n);
        for(res i=0;i<=n-2;i++)b[i]=P[i];
        res l=1,qaq=0;
        while(l<=(n-1))l<<=1,qaq++;
        finv[0]=finv[1]=inv[0]=inv[1]=1;
        for(res i=2;i<=l;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i),finv[i]=mul(finv[i-1],inv[i]);
        getln(b,c,l),derivation(c,b,l);
        for(res i=n-2;i;i--)b[i]=kcz-b[i-1];
        b[0]=n;
        for(res i=0;i<=n-2;i++)a[i]=mul(qpow(i+1,m),finv[i]);
        memset(c,0,sizeof(c));
        getln(a,c,l);
        for(res i=0;i<=n-2;i++)c[i]=mul(c[i],b[i]);
        for(res i=n-1;i<l;i++)c[i]=0;
        getexp(c,d,l);
        memset(c,0,sizeof(c));
        getinv(a,c,l);
        for(res i=0;i<=n-2;i++)a[i]=mul(a[i],qpow(i+1,m));
        while(l<=2*(n-2))l<<=1,qaq++;
        for(res i=0;i<l;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        for(res i=n-1;i<l;i++)a[i]=c[i]=0;
        NTT(a,1,l),NTT(c,1,l);
        for(res i=0;i<l;i++)a[i]=mul(a[i],c[i]);
        NTT(a,-1,l);
        res ans=0;
        for(res i=0;i<=n-2;i++)add(ans,mul(mul(a[i],b[i]),d[n-2-i]));
        printf("%d\n",mul(ans,ret));
    }
}

[loj2861]

Tag & Difficulty

Tag: 类虚树 | Difficulty: 二

solution

做法：这题唯一的难点就是转化题意，仔细思考下题意到底可以改成什么。由于是凸多边形，于是切割实际上只是选择某一条边，然后分开来，而一条边最多会被两个三角形共用。那么我们将共用一条边的三角形连边后，这一定会是棵树。于是题意转化成了，给一棵树，每个点有颜色，问最多有多少个连通块，使得相同颜色的点一定在一个连通块里。对每一种颜色分别考虑，那么这种颜色构成的虚树一定在同一个连通块里。于是类似地建出虚树，树上差分维护下就好了。时间复杂度 。

//2022.2.14 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;
    map<Pair,int> M;
    vector<int> G[N];
    int F[N][21],dfn[N],idx,dep[N];
    void dfs(res x,res fax){
        F[x][0]=fax,dfn[x]=++idx;
        for(res i=1;i<=20;i++)F[x][i]=F[F[x][i-1]][i-1];
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dep[tox]=dep[x]+1,dfs(tox,x);
        }
    }
    inline int get_lca(res x,res y){
        if(dep[x]<dep[y])swap(x,y);
        res d=dep[x]-dep[y];
        for(res i=20;~i;i--)if(d&(1<<i))x=F[x][i];
        if(x==y)return x;
        for(res i=20;~i;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
        return F[x][0];
    }
    vector<int> A[N];
    LL f[N];
    void dfs_f(res x,res fax){
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dfs_f(tox,x),f[x]+=f[tox];
        }
    }
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n-2;i++){
            res a=read(),b=read(),c=read(),d=read();
            if(a>b)swap(a,b);
            if(b>c)swap(b,c);
            if(a>b)swap(a,b);
            if(M.count(mp(a,b)))G[M[mp(a,b)]].pb(i),G[i].pb(M[mp(a,b)]);
            else M[mp(a,b)]=i;
            if(M.count(mp(b,c)))G[M[mp(b,c)]].pb(i),G[i].pb(M[mp(b,c)]);
            else M[mp(b,c)]=i;
            if(M.count(mp(a,c)))G[M[mp(a,c)]].pb(i),G[i].pb(M[mp(a,c)]);
            else M[mp(a,c)]=i;
            A[d].pb(i);
        }
        dfs(1,0);
        for(res i=1;i<=n-2;i++){
            sort(A[i].begin(),A[i].end(),[&](const res &x,const res &y){return dfn[x]<dfn[y];});
            res pre=0;
            for(auto x:A[i]){
                if(pre){
                    res lca=get_lca(pre,x);
                    f[x]++,f[pre]++,f[lca]-=2;
                }
                pre=x;
            }
        }
        dfs_f(1,0);
        res ans=0;
        for(res i=2;i<=n-2;i++)if(!f[i])ans++;
        printf("%d\n",ans);
    }
}

[loj2601]

Tag & Difficulty

Tag: 贪心 | Difficulty: 二

solution

做法：设每个景点车要离开的时间为 ，那么对于一个从 出现时间为 的人而言，它的贡献就是 。而 的式子也容易得到，即 ，其中 表示 号景点最后到的人的时间。注意到每次 减一后， 只减不增。设满足 的 为 ，那么对于某个处于 的 而言， 就会等于 。于是，我们可以写出最终答案式子，即

$$\sum_{i=1}^{n-1} a_iD_i+C$$

其中 为一固定常数，是 。

于是，我们可以发现 的贡献是独立的，且每次减少 后，会使某一段区间的 减一，并且当 取 的时候， 会减少。由于贡献独立，所以直接按 贪心就是对的了。我们用线段树来维护这一过程，那么只用维护区间最大，区间减，然后有 时暴力递归，递归时要修改当前点所在的左右区间编号，这是区间覆盖。所以总复杂度就是 。

虽然这样已经可以做了，但显然是有点麻烦，我们再改写一下前面的式子。注意到 的式子有一部分是 的区间和，我们改写成前缀和形式，即 。实际上，每次取分裂这个区间也比较难办，于是直接写出带 的式子，即

$$M_j=\max_{k=1}^j (T_k+sD_{j-1}-sD_{k-1})=sD_{j-1}+\max_{k=1}^j (T_k-sD_{k-1})$$

于是再接着改写下最终答案，即

$$\sum (sD_{j-2}+D_{j-1}+\max_{k=1}^{j-1} (T_k-sD_{k-1}))-t=\sum (sD_{j-1}+\max_{k=1}^{j-1} (T_k-sD_{k-1})))-C$$

另一方面，注意到答案已经与起点无关了，所以再度改写，即

$$-C+\sum_{j=1}^{n-1}(sD_{j}+\max_{k=1}^j (T_k-sD_{k-1}))*cnt_j$$

于是，此时对某个 减一的操作就等价于某些后缀 减一，反应到答案上就是答案减去某一段 的和。而这一段是可以直接算出来的，类似之前地，考虑某些 使得 为前缀最大值，那么选择某一点 ，就等价于答案减少 。由于 不变，所以仍然具有贪心性。这就等价于每次从最小值分裂某个区间，然后继续贪心找最大的 之和即可。时间复杂度仍然是 ，但无疑好写很多。

//2022.2.15 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;
    int D[N];
    int T[N],cnt[N],scnt[N];
#define tup tuple<int,int,int>
    priority_queue<tup> Q;
    int sD[N];
    int a[N];
    Pair mn[N<<2];
    int tag[N<<2];
    void build(res rt,res l,res r){
        if(l==r){mn[rt]=mp(a[l],l);return;}
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
        mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
    }
    inline void change(const res &rt,const res &v){
        tag[rt]+=v,mn[rt].fi+=v;
    }
    inline void pushdown(const res &rt){
        if(!tag[rt])return;
        change(rt<<1,tag[rt]),change(rt<<1|1,tag[rt]),tag[rt]=0;
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const res &v){
        if(L>R)return;
        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);
        mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
    }
    Pair query(res rt,res l,res r,const res &L,const res &R){
        if(L>R)return mp(inf,0);
        if(L<=l&&r<=R)return mn[rt];
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid&&R>mid)return min(query(rt<<1,l,mid,L,R),query(rt<<1|1,mid+1,r,L,R));
        if(L<=mid)return query(rt<<1,l,mid,L,R);
        return query(rt<<1|1,mid+1,r,L,R);
    }
    inline void MAIN(){
        n=read(),m=read(),k=read();
        LL ans=0;
        for(res i=1;i<n;i++)D[i]=read(),sD[i]=sD[i-1]+D[i];
        for(res i=1;i<=m;i++){
            res t=read(),A=read(),B=read();
            T[A]=max(T[A],t),cnt[B]++,ans-=t;
        }
        for(res i=1;i<=n;i++)scnt[i]=scnt[i-1]+cnt[i];
        res pre=1;
        for(res i=2;i<=n;i++){
            a[i]=max(0,a[i-1]+T[i-1]+D[i-1]-T[i]);
            if(!a[i])Q.push(tup(scnt[i]-scnt[pre],pre,i)),pre=i;
            ans+=(LL)cnt[i]*(a[i-1]+D[i-1]+T[i-1]);
        }
        if(pre!=n)Q.push(tup(scnt[n]-scnt[pre],pre,n));
        build(1,2,n);
        while(k>0&&!Q.empty()){
            auto [v,l,r]=Q.top();
            Q.pop();
            auto [va,p]=query(1,2,n,l+1,r-1);
            va=min({va,k,D[l]});
            ans-=(LL)va*v,k-=va;
            if(va==D[l])p=l+1;
            modify(1,2,n,l+1,r-1,-va),D[l]-=va;
            if(l<p)Q.push(tup(scnt[p]-scnt[l],l,p));
            if(p<r)Q.push(tup(scnt[r]-scnt[p],p,r));
        }
        printf("%lld\n",ans);
    }
}

[loj3083]

Tag & Difficulty

Tag: 拆位算贡献、单调栈 | Difficulty: 一点五

solution

做法：容易注意到直接算比较困难，于是考虑每一位来算。于是题意等价于找全 子矩阵的个数，这东西直接单调栈即可。时间复杂度 。

单调栈算子矩阵贡献时为了不算重，我们对于一个将要弹出栈的点只算它到两边点之间的高度，这样就不会算重了。

//2022.2.9 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e3+10;
namespace MAIN{
    int n;
    int a[N][N],h[N],st[N],top;
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)a[i][j]=read();
        res ans0=0,ans1=0,sum=Mul(n,n+1,2);
        sum=mul(sum,sum);
        for(res t=0;t<31;t++){
            res ret=0;
            for(res j=1;j<=n+1;j++)h[j]=0;
            for(res i=1;i<=n;i++){
                for(res j=1;j<=n;j++)
                    if(a[i][j]&(1<<t))h[j]++;
                    else h[j]=0;
                top=0;
                for(res j=1;j<=n+1;j++){
                    while(top&&h[st[top]]>h[j]){
                        add(ret,mul(h[st[top]]-max(h[st[top-1]],h[j]),Mul(j-st[top-1]-1,j-st[top-1],2)));
                        top--;
                    }
                    st[++top]=j;
                }
            }
            add(ans0,mul(ret,1<<t));
            ret=0;
            for(res j=1;j<=n+1;j++)h[j]=0;
            for(res i=1;i<=n;i++){
                for(res j=1;j<=n;j++)
                    if(a[i][j]&(1<<t))h[j]=0;
                    else h[j]++;
                top=0;
                for(res j=1;j<=n+1;j++){
                    while(top&&h[st[top]]>h[j]){
                        add(ret,mul(h[st[top]]-max(h[st[top-1]],h[j]),Mul(j-st[top-1]-1,j-st[top-1],2)));
                        top--;
                    }
                    st[++top]=j;
                }
            }
            add(ans1,mul(Add(sum,kcz-ret),1<<t));
        }
        printf("%d %d\n",ans0,ans1);
    }
}

[loj6104*]

Tag & Difficulty

Tag: 贪心 | Difficulty: 三

solution

做法：都转化模型了却分析不出怎么贪心啊。

首先可以注意到每一列至少要消掉最高的好点以下的所有点，那么题意转化成有序列 ，每次可以操作相邻的两个，一个减二，一个减一，最少操作次数使得全变成非正整数。然后我思考咋贪心都不会了，总感觉要维护的东西有点多。

于是就看了他人做法。注意到除了减到零的部分外，有些要减更多，减到负数部分。于是我们考虑除了减到零之后，还要多减少有几个。从左往右考虑，假设当前列最多还要操作 次，最少还要 次，对于新的一列而言，我们要考虑刚好让它掉落的情况，那么我们可以通过 和 推出新列的 和 ，而刚好掉落，就等价于选择 和 之间的某个公差为 的等差数列。但有可能新的列就算不操作也已经完成了，那么即要减到负的部分了，于是加上这部分答案即可。这样就做完了。

时间复杂度 。

//2022.2.18 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,m;
    char str[N];
    int a[N];
    inline void MAIN(){
        n=read(),m=read();
        res ans=0;
        for(res i=1;i<=n;i++){
            scanf("%s",str+1);
            for(res j=1;j<=m;j++){
                if(str[j]=='*'&&!a[j])a[j]=n-i+1,ans+=n-i+1;
            }
        }
        res mx=0,mn=0;
        for(res i=1;i<=m+1;i++){
            res nmx=a[i]-(mn/2+(mn&1)*2),nmn=a[i]-mx*2;
            if(nmx<0)ans+=-nmx,nmx=nmn=0;
            else if(nmn<0)nmn=nmx%3;
            mx=nmx,mn=nmn;
        }
        printf("%d\n",ans/3);
    }
}

[loj6432]

Tag & Difficulty

Tag: 组合数学 | Difficulty: 二

solution

做法：怎么以前 PKUSC 还有这么简单的题啊。

对每个人分别考虑，分类讨论这个人是否在那翻倍的人之中，然后剩下的组合数都非常简单，二分找一下数量就好了。时间复杂度 。

坑：注意特判分数为 ，因为那样分类讨论的结果会不同。

//2022.2.20 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,k;
    int a[N],b[N];
    int fac[N],inv[N];
    inline int C(const res &x,const res &y){
        return mul(fac[x],mul(inv[y],inv[x-y]));
    }
    inline void MAIN(){
        n=read(),k=read(),fac[0]=fac[1]=inv[0]=inv[1]=1;
        for(res i=2;i<=n;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        for(res i=2;i<=n;i++)inv[i]=mul(inv[i-1],inv[i]);
        for(res i=1;i<=n;i++)a[i]=b[i]=read();
        sort(b+1,b+n+1);
        b[0]=-1;
        for(res i=1;i<=n;i++){
            if(!a[i]){printf("%d\n",C(n,k));continue;}
            res ret=C((int)(upper_bound(b,b+n+1,(a[i]+1)/2-1)-upper_bound(b,b+n+1,a[i]-1))+n-1,k);
            res t=(int)(upper_bound(b,b+n+1,2*a[i]-1)-upper_bound(b,b+n+1,a[i]-1));
            if(k>=t)add(ret,C(n-t,k-t));
            printf("%d\n",ret);
        }
    }
}

[loj3274*]

Tag & Difficulty

Tag: 二分图、二分 | Difficulty: 四 （ 这可能只是因为我不会 ）

solution

做法：呃呃，我完全不会。第一步转成二分图我都没想到。

我们将可能颜色会变成一样的（ 原色相同、舔狗、有舔狗 ）的连边，那么一个点的度数要么是 ，要么是 。如果是 ，则那一定是答案。如果是 ，考虑将这三个点轮换扔进去询问，可以找到它舔的对象。同样地，可以找到舔它的对象，于是原色相同的就出来了。这样所用次数是小于等于 次。

那么问题就在于找这个二分图。考虑每次找一个最大点独立集，然后暴力三次二分找到独立集外与它相连的边，然后递归地找那些不在点独立集的边。由于点度不过 ，每个独立集大小都是大于等于原来的 的，于是总次数是不过 ，加上询问大概是 ，这样总次数就是足够的了。

//2022.2.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1010;
vector<int> G[N];
int vis[N],lov[N],whlov[N];
inline int ask(const res &a,const res &b,const res &c){
    vector<int> p;
    p.pb(a),p.pb(b),p.pb(c);
    return Query(p);
}
inline int ask(vector<int> a,const res &b){
    a.pb(b);
    return Query(a)==a.size();
}
inline int findans(const res &x,vector<int> v){
    if(v.size()==1){
        G[x].pb(v[0]),G[v[0]].pb(x);
        return v[0];
    }
    res mid=(int)(v.size())>>1;
    vector<int> L,R;
    for(res i=0;i<v.size();++i){
        if(i<mid)L.pb(v[i]);
        else R.pb(v[i]);
    }
    if(ask(L,x))return findans(x,R);
    return findans(x,L);
}
inline void Solve(res n){
    vector<int> ve;
    for(res i=1;i<=2*n;++i)ve.pb(i);
    random_shuffle(ve.begin(),ve.end());
    while(!ve.empty()){
        vector<int> duli,oth;
        for(auto x:ve){
            if(duli.empty()||ask(duli,x))duli.pb(x);
            else oth.pb(x);
        }
        for(auto x:oth){
            vector<int> rec=duli;
            do{
                res p=findans(x,rec);
                vector<int> ne;
                for(auto y:rec)if(y!=p)ne.pb(y);
                rec=ne;
                if(ask(rec,x)) break;
            }while(!rec.empty());
        }
        ve=oth;
    }
    for(res i=1;i<=2*n;++i){
        if(G[i].size()==1){
            if(vis[i]||vis[G[i][0]]) continue;
            Answer(i,G[i][0]);
            vis[i]=vis[G[i][0]]=1;
        }
        else{
            for(res j=0;j<=2;++j){
                if(ask(i,G[i][j],G[i][(j+1)%3])==1){
                    lov[i]=G[i][(j+2)%3];whlov[lov[i]]=i;
                    break;
                }
            }
        }
    }
    for(res i=1;i<=2*n;++i){
        if(vis[i])continue;
        for(res k=0;k<=2;++k){
            if(G[i][k]==lov[i]||G[i][k]==whlov[i]) continue;
            if(vis[G[i][k]]) continue;
            vis[i]=vis[G[i][k]]=1;
            Answer(i,G[i][k]);
            break;
        }
    }
}

[loj3561]

Tag & Difficulty

Tag: 贪心 | Difficulty: 三点五

solution

做法：先考虑对一个 的人而言，他被唤醒则要求 与 之间不被阻挡。那么每个 的人而言都有一个他的覆盖区间，而若两个覆盖区间是相交的，则相交处实际上对前一个人而言毫无意义，他是不能决定这块区域人是否被唤醒的，所以区间只有相离和包含关系了。

相离的可以独立考虑，那么我们要处理的就是包含关系，然后贪心处理答案。包含关系诈一看前面的选择会影响后面导致没有贪心性，实际上前后若都选，则答案不变。所以我们可以去贪心前面的选择，让前面的选择尽量大即可。从后往前考虑每个区间，隔断处一定是某个区间的起点，此时可以贪心考虑哪处隔断影响答案最大，然后更改其它隔断处的答案。注意到区间是包含关系，所以每个隔断处最多被修改一遍，利用单调栈总复杂度就是 了。

//2022.2.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e6+10;
namespace MAIN{
    int n,m,T;
    int L[N],t[N],R[N],cnt[N],sum[N];
    int st[N],top;
    inline void MAIN(const res &Case){
        n=read(),m=read(),T=read();
        res ans=0;
        for(res i=1;i<=n;i++)t[i]=read(),ans+=t[i]<=T;
        for(res i=n;i;i--){
            if(t[i]>T)continue;
            res pre=L[i]=i;
            R[i]=min(n,T+i-t[i]);
            while(top&&R[i]>=R[st[top]]){
                res p=st[top--];
                cnt[sum[i]]--,sum[i]+=L[p]-pre-1,cnt[sum[i]]++;
                sum[i]=max(sum[i],sum[p]),pre=R[p];
            }
            if(top)R[i]=min(R[i],L[st[top]]-1);
            cnt[sum[i]]--,sum[i]+=R[i]-pre,cnt[sum[i]]++;
            st[++top]=i;
        }
        for(res i=n;i;i--){
            res mn=min(m,cnt[i]);
            m-=mn,cnt[i]-=mn;
        }
        for(res i=1;i<=n;i++)ans+=i*cnt[i];
        printf("%d\n",ans);
    }
}

[loj3545]

Tag & Difficulty

Tag: 平面图对偶、区间 dp | Difficulty: 四

solution

做法：不能说是我想出来的，纯纯是因为之前看过题解了。

时，将异色的端点所处区域染色，同时将平面图转成其对偶图（ 即一个区域看成一个点，相邻区域连边 ），那么题意从最小割就转化成了两个空阔区域间的最短路（ 因为最优染色一定是两个区域，分别是黑白 ）。

更大时，考虑顺时针将每两个相邻且异色的射线间的空阔区域染与之前不同的颜色，把这些区域看成一个点，发现一个合法的割方案就等价于选择两个异色点连边，边权为这两个区域间的最小割，且要保证这里的边不交。于是做 次 ，将每个区域到其他区域的最小割都算出来，剩下的就是个区间 。时间复杂度 。

//2022.2.28 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=500+10;
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
namespace MAIN{
    int n,m,T;
    int a[N][N],b[N][N];
#define tup tuple<int,int,int>
    tup A[N];
    int id[N],w[N][N],dis[N][N],vis[N][N],k;
    priority_queue<tup,vector<tup>,greater<>>Q;
    inline void dij(const res &S){
        for(res i=0;i<=n;i++)for(res j=0;j<=m;j++){
            if(dis[i][j]<inf)Q.emplace(dis[i][j],i,j);
            vis[i][j]=0;
        }
        while(!Q.empty()){
            auto [d,x,y]=Q.top();
            Q.pop();
            if(vis[x][y])continue;
            vis[x][y]=1;
            if(x>0){
                res nx=x-1,ny=y;
                if(dis[nx][ny]>dis[x][y]+b[x][y])dis[nx][ny]=dis[x][y]+b[x][y],Q.emplace(dis[nx][ny],nx,ny);
            }
            if(y>0){
                res nx=x,ny=y-1;
                if(dis[nx][ny]>dis[x][y]+a[x][y])dis[nx][ny]=dis[x][y]+a[x][y],Q.emplace(dis[nx][ny],nx,ny);
            }
            if(x<n){
                res nx=x+1,ny=y;
                if(dis[nx][ny]>dis[x][y]+b[nx][y])dis[nx][ny]=dis[x][y]+b[nx][y],Q.emplace(dis[nx][ny],nx,ny);
            }
            if(y<m){
                res nx=x,ny=y+1;
                if(dis[nx][ny]>dis[x][y]+a[x][ny])dis[nx][ny]=dis[x][y]+a[x][ny],Q.emplace(dis[nx][ny],nx,ny);
            }
        }
        for(res i=1;i<=k;i++){
            res j=(i==k)?1:i+1;
            auto [p,W,opt]=A[i];
            if(opt!=get<2>(A[j])&&!opt){
                for(res x=p;x!=get<0>(A[j]);x=(x==n+n+m+m)?1:x+1) {
                    res px,py;
                    if(x<=m) px=0,py=x;
                    else if(x<=n+m) px=x-m,py=m;
                    else if(x<=n+m+m) px=n,py=m-(x-n-m);
                    else px=n-(x-n-m-m),py=0;
                    w[S][id[i]]=min(w[S][id[i]],dis[px][py]);
                    w[id[i]][S]=min(w[id[i]][S],dis[px][py]);
                }
            }
        }
    }
    int pos[N];
    int f[N][N];
    inline void MAIN(const res &Case){
        n=read(),m=read(),T=read();
        for(res i=1;i<n;i++)for(res j=1;j<=m;j++)a[i][j]=read();
        for(res i=1;i<=n;i++)for(res j=1;j<m;j++)b[i][j]=read();
        while(T--){
            k=read();
            res tot=0;
            for(res i=1;i<=k;i++){
                res W=read(),p=read(),opt=read();
                A[i]=tup(p,W,opt);
                if(p<=m)a[0][p]=W;
                else if(p<=n+m)b[p-m][m]=W;
                else if(p<=n+m+m)a[n][m-(p-n-m)+1]=W;
                else b[n-(p-n-m-m)+1][0]=W;
            }
            sort(A+1,A+k+1);
            for(res i=1;i<=k;i++){
                res j=(i==k)?1:i+1;
                auto [p,W,opt]=A[i];
                if(opt!=get<2>(A[j]))id[i]=++tot;
            }
            if(!tot){puts("0");continue;}
            for(res i=1;i<=tot;i++)for(res j=1;j<=tot;j++)w[i][j]=inf;
            for(res i=1;i<=k;i++){
                res j=(i==k)?1:(i+1);
                auto [p,W,opt]=A[i];
                if(opt!=get<2>(A[j])&&opt){
                    for(res x=0;x<=n;x++)for(res y=0;y<=m;y++)dis[x][y]=inf;
                    for(res x=p;x!=get<0>(A[j]);x=(x==n+n+m+m)?1:x+1) {
                        res px,py;
                        if(x<=m)px=0,py=x;
                        else if(x<=n+m)px=x-m,py=m;
                        else if(x<=n+m+m)px=n,py=m-(x-n-m);
                        else px=n-(x-n-m-m),py=0;
                        dis[px][py]=0;
                    }
                    dij(id[i]);
                }
            }
            for(res i=1;i<=tot;i++)pos[i]=pos[i+tot]=i;
            memset(f,0x3f,sizeof(f));
            for(res i=1;i<=tot+tot;i++)f[i][i-1]=0;
            for(res len=2;len<=tot;len++)for(res l=1,r=len;r<=tot+tot;l++,r++){
                f[l][r]=min(f[l][r],f[l+1][r-1]+w[pos[l]][pos[r]]);
                for(res K=l;K<r;K++)f[l][r]=min(f[l][r],f[l][K]+f[K+1][r]);
            }
            res ans=inf;
            for(res i=1;i<=tot;i++)ans=min(ans,f[i][i+tot-1]);
            printf("%d\n",ans);
            for(res i=1;i<=k;i++) {
                auto [p,W,opt]=A[i];
                if(p<=n)a[0][p]=0;
                else if(p<=n+m)b[p-m][m]=0;
                else if(p<=n+m+m)a[n][m-(p-n-m)+1]=0;
                else b[n-(p-n-m-m)+1][0]=0;
            }
        }
    }
}

[loj6086]

Tag & Difficulty

Tag: 拆式子算贡献 | Difficulty: 三

solution

做法：可以先考虑二维，然后就会发现三维是差差不多的。

我们假设当前 选择了 和 ，那么满足的条件就是 ，而此时的贡献是 。为了让条件与贡献式子长得差不多，我们不妨移个项，有

$$\begin{align*} &(L_a-K_a)-(L_b-K_b)\geq 0\\ &(K_a-J_a)-(K_b-J_b)\geq 0 &\end{align*}$$

注意到上面两个不等式一加，左边就是它们的贡献。于是我们就可以把一个数对的贡献拆成 ，那么一组 的贡献次数就是多少个比它小的数对的个数，其余同理，于是只要拆完贡献，排个序即可。时间复杂度 。

坑：注意要除以 。

//2022.3.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e5+10;
namespace MAIN{
    int n;
    int a[N],b[N],c[N];
    inline void MAIN(const res &Case){
        n=read();
        for(res i=1;i<=n;i++){
            res x=read(),y=read(),z=read();
            a[i]=x-y,b[i]=y-z,c[i]=z-x;
        }
        sort(a+1,a+n+1),sort(b+1,b+n+1),sort(c+1,c+n+1);
        res ans=0;
        for(res i=1;i<=n;i++)add(ans,mul(a[i]+b[i]+c[i],Add(2*i-1-n,0)));
        printf("%d\n",mul(ans,qpow(2)));
    }
}

[loj3028]

Tag & Difficulty

Tag: 贪心、树的直径 | Difficulty: 零点五

solution

做法：直径一定是两个叶子的路径，所以答案就是最深的点重复然后加上原来的直径即可。时间复杂度 。

//2022.3.2 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,m;
    vector<int> G[N];
    int dep[N],mx;
    void dfs(res x,res fax){
        if(dep[x]>dep[mx])mx=x;
        for(auto tox:G[x])if(tox!=fax)dep[tox]=dep[x]+1,dfs(tox,x);
    }
    inline void MAIN(const res &Case){
        n=read(),m=read();
        for(res i=2;i<=n;i++){
            res u=read();
            G[u].pb(i),G[i].pb(u);
        }
        dep[1]=1,dfs(1,0);
        res ret=dep[mx];
        dep[mx]=1,dfs(mx,0);
        printf("%lld\n",(LL)ret*2*(m-1)+dep[mx]);
    }
}

[loj3239*]

Tag & Difficulty

Tag: 倍增、结论题 | Difficulty: 三

solution

做法：这种题似乎我都不会。

有一个非常重要的性质就是，若某个点在两条对边所夹出的另外一端时，则一定无解。这可以考虑反证法，然后利用凸包的斜率性质得证。有了这个结论，这题就可以宣告结束了。我们随意地找一组对边来判一下，那么最坏情况就是这个点在两条边的同侧，这说明有一条边已经满足夹住这个点的性质。剩余的那条边我们直接倍增，找找看中途有没有满足，因为凸包的斜率性质，所以这是对的。时间复杂度 。

//2022.3.3 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 T;
    int last;
    int n;
#define pii pair<LL,LL>
    pii a[N];
    inline LL cub(const res &x){
        return (LL)x*x*x;
    }
    inline pii operator - (const pii &A,const pii &B){
        return mp(A.fi-B.fi,A.se-B.se);
    }
    inline unl operator ^ (const pii &A,const pii &B){
        return ((unl)A.fi*B.se)-((unl)A.se*B.fi);
    }
    inline bool ck(const res &p,const pii &A){
        return ((a[p]-A)^(a[p%n+1]-A))>=0;
    }
    inline int get(const res &x){
        return x>n?x-n:x;
    }
    inline void MAIN(const res &Case){
        T=read(),n=read();
        for(res i=1;i<=n;i++){
            LL x=Read(),y=Read();
            a[i]=mp(x,y);
        }
        res q=read();
        while(q--){
            LL A=Read()^(T*cub(last)),B=Read()^(T*cub(last));
            pii C=mp(A,B);
            res d1=ck(1,C),d2=ck(n/2+1,C);
            if(d1&&d2){puts("DA"),last++;continue;}
            if(!d1&&!d2){puts("NE");continue;}
            res u=d1?1:n/2+1;
            res s=0;
            for(res i=20;~i;i--)if(s+(1<<i)<n/2&&ck(get(u+(1<<i)),C))u=get(u+(1<<i)),s+=1<<i;
            if(ck(get(u+n/2),C))puts("DA"),last++;
            else puts("NE");
        }
    }
}

[loj6297]

Tag & Difficulty

Tag: 排序 | Difficulty: 零

solution

做法：排序就做完了，零分。

//2022.3.17 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;
    int a[N];
    Pair b[N];
    inline void MAIN(const res &Case){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read();
        sort(a+1,a+n+1);
        res m=0;
        for(res i=1;i<=n;){
            res j=i;
            while(a[j]==a[i]&&j<=n)j++;
            b[++m]=mp(j-i,a[i]),i=j;
        }
        sort(b+1,b+m+1),reverse(b+1,b+m+1);
        res fl=0;
        for(res i=1;i<=m;i++){
            if(b[i].fi!=b[1].fi){m=i-1,fl=1;break;}
        }
        if(!fl){puts("-1");return;}
        printf("%d\n",m);
        for(res i=m;i;i--)printf("%d ",b[i].se);
        puts("");
    }
}

[loj3684]

Tag & Difficulty

Tag: 性质分析、贪心构造 | Difficulty: 三

solution

做法：首先分析答案是什么，容易发现是强连通分量个数，于是就是给边定向使得强连通分量个数最少。不妨让左边一列边都往下，右边一列边都往上，这样会直观一点。

容易分析出一个性质，我们总想让右边上面的点连向左边上面的点，左边下面的点连向右边下面的点。可以发现，这样两边的最高点和最低点之间就形成了一个强联通分量。于是贪心地在左边自上而下地定向，如果当前连的右边的点在之前所有点的上面，那就从右往左连，否则从左往右连。证明是容易的，因为后者一定更劣，而前者一定更不劣。建完图再跑个 tarjan 求强连通分量即可。时间复杂度 。

//2022.3.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    int a,b,m;
    vector<Pair> A[N];
    int ans[N];
    vector<int> G[N];
    int dfn[N],low[N],idx,st[N],top,vis[N];
    int cnt;
    void tarjan(res x){
        dfn[x]=low[x]=++idx;
        vis[st[++top]=x]=1;
        for(auto tox:G[x]){
            if(!dfn[tox])tarjan(tox),low[x]=min(low[x],low[tox]);
            else if(vis[tox])low[x]=min(low[x],dfn[tox]);
        }
        if(dfn[x]==low[x]){
            cnt++;
            do{
                vis[st[top]]=0;
            }while(st[top--]!=x);
        }
    }
    inline void MAIN(const res &Case){
        a=read(),b=read(),m=read();
        for(res i=1;i<=m;i++){
            res u=read(),v=read();
            A[u].pb(mp(v,i));
        }
        for(res i=1;i<=a;i++)sort(A[i].begin(),A[i].end()),reverse(A[i].begin(),A[i].end());
        res mx=0;
        for(res i=1;i<=a;i++){
            for(auto [x,id]:A[i]){
                if(x>mx)mx=x,ans[id]=1,G[x+a].pb(i);
                else G[i].pb(x+a);
            }
        }
        for(res i=1;i<a;i++)G[i].pb(i+1);
        for(res i=1;i<b;i++)G[i+a].pb(i+a+1);
        for(res i=1;i<=a+b;i++)if(!dfn[i])tarjan(i);
        printf("%d\n",cnt);
        for(res i=1;i<=m;i++)printf("%d ",ans[i]);
    }
}

[loj3683]

Tag & Difficulty

Tag: 线段树、数论复杂度分析 | Difficulty: 三

solution

做法：考虑每个数在线段树上维护与它不互质的前驱，然后查询就是线段树上的区间 。考虑修改，发现每个数的不同质数个数是不多的，于是直接暴力枚举这个数的每个质数因子，然后把那些它是/将成为前驱的数暴力修改一下即可。复杂度只有 。

//2022.3.21 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 n,q;
    set<int> pre[N];
    vector<int> A[N];
    set<int> con[N];
    int vis[N];
    int mx[N<<2];
    void modify(res rt,res l,res r,const res &p){
        if(l==r){
            if(!pre[l].empty())mx[rt]=*(--pre[l].end());
            else mx[rt]=0;
            return;
        }
        res mid=(l+r)>>1;
        if(p<=mid)modify(rt<<1,l,mid,p);
        else modify(rt<<1|1,mid+1,r,p);
        mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
    }
    int query(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return mx[rt];
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query(rt<<1,l,mid,L,R);
        if(R>mid)ret=max(ret,query(rt<<1|1,mid+1,r,L,R));
        return ret;
    }
    char opt[2];
    inline void MAIN(const res &Case){
        n=read(),q=read();
        for(res i=2;i<=n;i++)if(!vis[i])for(res j=i;j<=n;j+=i)A[j].pb(i),vis[j]=1;
        for(res i=1;i<=n;i++)vis[i]=0;
        while(q--){
            scanf("%s",opt+1);
            if(opt[1]=='S'){
                res x=read();
                if(x==1)continue;
                if(!vis[x]){
                    vis[x]=1;
                    for(auto v:A[x]){
                        auto it=con[v].lower_bound(x);
                        if(it!=con[v].begin()){
                            auto y=*(--it);
                            pre[x].insert(y);
                            it++;
                        }
                        if(it!=con[v].end()){
                            auto y=*it;
                            pre[y].insert(x);
                            if(it!=con[v].begin())pre[y].erase(*(--it));
                            modify(1,1,n,y);
                        }
                        con[v].insert(x);
                    }
                    modify(1,1,n,x);
                }
                else {
                    vis[x]=0;
                    for(auto v:A[x]){
                        con[v].erase(x);
                        auto it=con[v].lower_bound(x);
                        if(it!=con[v].begin()){
                            auto y=*(--it);
                            pre[x].erase(y);
                            it++;
                        }
                        if(it!=con[v].end()){
                            auto y=*it;
                            pre[y].erase(x);
                            if(it!=con[v].begin())pre[y].insert(*(--it));
                            modify(1,1,n,y);
                        }
                    }
                    modify(1,1,n,x);
                }
            }
            else {
                res l=read(),r=read();
                puts(query(1,1,n,l,r)>=l?"DA":"NE");
            }
        }
    }
}

[loj3671]

Tag & Difficulty

Tag: Bitset、四毛子 | Difficulty: 三点五

solution

做法：容易注意到这题是个大拼凑题。考虑询问的答案是如何得出的，容易贪心地发现是对 的按 升序，其余的按 降序，然后前缀和的最大值的相反数就是答案。再观察一下，可以发现这等价于一维排序，其他三维都是前缀，是个四维偏序问题。经典的 CDQ 跑不过根号，根号跑不过 bitset，然后排序那一维再套个四毛子，这样复杂度是 。

为啥我这个跑得这么慢啊。

//2022.4.2 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=150000+10;
const int M=1<<16;
namespace MAIN{
    int q;
    char opt[10];
    struct Que{
        int op,a,b,c;
    }que[N];
    struct P{
        int x,y,z,a,b,id;
    }p[N];
    int px;
    int id[N];
    LL A[12][M],B[12][M];
    int ct[N];
    unsigned short now[12],nx[12][10000+1],ny[12][10000+1],nz[12][10000+1],L[12];
    LL ans[N],Now[N];
    inline void MAIN(const res &Case){
        q=read();
        for(res i=1,j=0;i<=N-10;i<<=1,j++)ct[i]=j;
        for(res i=1;i<=q;i++){
            scanf("%s",opt+1);
            if(opt[1]=='+'){
                res x=read(),y=read(),z=read(),a=read(),b=read();
                que[i].op=0,que[i].a=++px;
                p[px]={x,y,z,a,b,px};
            }
            else if(opt[1]=='-'){
                res k=read();
                que[i].op=0,que[i].a=k;
            }
            else {
                res g=read(),l=read(),d=read();
                que[i]={1,g,l,d};
            }
        }
        for(res i=1;i<=px;i++)id[i]=i;
        sort(p+1,p+px+1,[&](const P &A,const P &B){
            res _=(A.b>=A.a),__=(B.b>=B.a);
            if(_!=__)return _>__;
            if(_==1)return A.a<B.a;
            return A.b>B.b;
        });
        for(res i=1;i<=px;i++)id[p[i].id]=i,p[i].b-=p[i].a;
        for(res i=1;i<=q;i++)if(!que[i].op)que[i].a=id[que[i].a];
        for(res l=1,r;l<=px;l=r+1){
            r=min(px,l+16*12-1);
            res num=16;
            for(res j=0;j<12;j++){
                for(res i=1;i<=10000;i++)nx[j][i]=ny[j][i]=nz[j][i]=0;
                now[j]=0;
            }
            for(res j=0;j<12;j++)
                for(res S=1;S<1<<num;S++)A[j][S]=max((LL)p[l+16*j+ct[lowbit(S)]].a,A[j][S^lowbit(S)]-p[l+16*j+ct[lowbit(S)]].b),B[j][S]=p[l+16*j+ct[lowbit(S)]].b+B[j][S^lowbit(S)];
            vector<P> nP;
            for(res i=l;i<=r;i++)p[i].id=i-l,nP.pb(p[i]);
            sort(nP.begin(),nP.end(),[&](const P &A,const P &B){return A.x<B.x;});
            for(res i=0;i<12;i++)L[i]=0;
            for(res i=1,j=0,sz=(int)nP.size();i<=10000;i++){
                while(j<sz&&nP[j].x==i){
                    res I=nP[j].id;
                    L[I/16]|=1<<(I-I/16*16),j++;
                }
                for(res k=0;k<12;k++)nx[k][i]=L[k];
            }
            sort(nP.begin(),nP.end(),[&](const P &A,const P &B){return A.y<B.y;});
            for(res i=0;i<12;i++)L[i]=0;
            for(res i=1,j=0,sz=(int)nP.size();i<=10000;i++){
                while(j<sz&&nP[j].y==i){
                    res I=nP[j].id;
                    L[I/16]|=1<<(I-I/16*16),j++;
                }
                for(res k=0;k<12;k++)ny[k][i]=L[k];
            }
            sort(nP.begin(),nP.end(),[&](const P &A,const P &B){return A.z<B.z;});
            for(res i=0;i<12;i++)L[i]=0;
            for(res i=1,j=0,sz=(int)nP.size();i<=10000;i++){
                while(j<sz&&nP[j].z==i){
                    res I=nP[j].id;
                    L[I/16]|=1<<(I-I/16*16),j++;
                }
                for(res k=0;k<12;k++)nz[k][i]=L[k];
            }
            for(res i=1;i<=q;i++){
                if(que[i].op){
                    for(res j=0;j<12;j++){
                        LL sA=0,sB=0;
                        auto [op,x,y,z]=que[i];
                        res sit=now[j]&nx[j][x]&ny[j][y]&nz[j][z];
                        sA=A[j][sit]-Now[i];
                        sB=Now[i]+B[j][sit];
                        ans[i]=max(sA,ans[i]),Now[i]=sB;
                    }
                }
                else if(l<=que[i].a&&que[i].a<=r){
                    res I=que[i].a-l;
                    now[I/16]^=1<<(I-I/16*16);
                }
            }
        }
        for(res i=1;i<=q;i++)if(que[i].op)printf("%lld\n",ans[i]);
    }
}

[loj2037]

Tag & Difficulty

Tag: 线段树二分 | Difficulty: 二

solution

做法：发现三个操作都异常简单，询问操作是个类似最大子段和的东西，操作一是个区间覆盖，操作二我们可以二分出修改的右端点，然后也是个区间覆盖。注意到这个二分是可以放在线段树上，同时更加注意到这个二分和修改可以放在一起写，所以就很容易了。时间复杂度 。

//2022.4.2 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,m;
    struct P{
        int lm,rm,mx,len;
        inline void clear(){
            lm=rm=mx=0;
        }
        inline void cov(){
            lm=rm=mx=len;
        }
        inline void print(){
            printf("%d %d %d %d\n",lm,rm,mx,len);
        }
    }tr[N<<2];
    int sum[N<<2],tag[N<<2];
    inline P operator + (const P &A,const P &B){
        P C{};
        if(A.lm==A.len)C.lm=A.len+B.lm;
        else C.lm=A.lm;
        if(B.rm==B.len)C.rm=B.len+A.rm;
        else C.rm=B.rm;
        C.len=A.len+B.len;
        C.mx=max({A.mx,B.mx,A.rm+B.lm});
        return C;
    }
    void build(res rt,res l,res r){
        tr[rt].len=sum[rt]=r-l+1;
        if(l==r)return;
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
    }
    inline void change(const res &rt,const res &v){
        tag[rt]=v;
        if(v==1)tr[rt].clear(),sum[rt]=tr[rt].len;
        else tr[rt].cov(),sum[rt]=0;
    }
    inline void pushdown(const res &rt){
        if(!tag[rt])return;
        change(rt<<1,tag[rt]),change(rt<<1|1,tag[rt]),tag[rt]=0;
    }
    void modify(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R){change(rt,-1);return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R);
        tr[rt]=tr[rt<<1]+tr[rt<<1|1],sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    int nowv;
    void Modify(res rt,res l,res r,const res &L,const res &R){
        if(!nowv)return;
        if(L<=l&&r<=R&&nowv>=tr[rt].len-sum[rt]){nowv-=tr[rt].len-sum[rt],change(rt,1);return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)Modify(rt<<1,l,mid,L,R);
        if(R>mid)Modify(rt<<1|1,mid+1,r,L,R);
        tr[rt]=tr[rt<<1]+tr[rt<<1|1],sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    P query(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return tr[rt];
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid&&R>mid)return query(rt<<1,l,mid,L,R)+query(rt<<1|1,mid+1,r,L,R);
        if(L<=mid)return query(rt<<1,l,mid,L,R);
        return query(rt<<1|1,mid+1,r,L,R);
    }
    int querys(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return sum[rt];
        pushdown(rt);
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=querys(rt<<1,l,mid,L,R);
        if(R>mid)ret+=querys(rt<<1|1,mid+1,r,L,R);
        return ret;
    }
    inline void MAIN(const res &Case){
        n=read(),m=read(),build(1,1,n);
        while(m--){
            res opt=read();
            if(opt==0){
                res l=read(),r=read();
                modify(1,1,n,l,r);
            }
            else if(opt==1){
                res l=read(),r=read(),L=read(),R=read();
                res s=querys(1,1,n,l,r);
                modify(1,1,n,l,r),nowv=s,Modify(1,1,n,L,R);
            }
            else {
                res l=read(),r=read();
                printf("%d\n",query(1,1,n,l,r).mx);
            }
        }
    }
}

[loj3672]

Tag & Difficulty

Tag: 单调性分析 | Difficulty: 二

solution

做法：这真的是 CTT 的题吗，这难度是不是有点。

uoj 有个简化题意，一看就懂了。考虑一个合法 是咋样的，可以注意到是要求 只在 中出现一次，