2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——F. Map and Fold（折纸题）

Posted on 2026-03-08 Edited on 2026-04-06

题目大意

题目大意

有一张地图，可以通过若干次贯穿整张纸的水平方向和垂直方向的折叠，最终被折叠成一个 $1 \times 1$ 的正方形单位。每次折叠都发生在距离纸张边缘为整数个单位的位置。

当把这张地图重新完全展开时，所有的折痕会把纸张划分成一个 $r \times c$ 的正方形网格。任意两个相邻正方形之间共享的边即为一条长度为 $1$ 的折痕。根据折叠方向的不同，折痕可以分为两种：

峰折（Mountain fold）：向观察者方向折叠而成的凸起折痕。
谷折（Valley fold）：背离观察者方向折叠而成的凹陷折痕。

题目给定一个 $(2r - 1) \times (2c - 1)$ 的字符矩阵，用来编码展开后的地图折痕状态。矩阵中第 $i$ 行第 $j$ 列的字符含义如下：

当 $i$ 和 $j$ 均为奇数时，字符为 .，表示一个 $1 \times 1$ 的正方形。
当 $i$ 和 $j$ 均为偶数时，字符为 +，表示四个正方形相交的角。
其他情况下，字符表示两个相邻正方形之间的折痕：M 表示峰折，V 表示谷折。

任务：给定上述字符矩阵，判断是否能通过上述合法的折叠过程（每次水平或垂直折叠贯穿当前的整张纸，直到折成 $1 \times 1$ 大小），在现实中精准复现该矩阵所描述的折痕图案。如果可以，输出 YES，否则输出 NO。

样例及解释

样例输入

2
3 4
.V.V.M.
M+M+M+M
.M.M.V.
V+M+V+M
.M.M.V.
2 2
.M.
M+M
.M.

样例输出

1
2

YES
NO

样例解释
输入包含两个测试用例：

第一个测试用例给出了一个 $(2 \times 3 - 1) \times (2 \times 4 - 1)$ 即 $5 \times 7$ 的字符矩阵，代表一个 $3 \times 4$ 的网格。该图案是可以通过规定的折叠方法真实得到的折痕分布，因此输出 YES。
第二个测试用例给出了一个 $3 \times 3$ 的字符矩阵，代表一个 $2 \times 2$ 的网格。其四周的折痕全为 M（峰折），而在这种必须贯穿整张纸面进行折叠的规则下，无法在现实中构造出这样的折痕组合，因此输出 NO。

给你一个这样的矩阵，问可不可能折纸做到？

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）

P13825 【模板】线段树 1.5（指针式动态开点线段树）

Posted on 2026-03-08 Edited on 2026-04-06

题目大意

P13825 【模板】线段树 1.5

题目描述

如题，已知一个长度为 $n$

的数列 $\{a_i\}$ （ $1 \leq i \leq n$ ），初始时 $a$ 序列满足 $a_i = i$ 。你需要进行下面两种操作：

将某区间每一个数加上 $k$ 。
求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n, m$ ，分别表示该数列数字的个数和操作的总个数。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1 l r k：将区间 $[l,r]$ 内每个数加上 $k$ 。
2 l r：输出区间 $[l,r]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例 #1

输入 #1

输出 #1

1
2
3

9
9
18

说明/提示

对于 $30\%$ 的数据， $n \le 8$ ， $m \le 10$ 。

对于 $50\%$ 的数据， $n \le {10}^5$ 。

对于 $100\%$ 的数据， $1 \le m,k \le {10}^5$ ， $1 \leq l \leq r \leq n\leq 10^9$ 。

思路讲解


/* 
 * 2026-03-08  P13825 【模板】线段树 1.5 动态开点线段树
 * AC https://www.luogu.com.cn/record/266006147
 *
 */
