算法入门-前缀和和差分数组

BGN51 静态区间和（前缀和）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//
// Created by XIAOBAI on 2026/5/21.
//静态区间和（前缀和）

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
bool is_prime(ll a) {
    for (ll i=2;i*i<=a;i++) {
        if (a%i==0) return false;
    }
    return true;
}
void solve() {
    ll n,q;
    cin>>n>>q;
    vector<ll> v(n+1,0);
    vector<ll> qzh(n+1,0);
    for (ll i=1;i<=n;i++) {
        cin>>v[i];
        qzh[i]=qzh[i-1]+v[i];
    }
    for (ll i=1;i<=n;i++) {
        cout<<qzh[i]<<" ";
    }
    while (q--) {
        ll L,R;
        cin>>L>>R;
        cout<<qzh[R]-qzh[L-1]<<'\n';
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN52 模版 差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//
// Created by XIAOBAI on 2026/5/21.
//模版 差分

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
bool is_prime(ll a) {
    for (ll i=2;i*i<=a;i++) {
        if (a%i==0) return false;
    }
    return true;
}
void solve() {
    ll n,m;
    cin>>n>>m;
    vector<ll> v(n+1,0);
    vector<ll> b(n+1,0);//差分数组，用于存增量，这样通过一次遍历得到所有增量
    for (ll i=1;i<=n;i++) {
        cin>>v[i];
    }
    while (m--) {
        ll L,R,K;
        cin>>L>>R>>K;
        b[L]+=K;//在增量数组的L位置+k，R+1位置-k，遍历后就可以只在L~R区域内得到增量！
        if(R+1<=n)b[R+1]-=K;
    }
    for (ll i=1;i<=n;i++) {
        b[i]+=b[i-1];//遍历得到所有位置增量
    }
    for (ll i=1;i<=n;i++) {
        cout<<v[i]+b[i]<<" ";//原数组的值加上差分数组值就是加完的
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN53 舞萌时间到！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//
// Created by XIAOBAI on 2026/5/21.
//舞萌时间到！

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    string s;
    cin>>s;
    ll q,n=s.size();
    cin>>q;
    vector<ll> dx(n+1,0);
    vector<ll> qzh(n+1,0);
    for(int i=1;i<=n;i++) {
        if (s[i-1]=='P') dx[i]=3;
        else if (s[i-1]=='p') dx[i]=2;
        else if (s[i-1]=='G') dx[i]=1;
        else dx[i]=0;
        qzh[i]=qzh[i-1]+dx[i];
    }
    while(q--) {
        ll L,R;
        cin>>L>>R;
        cout<<qzh[R]-qzh[L-1]<<'\n';
    }

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN54 牛牛与切割机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//
// Created by XIAOBAI on 2026/5/28.
//牛牛与切割机

#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n,sum=0,ans=LLONG_MAX,have=0;
    cin>>n;
    vector<ll> v(n+1);
    vector<ll> qzh(n+1);
    for (ll i=1; i<=n; i++) {
        cin>>v[i];
        sum+=v[i];
    }
    for (int i=1; i<n; i++){
        have+=v[i];sum-=v[i];
        ans=min(ans,have*sum);
    }
    cout<<ans<<'\n';

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN55

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//
// Created by XIAOBAI on 2026/5/30.
//
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n,Mas=-1,Mac=-1;
    vector<ll> v(1e6+7,0);
    cin>>n;
    while(n--) {
        ll a,b;
        cin>>a>>b;
        v[a]++;
        v[b+1]--;
        Mas=max(Mas,b);
    }

    for (ll i=1;i<=Mas+1;i++) {//注意处理边界问题
        v[i]=v[i-1]+v[i];
        Mac=max(Mac,v[i-1]);
        //cout<<v[i-1];
        // cout<<v[i-1]<<" ";
    }
    cout<<Mac;

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN56 【模板】二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//
// Created by XIAOBAI on 2026/5/30.
//【模板】二维前缀和
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n,m,q;
    cin>>n>>m>>q;
    vector<vector<ll>> a(n+1,vector<ll>(m+1,0));
    vector<vector<ll>> qzh(n+1,vector<ll>(m+1,0));
    for (ll i=1;i<=n;i++) {
        for (ll j=1;j<=m;j++) {
            cin>>a[i][j];
        }
    }
    for (ll i=1;i<=n;i++) {
        for (ll j=1;j<=m;j++) {
            qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+a[i][j];
        }
    }
    while(q--) {
        ll x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<(qzh[x1-1][y1-1]+qzh[x2][y2]-qzh[x1-1][y2]-qzh[x2][y1-1])<<'\n';
    }



}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN57 【模板】二维差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//
// Created by XIAOBAI on 2026/5/30.
//【模板】二维差分
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n,m,q;
    cin>>n>>m>>q;
    vector<vector<ll>> a(n+2,vector<ll>(m+2,0));
    vector<vector<ll>> qzh(n+2,vector<ll>(m+2,0));
    for (ll i=1;i<=n;i++) {
        for (ll j=1;j<=m;j++) {
            cin>>a[i][j];
        }
    }

    while (q--) {
        ll x1,y1,x2,y2,k;
        cin>>x1>>y1>>x2>>y2>>k;
        qzh[x1][y1]+=k;
        qzh[x2+1][y2+1]+=k;
        qzh[x1][y2+1]-=k;
        qzh[x2+1][y1]-=k;

    }
    for (ll i=1;i<=n;i++) {
        for (ll j=1;j<=m;j++) {
            qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+qzh[i][j];
        }
    }
    for (ll i=1;i<=n;i++) {
        for (ll j=1;j<=m;j++) {
            cout<<a[i][j]+qzh[i][j]<<" ";
        }
        cout<<'\n';
    }




}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN58 空间跃迁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//
// Created by XIAOBAI on 2026/6/2.
//空间跃迁
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n+1,0),qzh(n+1,0);
    for (ll i=1;i<n;i++) {
        cin>>a[i];
        qzh[i]=a[i]+qzh[i-1];
    }

    ll sum=0;
    if (k==0) cout<<qzh[n-1];
    else {
        for (ll i=1;i<=n-k;i++) {
            sum=max(qzh[i+k-1]-qzh[i-1],sum);
        }
        cout<<qzh[n-1]-sum;
    }




}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN59

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//
// Created by XIAOBAI on 2026/6/2.
//
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n+2,0),qzh(n+2,0);
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        qzh[i]=a[i]+qzh[i-1];
    }
    ll sum=0;
    for (int i=2;i<=n;i++) {
        if (qzh[i]>=0) {
            sum+=qzh[i];
        }
    }
    cout << sum;

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN60

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//
// Created by XIAOBAI on 2026/6/2.
//
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n,m;
    cin>>n>>m;
    vector<vector<int>> dx(n+2,vector<int>(3,0));
    while (m--) {
        ll L,R,k;
        cin>>L>>R>>k;
        k--;
        dx[L][k]++;dx[R+1][k]--;
    }
    ll ans=0;
    for (int i=1;i<=n;i++) {
        for (int j=0;j<3;j++) {
            dx[i][j]=dx[i-1][j]+dx[i][j];
        }
        if (dx[i][0]&&dx[i][1]&&!dx[i][2]) ans++;
    }
    cout<<ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN61

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//
// Created by XIAOBAI on 2026/6/2.
//
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n;
    cin>>n;
    string a="0",b="1",c="";
    for (int i=2;i<n;i++) {
        c=a+b;
        a=b;
        b=c;
    }
    ll sz=c.size(),Y=0,sum=0;
    for (int i=0;i<sz;i++) {
        if (c[i]=='1') {Y++;}
        else {sum+=Y;sum%=MOD1;}
    }
    cout<<sum<<'\n';

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }

}