區間

[a,b]

掃描線

/*
 * b966. 3. 線段覆蓋長度
 * C++
 * AC (27ms, 1.3MB)
*/
#include<bits/stdc++.h>
using namespace std;

map<int,int>diff;

int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;++i){
		int a,b;
		cin >> a >> b;
		diff[a]++;
		diff[b]--;
	}
	//
	int sum = 0;
	int state = 0;
	auto last = diff.begin();
	for (auto it = diff.begin(); it != diff.end(); ++it) {
        if (state > 0) {
            sum += it->first - last->first; // length
        }
        state += it->second; // +1 -1
        last = it; // node
    }
    cout << sum << endl;
}

O(n) 最大值 最小值

/*
 * c435. MAX ! MAX ! MAX !
*/
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int M = INT_MIN;
    int m = INT_MAX;
    int ans = 0;
    for(int i=0;i<n;++i){
        int x;
        cin >> x;
        if(x>M){
            M = x;
            m = 999999;
        }
        if(x<m){
            m = x;
            ans = max(ans,M-m);
        }
    }
    cout << ans << endl;
}

前綴和

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

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;++i){
        cin >> a[i];
    }
    vector<int> prefix_sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = prefix_sum[i - 1] + a[i - 1];
    }
    return 0;
}

二維前綴和

/*
 * zerojudge
 * a694. 吞食天地二
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,m;
	while(cin >> n >> m){
		int sum[n+1][n+1];
		for (int i = 0; i <= n; ++i) {
	        for (int j = 0; j <= n; ++j) {
	            sum[i][j] = 0;
	        }
	    }
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				int value;
				cin >> value;
				sum[i][j] = sum[i-1][j] + sum[i][j-1] -sum[i-1][j-1] + value;
			}
		}
		//
		for(int i=0;i<m;++i){
			int r1,c1,r2,c2;
			cin >> r1 >> c1 >> r2 >> c2;
			cout << sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1]<< endl;
		}
	}
}

區間和

/*
 * AP325
 * P-1-6. 最接近的區間和
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin >> n;
	int b[n];
	b[0]=0;
	int sum=0;
	for(int i=1;i<n;i++){
		int x;
		cin >> x;
		sum+=x;
		b[i]=sum;
	}
	int k=11;
	int max[3]= {0,-1,0};
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(b[j]-b[i]<k && b[j]-b[i]>max[1]){
				max[1] = b[j]-b[i];
				max[0] = i;
				max[2] = j;
			}
		}
	}
	cout << "[" << max[0] << "," << max[2] << "]" << endl;
}

差分

/* 
 * CSES
 * Restaurant Customers
*/
#include<bits/stdc++.h>
using namespace std;

map<int,int>diff;

int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;++i){
		int a,b;
		cin >> a >> b;
		diff[a]++;
		diff[b]--;
	}
	int max=-999;
	int sum=0;
	for(auto it=diff.begin();it!=diff.end();++it){
		sum+=it->second;
		if(sum>max){
			max=sum;
		}
	}
	cout << max << endl;
}

最大區間和

/*
 * CSES
 * Maximum Subarray Sum
*/
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
 
    long long s = 0;
    long long mn = 0;
    long long ans = -99999;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        s += x; // 前綴和
        ans = max(ans, s - mn); // 最大區間和
        mn = min(mn, s); // 最小前綴和
    }
    cout << ans << endl;
}

稀疏表

/*
 * zerojudge
 * d539 - 區間 MAX
*/
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main() {
	fastio;
    int N;
    cin >> N;
    int LOG = log2(N) + 1;
    vector<vector<int>> st(N, vector<int>(LOG));
    vector<int> T(N);
    ////
    for (int i = 0; i < N; ++i) {
        cin >> T[i];
        st[i][0] = T[i];  // 初始化稀疏表的第一列，對應區間長度為 1
    }

    // 構建稀疏表
    for (int j = 1; (1 << j) <= N; ++j) {
        for (int i = 0; i + (1 << j) - 1 < N; ++i) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

    int M;
    cin >> M;
    while (M--) {
        int a, b;
        cin >> a >> b;
        a-=1;
        b-=1;
        if (a > b){
        	swap(a, b);
        }
        int len = b - a + 1;
        int k = log2(len);
        int result = max(st[a][k], st[b - (1 << k) + 1][k]);
        cout << result << endl;
    }

    return 0;
}