多重循环问题做时间的优化

Question

我的代码是这样的

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int day[N];
int tree[N],res[N]; // 
int n,m,k;
int main()
{
    cin >> n >> m >> k;
    for(int i = 1;i <= m;i ++)    // 天数
    {
        //每天固定加一
        int op,x;
        cin >> op >> x;
        if(op == 1)
        {
            res[x] = k;
        }
        else if(op == 2)
        {
            res[x] = 0;
        }
        else if(op == 3)
        {
            cout<<tree[x]<<endl;
        }
        for(int j = 1; j <= n;j ++)
        {
            tree[j] ++;
            if(res[j] != 0)
            {
                tree[j] ++;
                res[j] --;
            }
        }
        
        
    }
    
}

请问，如何做时间的优化使其通过，或者其他思路解决也行

Answer 1

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
这份代码的时间复杂度为 $O(nm)$，其中 $n$ 表示每天的树木数量，$m$ 表示天数。可以看到代码中有两层循环，所以时间复杂度比较高。

对于这个问题，可以考虑使用差分的思想进行优化。我们可以用一个数组 $day$ 记录每天树木的数量变化量，$day[i]$ 表示第 $i$ 棵树在当天的数量变化量。然后我们根据 $day$ 数组来更新每天的树木数量，最后输出第 $x$ 棵树的数量即可。

具体实现步骤如下：

1、初始化 $day$ 数组为全零。
2、对于每天输入的操作，根据操作类型和编号修改 $day$ 数组：
    a. 如果是操作类型 $1$，则将 $day[x]$ 加上 $k$，表示第 $x$ 棵树在当天增加 $k$ 个。
    b. 如果是操作类型 $2$，则将 $day[x]$ 减去之前的值，表示第 $x$ 棵树在当天数量不变。
    c. 如果是操作类型 $3$，则需要输出第 $x$ 棵树在当天的数量。
3、对于每天，遍历一遍 $day$ 数组，累加每棵树当天的变化量，得到每棵树最终的数量，并将其更新到 $tree$ 数组中。

这样做的时间复杂度为 $O(m+n)$，相比之前的方法有很大的提升。以下是实现代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int day[N], tree[N];

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= m; i++)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1) day[x] += k;
        else if (op == 2) day[x] -= day[x];
        else if (op == 3) cout << tree[x] << endl;
    }

    for (int i = 1; i <= n; i++)
    {
        tree[i] = day[i];
        if (i > 1) tree[i] += tree[i-1];
        cout << tree[i] << " ";
    }
    cout << endl;

    return 0;
}

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