【M Contect-Div.3】#2 题解

· · 题解

都打得怎么样，我发现没一个人做出来我的题 QWQ。 ——mengnn。

本帖由 mengnn 编写，若有疏漏感谢指出。

本帖 2025.8.17 完工。

A. Tree-Music 题解

题面及思路

简单的模拟和判断，从头到尾把字符串看一遍就好，就不过多赘述。

注意：读入为一整行。

时间复杂度

简单的线形级复杂度，若设输入总字符数为 n，则复杂度为 O(n)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    while(1){
        cin>>s;
        if(s=="||")break;
        if(s=="|")putchar('|');
        if(s=="4")putchar('x');
        if(s=="8")putchar('_'),putchar('x');
        if(s=="16")putchar('_'),putchar('_'),putchar('x');
        if(s=="2")putchar('X');
        putchar(' ');
    }
    return 0;
}

代码来自 SP_beyond_xxxx。

B. Tree-City 题解

题面及思路

为方便描述，我们设第 i 个 NPC 使旅行者获得的快乐度为 a_i。

可以运用递推思想，对于 1~n 中的每一个 i，因为要静态的速算区间和，所以前缀和是很必要的，我们用 sum_i=\sum_{j = 1}^{i} a_j。然后再存一个 minn_i 表示 \min_{j = 1}^{i} sum_j。

然后从 1 到 n 遍历每一个 sum_i，贪心地更新答案 sum_i-minn_{i-1} 就好了。

这里我们节省数组的空间开销，运用滚动数组，用变量 sum 表示当前 sum_i，变量 m 表示当前 m_{i-1}，ans 表示答案。

注意：多测不清空，爆零两行泪。

时间复杂度

数据组数为 T，序列元素个数为 n，则复杂度为 O(Tn)。

AC Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const long long INF=0x7f7f7f7f7f7f7f7f;
int T,n,a[N];
long long sum,ans,m;
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        ans=-INF;m=sum=0;
        for(int i=1;i<=n;i++){
            sum+=a[i];
            ans=max(ans,sum-m);
            m=min(m,sum);
        }cout<<ans<<'\n';
    }return 0;
}

代码来自 mengnn。

C. Tree-Maths 题解

题面及思路

高精度很恶心的，但他还是出了 (T n T)。

纯模拟，根据题目来就行，先把两个数字转成非科学计数法形式，然后高精加/减即可。

时间复杂度

数据组数为 T，序列元素个数为 n，则复杂度为 O(Tn)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long s_2,r,a[N],b[N],c[N],len,p,temp[N];
string s1,s2;
string ss,sss;
char f='+';

struct SciNum {
    string num;
    int exp;
};

SciNum parseSci(string s) {
    SciNum res;
    size_t e_pos = s.find('e');
    if(e_pos == string::npos) {
        res.num = s;
        res.exp = 0;
    } else {
        res.num = s.substr(0, e_pos);
        res.exp = stoi(s.substr(e_pos+1));
    }
    return res;
}

string normalize(SciNum sn) {
    string num = sn.num;
    int exp = sn.exp;

    size_t dot_pos = num.find('.');
    if(dot_pos != string::npos) {
        exp -= (num.size() - dot_pos - 1);
        num.erase(dot_pos, 1);
    }

    while(num.size() > 1 && num[0] == '0') {
        num.erase(0, 1);
    }

    return num + string(exp, '0');
}

void jia(long long a[],long long b[]){
    for(int i=1;i<=len+1;i++){
        c[i]+=a[i]+b[i];
        if(c[i]>=10){
            c[i+1]+=1;
            c[i]%=10;
        }
    }
    len=max(s1.size(),s2.size());
    if(c[len+1]!=0){
        len++;
    }
    for(int i=len;i>0;i--){
        cout<<c[i];
    }
}

void jian(long long a[],long long b[]){
    for(int i=1;i<=len+1;i++){
        if(a[i]<b[i]){
            a[i+1]-=1;
            a[i]+=10;
        }
        c[i]=a[i]-b[i];
    }
    if(s1.size()<s2.size()||(s1<s2&&s1.size()==s2.size())){
        swap(s1,s2);
        f='-';
    }len=max(s1.size(),s2.size());
    for(int i=len;i>=1;i--){
        if(c[i]!=0){
            p=i;
            break;
        }
    }
    if(f=='-'){
        cout<<f;
    }
    for(int i=p;i>0;i--){
        cout<<c[i];
    }
    if(p==0){
        cout<<'0';
    }
}

