ABC 256

E – Takahashi’s Anguish(图论、基环树、并查集)

Problem

现在有/(N/)个人排队，但如果第/(X_i/)个人排到第/(i/)个人前面，第/(i/)个人会获得不满值/(C_i/)，求在最优安排下的最小的不满值之和

Solve

将第/(i/)个人向第/(X_i/)人连一条有向边，那么整个图的每个点的出度都是/(1/)，形成了一个基环内向森林，假设这个森林有/(m/)个连通块，那么每个连通块有且只有一个环，每个连通块对答案的贡献就是环上最小的/(C_i/)，很好思考，因为一个环上只有开头的那个人不会被满足，让这个不能被满足的人最小即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int f[N];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n;
   cin>>n;
   vector<int>x(n+1);
   vector<int>c(n+1);
   for(int i=1;i<=n;i++) cin>>x[i];
   for(int i=1;i<=n;i++) cin>>c[i];
   for(int i=1;i<=n;i++) f[i]=i;
   long long ans=0;
   for(int i=1;i<=n;i++)
    if(find(i)!=find(x[i])){
        f[find(i)]=find(x[i]);
    }else{
        int cur=c[i],v=i;
        do{
            v=x[v];
            cur=min(cur,c[v]);
        }while(v!=i);
        ans+=cur;
    }

    cout<<ans<<'/n';
}

F – Cumulative Cumulative Cumulative Sum(树状数组)

Problem

给定一个长度为/(N/)的序列/(A/)，记/(B_i=/sum_{j=1}^iA_i/)，/(C_i=/sum_{j=1}^iB_i/)，/(D_i=/sum_{j=1}^iC_i/)

现在有/(Q/)个操作，操作有/(2/)种

• 1 x v将/(A_x/)改为/(v/)
• 2 x查询/(D_x/)

Solve

展开后容易知道/(D_n=/sum_{i=1}^n/frac{(n-i+1)(n-i+1+1)}{2}A_i/)，考虑把/((n-i+1)(n-i+1+1)/)展开，/(A_i(n-i+1)(n-i+1+1)=n(n+1)A_i-A_i(i-1)(2n+1)+A_i(i-1)^2/)，所以我们只需要求/(A_i/)、/(A_i(i-1)/)、/(A_i(i-1)^2/)的前缀和就好了。

Code

#include <bits/stdc++.h>
using namespace std;
const int mod= 998244353;
const int N=2e5+10;
typedef long long ll;
struct BIT{
    int n;
    vector<ll>tr;
    BIT(int n_):n(n_){
        tr.resize(n_+1);
    }
    void add(int p,ll x){
       for(;p<=n;p+=p&-p) tr[p]=(tr[p]+x)%mod;
    }
    ll ask(int p){
        ll res=0;
        for(;p;p-=p&-p) res=(res+tr[p])%mod;
            return res;
    }
};
ll power(ll x,ll y){
   ll res=1;
   while(y){
    if(y&1) res=res*x%mod;
    x=x*x%mod;
    y>>=1;
   }
   return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    ll inv=power(2,mod-2);
    BIT t1(n),t2(n),t3(n);
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
        t1.add(i,a[i]),t2.add(i,a[i]*(i-1)%mod),t3.add(i,a[i]*(i-1)%mod*(i-1)%mod);
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            ll v;
            cin>>x>>v;
            t1.add(x,(v-a[x]+mod)%mod);
            t2.add(x,(v-a[x]+mod)%mod*(x-1)%mod);
            t3.add(x,(v-a[x]+mod)%mod*(x-1)%mod*(x-1)%mod);
            a[x]=v;
        }else{
            int x;
            cin>>x;
            ll res=0;
            ll s0=t1.ask(x);
            ll s1=t2.ask(x);
            ll s2=t3.ask(x);
            res=((s2-s1*(x+(x+1))%mod+mod)%mod+s0*x%mod*(x+1)%mod)%mod;
            cout<<res*inv%mod<<'/n';
        }
    }
}

G – Black and White Stones(矩阵优化DP、计数)

Problem

现在有一个边长为/(D/)的正/(N/)边形，每条边可以放/(D+1/)个石头，每个石头有黑、白两种颜色，要求每条边白色的石头个数是一样的，问有多少种放置石头的方法，答案对/(998244353/)取模。

/(1/le N/le 10^{12}/)，/(1/le M/le 10^4/)

Solve