struct Tag {
    // 在母串中的这个位置
    ll add=0;
    bool need_apply=false;
    void apply(const Tag &t) {
        add+=t.add;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    i128 sum=0;
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        res.sum+=b.sum;
        return res;
    }
    void apply(const Tag&t) {
        if (!t.need_apply) {
            return;
        }
        ll len=r-l+1;
        sum+=len*t.add;
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
template<class I=Info,class T=Tag>
struct SEG {
    // 如果不需要泛型，可以用下面的来替代
    // using I=Info;
    // using T=Tag;
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
        u->info.sum=i128(u->info.l+u->info.r)*(u->info.r-u->info.l+1)/2;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        root->info.l=1;
        root->info.r=N;
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag);
            u->rs->info.apply(u->tag);
            u->ls->tag.apply(u->tag);
            u->rs->tag.apply(u->tag);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,const T& t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t);
            u->tag.apply(t);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

AC代码

AC
https://www.luogu.com.cn/record/266006147

源代码

/**
 * Problem: P13825 【模板】线段树 1.5
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P13825
 * Created: 2026-03-08 13:03:42
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
ostream& operator<<(ostream& os, i128 x) {
    if (x < 0) os << '-', x = -x;
    if (x > 9) os << x / 10;
    return os << (char)('0' + x % 10);
}

struct Tag {
    // 在母串中的这个位置
    ll add=0;
    bool need_apply=false;
    void apply(const Tag &t) {
        add+=t.add;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    i128 sum=0;
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        res.sum+=b.sum;
        return res;
    }
    void apply(const Tag&t) {
        if (!t.need_apply) {
            return;
        }
        ll len=r-l+1;
        sum+=len*t.add;
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
template<class I=Info,class T=Tag>
struct SEG {
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
        u->info.sum=i128(u->info.l+u->info.r)*(u->info.r-u->info.l+1)/2;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        root->info.l=1;
        root->info.r=N;
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag);
            u->rs->info.apply(u->tag);
            u->ls->tag.apply(u->tag);
            u->rs->tag.apply(u->tag);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,const T& t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t);
            u->tag.apply(t);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

void Solve() {
    ll N,M;
    cin >> N >> M;
    SEG<Info,Tag> seg(N);
    for (int i=1;i<=M;++i) {
        ll op;
        cin>>op;
        if (op==1) {
            ll l,r,k;
            cin>>l>>r>>k;
            seg.modify(seg.root,l,r,{k,true});
        }else {
            ll l,r;
            cin>>l>>r;
            cout<<seg.query(seg.root,l,r).sum<<"\n";
        }
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC

*/

心路历程（WA，TLE，MLE……）

不要忘记初始化这个根节点。

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——B. DJ Nicholas（get_range_cnt，可以变为 get_pref_cnt(r)-get_pref_cnt(l - 1)，是一个非常经典的套路）

Posted on 2026-03-07 Edited on 2026-04-06

题目大意

题目设定
给定一个包含 $k$ （ $1 \le k \le 26$ ）首短歌的曲库，分别用前 $k$ 个大写英文字母表示。
由这 $k$ 首歌可以生成一个无限长的母带（master track） $t$ 。生成方式为：不断重复这 $k$ 首歌，但在每一次重复整个曲库时，都会将当前序列的第一首歌移动到序列的末尾。
例如，当 $k = 4$ 时，曲库初始为 ABCD，那么母带 $t$ 就是无限长的字符串 ABCD BCDA CDAB DABC ABCD ...。

有一个长度为 $n$ 的播放列表，初始时全部为空白。在此问题中，播放列表和母带均从 1 开始索引。

操作要求
需要对播放列表执行 $q$ 次操作，操作分为以下两种：

+ i a b：将播放列表中从位置 $a$ 到 $b$ （包含两端）的片段，替换为母带 $t$ 中从位置 $i$ 开始、长度为 $b - a + 1$ 的子串。
? a b：查询播放列表中从位置 $a$ 到 $b$ （包含两端）的片段。输出 $k$ 个整数，其中第 $j$ 个整数表示该片段中第 $j$ 个英文字母（即第 $j$ 首歌）的出现次数。

输入格式
第一行包含三个空格分隔的整数 $k$ 、 $n$ 和 $q$ 。
接下来 $q$ 行，每行描述一个操作，格式为 + i a b 或 ? a b。

输出格式
对于每一个 ? a b 操作，输出一行包含 $k$ 个空格分隔的整数，表示查询的结果。

数据范围
$1 \le k \le 26$
$1 \le n \le 10^9$
$1 \le q \le 10^5$
每次操作中： $1 \le i \le 10^9$ ， $1 \le a \le b \le n$

样例输入

样例输出

1 2 1 1

样例解释
在此样例中， $k = 4$ 且 $n = 10$ 。母带 $t$ 为 ABCDBCDACDABDABC...。
播放列表初始为空，我们用星号代表空白部分：**********。

执行 + 7 2 6：
我们需要一个长度为 $6 - 2 + 1 = 5$ 的子串。
母带 $t$ 中从位置 7 开始、长度为 5 的子串是 DACDA。
将播放列表中第 2 到第 6 首歌替换为该子串，此时播放列表变为：DACDA****。
执行 + 2 8 10：
播放列表第 8 到 10 的位置被替换后变为：DACDA*BCD。
执行 + 9 1 4：
覆盖掉前 4 个位置的歌曲，播放列表最终变为：CDABDA*BCD。
执行 ? 4 9：
查看当前播放列表中第 4 到第 9 首歌，对应片段为 BDA*BC。
需要输出 A、B、C、D 四个字母在此片段内分别出现的次数。因此，输出 1 2 1 1。

思路讲解

其实还是很明显的动态开点线段树。我说白了是个动态开点线段树的云玩家，我都看出来是动态开点线段树了。

P13825 【模板】线段树 1.5（指针式动态开点线段树）

既然是这个动态开点线段树，我们想一想，我们的 apply 函数如何书写吧。

其实最重要的是，在知道母带上 l，r 的情况下，求出母带上的 cnt 数组。

get_range_cnt，可以变为 get_pref_cnt®-get_pref_cnt(l - 1)，是一个非常经典的套路。

array<int, 26> get_range_cnt(ll l, ll r) {
    auto R = get_pref_cnt(r);
    auto L = get_pref_cnt(l - 1);
    for (int i = 0; i < k; ++i) {
        R[i] -= L[i];
    }
    return R;
}

AC代码

AC
https://codeforces.com/gym/106262/submission/365836934

源代码

/**
 * Problem: B. DJ Nicholas
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/B
 * Created: 2026-03-04 17:34:48
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

// static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
// static constexpr ll mod = 998244353; // (ll)1e9+7;
// static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

ll K;
/*
 *
 */
using arr=array<unsigned int,27>;
bool is_init=false;
vector<vector<ll>> next_ch_rem_pos(28,vector<ll>(28));
arr get_pref(ll r) {
    arr res{};
    if (r==0) {
        return res;
    }

    if (!is_init) {
        vector<ll> str(K*K+2);
        for (int i=1;i<=K;++i) {
            for (int j=1;j<=K;++j) {
                str[K*(i-1)+j]=j;
            }
        }
        for (int i=1;i<=K;++i) {
            rotate(str.begin()+K*(i-1)+1,str.begin()+K*(i-1)+i,str.begin()+K*(i-1)+K+1);
        }
        // 怕这个遍历影响常数？直接存下来不就行了？
        for (int ch=1;ch<=K;++ch) {
            for (int i=1;i<=K*K;++i) {
                if (str[i]==ch) {
                    next_ch_rem_pos[ch][((i-1)/K)]=i;
                }
            }
        }
        is_init=true;
    }

    for (int i=1;i<=K;++i) {
        res[i]+=r/K;
        ll rot=((r/K*K+1-1)/K)%K;
        ll next_pos=next_ch_rem_pos[i][rot]+r/(K*K)*(K*K);
        if (next_pos<=r) {
            ++res[i];
        }
    }
    return res;
}
arr operator-(arr a, arr b) {
    for (int i=1;i<=K;++i) {
        a[i]-=b[i];
    }
    return a;
}
arr get_range(ll l,ll r) {
    // st 是 1-based，我们先切换成 0-based
    return get_pref(r)-get_pref(l-1);
}
struct Tag {
    // 在母串中的这个位置
    ll base=0;
    bool need_apply=false;
    void apply(const Tag &t,ll offset) {
        base=t.base+offset;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    arr cnt{};
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        for (int i=1;i<=26;++i) {
            res.cnt[i]+=b.cnt[i];
        }
        return res;
    }
    void apply(const Tag&t,ll offset) {
        if (!t.need_apply) return;
        cnt=get_range(t.base+offset,t.base+offset+r-l);
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
// template<class I=Info,class T=Tag>
struct SEG {
    // 如果不需要泛型，可以用下面的来替代
    using I=Info;
    using T=Tag;
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag,0);
            u->rs->info.apply(u->tag,u->rs->info.l - u->info.l);
            u->ls->tag.apply(u->tag,0);
            u->rs->tag.apply(u->tag,u->rs->info.l - u->info.l);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,T t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t,u->info.l-l);
            u->tag.apply(t,u->info.l-l);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

void Solve() {
    ll N,Q;
    cin >> K >> N >> Q;
    SEG seg(N);
    for (int i=1;i<=Q;++i) {
        char op;
        cin>>op;
        if (op=='+') {
            ll base,l,r;
            cin>>base>>l>>r;
            seg.modify(seg.root,l,r,{base,true});
        }else {
            ll l,r;
            cin>>l>>r;
            Info res=seg.query(seg.root,l,r);
            for (int j=1;j<=K;++j) {
                cout<<res.cnt[j]<<" ";
            }
            cout<<"\n";
        }
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106262/submission/365836934

*/

心路历程（WA，TLE，MLE……）

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——D. Drinking Culture（把概率，转化为可行域面积占总面积的比重，这一点对两参数随意取的概率问题特别有用，三参数随意取的就是算体积占比？我猜）

Posted on 2026-03-07 Edited on 2026-04-06

题目大意

题目总结

Bob 有 $n$ 瓶酒精饮料，标号为 $1$ 到 $n$ 。已知第 $i$ 瓶饮料包含 $v_i$ 单位的液体体积，其中有 $a_i$ 单位是纯酒精（ $0 \le a_i \le v_i$ ）。因此，第 $i$ 瓶饮料的酒精浓度为 $a_i / v_i$ 。每瓶饮料是完全均匀的，从中取出任意体积的液体，其酒精浓度均保持不变。

Bob 可以从这些瓶子中选择任意组合，并从每瓶中取出任意体积（不必须为整数）的液体进行混合。

现在提出一个挑战：
令 $V = \sum_{i=1}^n v_i$ 为所有瓶子中液体的总体积。
在 $[0, V]$ 区间内均匀随机生成一个实数 $s$ （目标总体积）；
在 $[0, 1]$ 区间内均匀随机生成一个实数 $f$ （目标酒精浓度）。

请计算：Bob 能够成功调配出总体积恰好为 $s$ 、且酒精浓度恰好为 $f$ 的饮品的概率是多少？（输出结果与标准答案的绝对或相对误差需不超过 $10^{-8}$ ）。

输入格式
第一行包含一个整数 $n$ （ $2 \le n \le 2 \times 10^5$ ）。
第二行包含 $n$ 个整数，依次为 $v_1, v_2, \dots, v_n$ （ $1 \le v_i \le 10^9$ ）。
第三行包含 $n$ 个整数，依次为 $a_1, a_2, \dots, a_n$ （ $0 \le a_i \le v_i$ ）。

样例输入

1
2
3

3
350 750 330
140 131 16

样例输出

1	0.19356182654786474591

样例解释
在这个样例中，所有液体的总体积 $V = 350 + 750 + 330 = 1430$ 。

我们可以考虑两种具体的情况：
第一种情况：假设生成的 $s = 500$ 且 $f = \frac{3}{13}$ 。此时 Bob 是可以成功调配的。例如，他可以从第 $1$ 瓶中取出 $\frac{97750}{377}$ 单位的液体，从第 $3$ 瓶中取出 $\frac{90750}{377}$ 单位的液体。
调配出的总体积为 $\frac{97750}{377} + \frac{90750}{377} = \frac{188500}{377} = 500$ 。
调配出的酒精浓度为：

\frac{\frac{97750}{377} \times \frac{140}{350} + \frac{90750}{377} \times \frac{16}{330}}{500} = \frac{3}{13}

第二种情况：假设生成的 $s = 814$ 且 $f = 0.1234567$ 。此时 Bob 是无法完成调配的，因为利用他现有的饮料集合无法混合出该体积和浓度的饮品。

综合考虑所有可能在给定范围内均匀生成的 $s$ 和 $f$ 的数值对 $(s, f)$ ，Bob 能够成功调配的概率约为 $0.19356182654786474591$ 。

思路讲解

把概率，转化为可行域面积占总面积的比重，这一点对两参数随意取的概率问题特别有用。

具体而言，我们的这个分段函数应该长这样：

其不定积分是长这样的，带进去值，算一下定积分即可。

AC代码

AC
https://qoj.ac/submission/2106344
AC
https://codeforces.com/gym/106262/submission/365722146

源代码

/**
 * Problem: D. Drinking Culture
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/D
 * Created: 2026-03-07 17:50:25
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = long double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct V_A {
    ll v,a;
    // concentration
    DB c;
};
DB calVal(ll A,ll V,DB c,ll x) {
    if (x<=0) {
        return 0;
    }
    DB res=A*log(x)+c*x-c*V*log(x);
    return res;
}
void Solve() {
    ll N;
    cin >> N;
    // vector<ll> A(N+2),V(N+2);
    vector<V_A> wine_inc(N+2);
    ll sumv=0;
    for (int i=1;i<=N;++i) {
        cin>>wine_inc[i].v;
        sumv+=wine_inc[i].v;
    }
    for (int i=1;i<=N;++i) {
        cin>>wine_inc[i].a;
        wine_inc[i].c=DB(wine_inc[i].a)/wine_inc[i].v;
    }
    vector<V_A> wine_dec=wine_inc;
    sort(wine_inc.begin()+1,wine_inc.begin()+N+1,[](const V_A &a,const V_A &b) {
        return a.c<b.c;
    });
    sort(wine_dec.begin()+1,wine_dec.begin()+N+1,[](const V_A &a,const V_A &b) {
        return a.c>b.c;
    });
    DB mn_area=0;
    do {
        ll upA=0;
        ll upV=0;
        for (int i=1;i<=N;++i) {
            ll curV=upV+wine_inc[i].v;
            mn_area+=calVal(upA,upV,wine_inc[i].c,curV)-calVal(upA,upV,wine_inc[i].c,upV);
            upA=upA+wine_inc[i].a;
            upV=upV+wine_inc[i].v;
        }
    }while (false);
    DB mx_area=0;
    do {
        ll upA=0;
        ll upV=0;
        for (int i=1;i<=N;++i) {
            ll curV=upV+wine_dec[i].v;
            mx_area+=calVal(upA,upV,wine_dec[i].c,curV)-calVal(upA,upV,wine_dec[i].c,upV);
            upA=upA+wine_dec[i].a;
            upV=upV+wine_dec[i].v;
        }
    }while (false);
    DB area=mx_area-mn_area;
    DB ans=area/sumv;
    cout<<fsp(15)<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2106344
AC
https://codeforces.com/gym/106262/submission/365722146

*/

心路历程（WA，TLE，MLE……）

注意，分段函数不是线性的，而是一个分段反比例函数。

不要一会用 x，一会用 v，但是代表同一个意思。

2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——I. Stone Steps（在解决样例中出现的问题的时候，处理问题的方式尽量的这个能够和原来的方式有所关联，或者说，样例中出现的问题是提示我们思路中的漏洞，我们最好进行重新推导）

Posted on 2026-03-07 Edited on 2026-04-06

题目大意

题目名称： Stone Steps

题目描述：
给定一个仅包含非零十进制数字的字符串 $s$ （长度 $1 \le |s| \le 5 \times 10^5$ ）。

对于任意不包含数字 0 的正整数 $n$ ，定义 $H(n)$ 为将 $n$ 的所有数位按非降序（从小到大）重新排序后得到的新整数。例如： $H(1971) = 1179$ ， $H(3) = 3$ 。

你的任务是计算字符串 $s$ 的所有非空连续子串所代表的十进制整数的 $H$ 函数值之和。即对于所有满足 $1 \le i \le j \le |s|$ 的子串 $s[i...j]$ ，求出 $H(s[i...j])$ 并求和。最终的结果需要对 1000696967 取模后输出。

输入格式：
单行输入一个字符串 $s$ 。

输出格式：
输出一个整数，表示所有非空连续子串的 $H$ 函数值之和对 1000696967 取模的结果。

样例 1：

输入：
3141

输出：
1432

样例 1 解释：
当 $s$ 为 3141 时，共有 10 个非空连续子串，计算过程如下：

$s[1...1]$ 为 3， $H(3) = 3$
$s[2...2]$ 为 1， $H(1) = 1$
$s[3...3]$ 为 4， $H(4) = 4$
$s[4...4]$ 为 1， $H(1) = 1$
$s[1...2]$ 为 31， $H(31) = 13$
$s[2...3]$ 为 14， $H(14) = 14$
$s[3...4]$ 为 41， $H(41) = 14$
$s[1...3]$ 为 314， $H(314) = 134$
$s[2...4]$ 为 141， $H(141) = 114$
$s[1...4]$ 为 3141， $H(3141) = 1134$

将其相加得： $3 + 1 + 4 + 1 + 13 + 14 + 14 + 134 + 114 + 1134 = 1432$ 。

样例 2：

输入：
1

输出：
1

样例 3：

输入：
11234567891234567891

输出：
43138332

思路讲解

还是要使用拆分算贡献的思想。

我们还需要利用一个东西，就是数位，其实只有 9 个，所以我们不用想着一次遍历去解决，可以遍历 9 次。

不过，我认为最有用的，还是把这个所有的东西，贡献，全部写下来。然后看看有什么规律。全部都写下来以后，我们发现这个规律非常的简单。

然后就跟着上面的这个公式求就完了。

以样例一具体而言就是：

推这种式子就是要细心。

AC代码

https://codeforces.com/gym/106262/submission/365694725

源代码

/**
 * Problem: I. Stone Steps
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/I
 * Created: 2026-03-07 12:15:37
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10/*, INF = (1ll<<61)-1*/;
static constexpr ll mod = 1000696967;
// static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
ll pow10[MAXN];
void Solve() {
    string s;
    cin>>s;
    ll N=SZ(s);
    s.insert(s.begin(),'#');
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        A[i]=s[i]-'0';
    }
    ll ans=0;
    // set<ll> st_pos;
    for (int d=1;d<=9;++d) {
        vector<ll> suf_sum_diff_gt_d(N+2)/*,suf_cnt_gt_d(N+2)*/;
        vector<ll> suf_pos(N+2);
        suf_pos[N+1]=N+1;
        do {
            vector<ll> i_vec;
            i_vec.push_back(N+1);
            for (ll i=N;i>=1;--i) {
                suf_sum_diff_gt_d[i]=suf_sum_diff_gt_d[i+1];
                suf_pos[i]=suf_pos[i+1];
                // suf_cnt_gt_d[i]=suf_cnt_gt_d[i+1];
                if (A[i]>=d) {
                    suf_sum_diff_gt_d[i]+=i_vec.back()-i;
                    suf_sum_diff_gt_d[i]*=10;
                    suf_sum_diff_gt_d[i]%=mod;
                    suf_pos[i]=i;
                    i_vec.push_back(i);
                    // suf_cnt_gt_d[i]++;
                }
            }
        }while (false);

        vector<ll> i_pos;
        // 哨兵节点
        i_pos.push_back(0);
        ll glo_sum=0;
        for (int i=1;i<=N;++i) {
             if (A[i]>d) {
                 glo_sum*=10;
                 glo_sum%=mod;
                 glo_sum+=i-i_pos.back();
                 i_pos.push_back(i);
             }else if (A[i]==d) {
                 ll sum=glo_sum;
                 sum*=10;
                 sum%=mod;
                 sum+=i-i_pos.back();
                 // lsum 是在前面的，所有的值的条件下，的贡献
                 ll lsum=A[i]*sum%mod;
                 // lans 是算的是后面的
                 ll lans=sum*suf_sum_diff_gt_d[i+1]%mod;
                 lans+=sum*(suf_pos[i+1]-(i+1))%mod;
                 lans%=mod;
                 lans*=A[i];
                 lans%=mod;
                 ans+=lans;
                 ans+=lsum;
                 ans%=mod;
                 ans%=mod;
             }
        }
    }
    ans%=mod;
    if (ans<0) {
        ans+=mod;
    }
    cout<<ans<<"\n";
    // mod 1000696967
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    pow10[0]=1;
    for (int i=1;i<=MAXN-5;++i) {
        pow10[i]=pow10[i-1]*10;
        pow10[i]%=mod;
    }
    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

_______________[ Stress test, testcase 14 INPUT ]_______________
832

_______________[ Stress test, testcase 14 OUTPUT]_______________
282

expected：312

*/

心路历程（WA，TLE，MLE……）

在处理 lans，也就是背后的时候，忘记处理了不含 i7 的情况，即什么都不含，只含 i5 的背后情况。