int main(){
    char op;
    cin>>ss>>op>>sss;

    SciNum num1 = parseSci(ss);
    SciNum num2 = parseSci(sss);

    s1 = normalize(num1);
    s2 = normalize(num2);

    a[0]=s1.size();
    b[0]=s2.size();
    for(int i=0;i<a[0];i++)a[a[0]-i]=s1[i]-'0';
    for(int i=0;i<b[0];i++)b[b[0]-i]=s2[i]-'0';

    len=max(a[0],b[0]);
    if(op=='+') jia(a,b);
    else jian(a,b);

    return 0;
}

代码来自 SP_beyond_xxxx。

D. Tree-Dream 题解

题面及思路

题目很经典也很迷惑，看起来像是 LIS 变形，实际上是树状数组简单应用。

我们定义树状数组 s 和 t，分别维护从前到后和从后到前 1~k 的数出现个数的前缀和（k 为任意数）。

对于树状数组 s，每次我们要先查询后修改，因为我们要求的是严格上升，所以我们需要计算 1\le j<i\le n,a_j<a_in 的 j 的数量。易知，答案即为 s.ask(a[i]-1)。

对于树状数组 t，与 s 同理，但我们要逆序求答案。我们需要计算 1\le i<j\le n,a_i<a_j 的 j 的数量。我们可以运用补集思想，a_i\ge a_j，答案即 t.ask(a[i])，那么我们要求 a_i<a_j，答案即为 n-i-t.ask(a[i])，答案中的 n-i 为现在 t 中的元素个数。因为我们先查询后修改，所以是不需要加一的。

注意到 \max_{i=1}^{n} a_i 实际上很大，达到了 10^{36} 量级，long long 绝对是存不下的，可以用 __int128 存储。

再注意到 n 和 \max_{i=1}^{n} a_i 的差距特别大，最坏情况才有 2\times10^6 个数被应用，我们的树状数组开不了 10^{36} 这就必须要离散化 或用 map 存储。

假如说树状数组 s 对于 a_1,a_2,...,a_n 的答案为 l_1,l_2,...,l_n，树状数组 t 对于 a_1,a_2,...,a_n 的答案为 r_1,r_2,...,r_n。根据简单的组合数运算，则最终的答案就是 \sum_{i=1}^{n}l_i\cdot r_i。

因为输入元素个数较多，我们保险一些，写上快速读入。

最后，注意答案要开 long long。

时间复杂度

因为输入元素个数为 n，所以输入和遍历数组复杂度绝对就是 O(n) 的。

又因为用到了离散化和树状数组，所以它们各会取一个 O(\log_2n)。

总时间复杂度来到了 O(n+n\log_2^2n)，最终复杂度 O(n\log_2^2n) 看起来不太能通过，但树状数组的和离散化二分的 \log_2n 常数都很小，足以通过此题。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
__int128 n,a[N],mp[N],ans;
long long l[N];
inline void rd(__int128 &x){
    x=0;char ch;
    bool f=false;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
        if (ch=='-')
            f=true;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<3)+(x<<1)+(ch&15);
    if (f) x=-x;
}
inline void wr(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) wr(x/10);
    putchar(x%10+'0');
    return ;
}
inline int f(__int128 v){
    return lower_bound(mp+1,mp+n+1,v)-mp+1;
}
struct Tree{
    int c[N];
    inline void add(int x,int v){
        for (;x<=n;x+=x&-x)
            c[x]+=v;
    }
    inline int ask(int x){
        int res=0;
        for (;x;x^=x&-x)
            res+=c[x];
        return res;
    }
}s,t;
int main(){
    rd(n);
    for (int i=1;i<=n;i++) rd(a[i]),mp[i]=a[i];
    sort(mp+1,mp+n+1);
    for (int i=1;i<=n;i++){
        l[i]=s.ask(f(a[i])-1);
        s.add(f(a[i]),1);
    }
    for (int i=n;i;i--){
        if (i!=n&&i!=1)
            ans+=l[i]*(n-i-t.ask(f(a[i])));
        t.add(f(a[i]),1);
    }
    wr(ans);
    return 0;
}

E. Tree-Save 题解

题面及思路

为了提高 AK 概率，这题还是出得很板的，一眼树剖，只不过线段树需要允许区间乘，区间加，区间求和。

线段树和树剖不会写的建议去这里和这里。

时间复杂度

树链剖分的初始化要遍历两次树，若树的节点数为 n 个，则复杂度为 O(n)。

可以证明，树链剖分会把树剖分成 \log_2n 条链，所以跳链复杂度为 O(\log_2n)。