考虑枚举每条边白色的个数为/(k/)，对于一条边，考虑有多少种填法。记/(dp_{i,j}/)为一条边首端的颜色为/(i/)，尾端颜色为/(j/)的填法，不妨设/(0/)为填白色，/(1/)为填黑色，又由于已经固定了/(2/)端的填色方案，那么是需要在剩下的/(d-1/)个里面选即可，那么/(dp_{0,0}=/binom{k-2}{d-1}/)，/(dp_{0,1}=/binom{k-1}{d-1}/)，/(dp_{1,0}=/binom{k-1}{d-1}/)，/(dp_{1,1}=/binom{k}{d-1}/)，这是一条边的方案数，但由于/(2/)条相邻边的有一端是公共端，所以不能直接用一个多项式/((dp_{0,0}+dp_{0,1}+dp_{1,0}+dp_{1,1})^n/)这样用多项式快速幂算，不妨强制选定一个方向(顺/逆)作为首到尾的方向，这里规定第一维是首，第二维是尾，那么合法的转移就是/(dp_{0,0}/times (dp_{1,0}+dp_{0,0})/)，/(dp_{1,0}/times (dp_{1,1}+dp_{0,1})/)，/(dp_{0,1}/times (dp_{1,0}+dp_{0,0})/)，/(dp_{1,1}/times (dp_{1,1}+dp_{0,1})/)，显然，这是一个矩阵乘法的形式，对应的矩阵就是
/(A=/left[
/begin{matrix}
dp_{1,1} & dp_{0,1} //
dp_{1,0} & dp_{0,0} //
/end{matrix}
/right]
/)，/(A[0][0]/)表示首尾都是黑色的方案数，意味着矩阵乘法之后仍然需要保持这样的定义，发现做完/((AA)[0][0]=dp_{1,1}/times dp_{1,1}+dp_{0,1}/times dp_{1,0}/)，刚好还是首位是黑的方案数，比如/(dp_{0,1}/times dp_{1,0}/)的意义就是首白尾黑的边接上首黑尾白的边，这样的新边就是首黑尾黑的。所以只需要对这个矩阵做快速幂，时间复杂度是/(O(logN)/)的。对于每一个/(k/)，答案加上最后快速幂完的矩阵的对角线上的元素即可，因为最后会连到一个点上，所以首尾的颜色一定是一样的。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
struct Matrix{
     ll a[2][2];
     Matrix(){
         memset(a,0,sizeof a);
     }
     Matrix operator * (const Matrix &t)const{
        Matrix res;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                     res.a[i][j]=(res.a[i][j]+a[i][k]*t.a[k][j]%mod)%mod;
        return res;
     }
};
ll power(ll x,int y){
    ll res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
Matrix Matpower(Matrix A,ll x){
    Matrix res;
    res.a[0][0]=res.a[1][1]=1;
    while(x){
        if(x&1) res=res*A;
         A=A*A;
        x>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    int d;
    cin>>n>>d;
    vector<ll>binom(d);
    binom[0]=1;
    for(int i=1;i<d;i++) binom[i]=binom[i-1]*(d-i+mod)%mod*power(i,mod-2)%mod;
    auto cal=[&](int x)->ll{
         if(x<0||x>=d) return 0;
         else return binom[x];
    };
    ll ans=0;
    for(int i=0;i<=d+1;i++){
        Matrix dp;
        dp.a[0][0]=cal(i),dp.a[0][1]=cal(i-1);
        dp.a[1][0]=cal(i-1),dp.a[1][1]=cal(i-2);

        Matrix res=Matpower(dp,n);

        ans=((ans+res.a[0][0])%mod+res.a[1][1])%mod;
    }
    cout<<ans<<'/n';
}

Ex – I like Query Problem(区间修改、区间求和、势能线段树)

Problem

有一个长度为/(N/)的序列/(A=(a_1,a_2,/cdot /cdot /cdot,a_N)/)和/(Q/)个询问，询问分为三种类型

• 1 l r x：把/(a_l,/cdot /cdot /cdot,a_r/)的每个数变成/(/lfloor /frac{a_i}{x} /rfloor/)
• 2 l r y：把/(a_l,/cdot /cdot /cdot,a_r/)的每个数变成/(y/)
• 3 l r：查询区间/([l,r]/)的和

/(1/le N/le 5/times 10^5/)，/(1/le Q/le 10^5/)，/(1/le a_i/le 10^5/)，/(2/le x/le 10^5/)，/(1/le y/le 10^5/)

Solve

难点在于操作1，但根据势能线段树的理论，并且每次操作1都是除以一个大于等于/(2/)的数，所以每个数最多操作/(18/)次就变为/(0/)了，记录一个区间最小值和区间最大值来判断两个区间经过若干次操作后是否相等。

Code

#include <bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define ll long long
using namespace std;
const int N=5e5+10;
int a[N];
struct seg{
    ll sum;
    int mx,mn;
    int tag;
    int sz;
}tr[N*4];
void pushup(int rt){
    tr[rt].sum=tr[ls].sum+tr[rs].sum;
    tr[rt].mn=min(tr[ls].mn,tr[rs].mn);
    tr[rt].mx=max(tr[ls].mx,tr[rs].mx);
}
void build(int rt,int l,int r){
     tr[rt].sz=r-l+1;
     tr[rt].tag=-1;
     if(l==r){
        tr[rt].sum=tr[rt].mn=tr[rt].mx=a[l];
        return;
     }
     int mid=l+r>>1;
     build(ls,l,mid);
     build(rs,mid+1,r);
     pushup(rt);
}
void change2(int rt,int x){
    tr[rt].tag=x;
    tr[rt].sum=1LL*tr[rt].sz*x;
    tr[rt].mn=tr[rt].mx=x;
}
void change1(int rt,int x){
      if(tr[rt].mn==tr[rt].mx){
        change2(rt,tr[rt].mn/x);
      } else{
        change1(ls,x);
        change1(rs,x);
        pushup(rt);
      }
}
void pushdown(int rt){
    if(tr[rt].tag!=-1){
        change2(ls,tr[rt].tag);
        change2(rs,tr[rt].tag);
        tr[rt].tag=-1;
    }
}
void update(int rt,int L,int R,int l,int r,int x,int t){
    if(l<=L&&R<=r){
        if(t==2) change2(rt,x);
        else change1(rt,x);
        return;
    }
    pushdown(rt);
    int mid=L+R>>1;
    if(l<=mid) update(ls,L,mid,l,r,x,t);
    if(r>mid) update(rs,mid+1,R,l,r,x,t);
    pushup(rt);

}
ll query(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r) return tr[rt].sum;
    pushdown(rt);
    ll res=0;
    int mid=L+R>>1;
    if(l<=mid) res+=query(ls,L,mid,l,r);
    if(r>mid) res+=query(rs,mid+1,R,l,r);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==3){
            cout<<query(1,1,n,l,r)<<'/n';
        }else{
            int x;
            cin>>x;
            update(1,1,n,l,r,x,op);
        }
    }
}