TLE

P2367 语文成绩

pppppLF @ 2023-05-30 21:32:05

话不多说上代码

#include <bits/stdc++.h>
using namespace std;
int a[5000005]; 
int main(){
    int n,p,x,y,z;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=p;i++){
        cin>>x>>y>>z;
        for(int i=x;i<=y;i++){
            a[i]+=z;
        }
    }
    sort(a+1,a+n+1);
    cout<<a[1];
   return 0;
}

by huangruiheng0217 @ 2023-05-30 21:35:45

有个东西叫差分，你这复杂度明显不对

by pppppLF @ 2023-05-30 21:40:12

差分？？？

by jomy @ 2023-05-30 21:42:35

@pppppLF n\le5×10^6,p\le n

for(int i=1;i<=p;i++){
        cin>>x>>y>>z;
        for(int i=x;i<=y;i++){
            a[i]+=z;
        }
    }

这里复杂度 O(n^2) 过不了。

by jomy @ 2023-05-30 21:43:12

差分看题解

by yzm0325 @ 2023-05-30 21:55:59

@pppppLF 差分是个好东西，就是差分数组每项 f_i=a_i-a_{i-1}，区间修改只需要改两头就行了。

原数组 1 1 4 5 1 4
差分数组 0 0 0 0 0

更改：

原数组 0 0 \color{red}1 \color{red}1 \color{red}1 0
差分数组 0 \color{blue}-1 0 0 \color{blue}1 0

最后答案取一遍前缀和就行了

by yzm0325 @ 2023-05-30 21:56:19

@Zhuyiming0325 第一张表少个0，我是**

by yzm0325 @ 2023-05-30 21:57:47

@Zhuyiming0325 我服了，理解就行了第二张表错了

|