线段树的维护时 O(\log_2n) 的，又因为有 q 次询问，所以总时间复杂度来到了 O(n+q\log_2^2n)，最终复杂度 O(q\log_2^2n)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const long long mod=998244353;
int n,m,R;
long long val[N];
int f[N],son[N],sz[N],dep[N];
int top[N],dfn[N],rnk[N],cnt;
vector<int> edge[N];
struct STree{
    struct node{
        int l,r;
        long long mul,add,sum;
    }t[N<<2];
    inline void build(int p,int l,int r){
        t[p].l=l;t[p].r=r;
        t[p].mul=1;t[p].add=0;
        if (l==r){
            t[p].sum=val[rnk[l]]%mod;
            return ;
        }int mid=(l+r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
        return ;
    }
    inline void pushdown(int p){
        int l=p<<1,r=p<<1|1;
        t[l].sum=(t[l].sum*t[p].mul+t[p].add*(t[l].r-t[l].l+1))%mod;
        t[r].sum=(t[r].sum*t[p].mul+t[p].add*(t[r].r-t[r].l+1))%mod;
        t[l].mul=(t[l].mul*t[p].mul)%mod;
        t[r].mul=(t[r].mul*t[p].mul)%mod;
        t[l].add=(t[l].add*t[p].mul+t[p].add)%mod;
        t[r].add=(t[r].add*t[p].mul+t[p].add)%mod;
        t[p].add=0;t[p].mul=1;
        return ;
    }
    inline void change(int p,int l,int r,long long v,bool d){
        if (l<=t[p].l&&t[p].r<=r){
            if (d){
                t[p].add=v*t[p].add%mod;
                t[p].mul=v*t[p].mul%mod;
                t[p].sum=v*t[p].sum%mod;
            }else{
                t[p].add=(t[p].add+v)%mod;
                t[p].sum=(t[p].sum+v*(t[p].r-t[p].l+1)%mod)%mod;
            }return ;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if (l<=mid) change(p<<1,l,r,v,d);
        if (r>mid) change(p<<1|1,l,r,v,d);
        t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
        return ;
    }
    inline long long ask(int p,int l,int r){
        if (l<=t[p].l&&t[p].r<=r) return t[p].sum;
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        long long val=0;
        if (l<=mid) val=(val+ask(p<<1,l,r))%mod;
        if (r>mid) val=(val+ask(p<<1|1,l,r))%mod;
        return val;
    }
}st;
inline void dfs1(int x){
    sz[x]=1;
    son[x]=-1;
    for (auto y:edge[x])
        if (!dep[y]){
            dep[y]=dep[x]+1;
            f[y]=x;
            dfs1(y);
            sz[x]+=sz[y];
            if (son[x]==-1||sz[y]>sz[son[x]]) son[x]=y;
        }
}
inline void dfs2(int x,int t){
    top[x]=t;
    dfn[x]=++cnt;
    rnk[cnt]=x;
    if (son[x]==-1) return ;
    dfs2(son[x],t);
    for (auto y:edge[x])
        if (y!=f[x]&&y!=son[x])
            dfs2(y,y);
}
inline void add_ans(int x,int y,long long v){
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        st.change(1,dfn[top[x]],dfn[x],v,0);
        x=f[top[x]];
    }if (dfn[x]>dfn[y]) swap(x,y);
    st.change(1,dfn[x],dfn[y],v,0);
}
inline void cheng_ans(int x,int y,long long v){
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        st.change(1,dfn[top[x]],dfn[x],v,1);
        x=f[top[x]];
    }if (dfn[x]>dfn[y]) swap(x,y);
    st.change(1,dfn[x],dfn[y],v,1);
}
inline long long get_ans(int x,int y){
    long long ans=0;
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=(ans+st.ask(1,dfn[top[x]],dfn[x]))%mod;
        x=f[top[x]];
    }if (dfn[x]>dfn[y]) swap(x,y);
    return (ans+st.ask(1,dfn[x],dfn[y]))%mod;
}
int main(){
    scanf("%d%d",&n,&m);R=1;
    for (int i=1;i<=n;i++) scanf("%lld",&val[i]);
    for (int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }dep[R]=1;dfs1(R);dfs2(R,R);
    st.build(1,1,n);
    while (m--){
        long long opt,x,y,z;
        scanf("%lld%lld",&opt,&x);
        if (opt<6) scanf("%lld",&y);
        if (opt<3) scanf("%lld",&z);
        if (opt==1) add_ans(x,y,z);
        if (opt==2) cheng_ans(x,y,z);
        if (opt==3) printf("%lld\n",get_ans(x,y));
        if (opt==4) st.change(1,dfn[x],dfn[x]+sz[x]-1,y,0);
        if (opt==5) st.change(1,dfn[x],dfn[x]+sz[x]-1,y,1);
        if (opt==6) printf("%lld\n",st.ask(1,dfn[x],dfn[x]+sz[x]-1));
    }
    return 0;
}