ABC426不太全题解

复仇者_澜（不处不加团队）

2025-10-09 13:47:11

发布于：广东

6阅读

0回复

0点赞

前话：这是一篇迟来了5天的题解[狗头保命]

A&B：

若只题不讲。

C：

个人难度：橙上 $\sim$ 黄下

暴力算法：

模拟全过程，时间复杂度 $O(NQ)$ ，显然超时。

正解算法：

注意到本题最大的版本仅为 $N$ ，我们考虑从这里入手。

由于题目只让我们求升级的台数，我们可以定义数组 $p$ ，其中 $p(i)$ 表示操作系统版本为 $i$ 的数量。

再定义变量 $cur$ 表示当前最小版本，对于每次询问，需要更新的数量就是 $\sum_{i=cur}^x p(i)$ 。随后将 $p(y)$ 加上前式，并且更新 $cur=x+1$ 。

最后输出答案即可。

$\tt{ACCODE:}$

#include<bits/stdc++.h>
using namespace std;
int p[1000009];
int main(){
    int n,q,cur = 1;
    cin>>n>>q;
    for(int i = 1;i<=n;++i) p[i] = 1;
    while(q--){
        int x,y;
        cin>>x>>y;
        int ans = 0;
        while(cur<=x){
            ans+=p[cur];
            p[y]+=p[cur];
            cur++;
        }
        cout<<ans<<endl;
    }
}