前缀和跟差分是逆运算

例题

POJ3061 Subsequence

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e5+100;
int prefix[maxn],input[maxn];
int main(){
    int t;
    cin >> t;
    while(t--){
        memset(prefix,0,sizeof prefix);
        memset(input,0,sizeof input);
        int n,s,res = maxn; 
        cin >> n >> s;
        for(int i=1;i<=n;i++){
            cin >> input[i];
            prefix[i] = prefix[i-1]+input[i];
        }
        int i=0,j = 1; 
        while(j<=n){
            if(prefix[j]-prefix[i]<s) j++;
            else{
                while(prefix[j]-prefix[i]>=s) i++;
                res = min(res,j-i+1);
            }
        }
        if(res!=maxn) cout << res << endl;
        else cout << "0" << endl;
    }
    return 0;
}

NC16561 国王的游戏

#include<iostream>
#include<cstring>
#include<algorithm> 
#include<vector>
using namespace std;
const int maxn = 1e5;
struct node{
    int x,y;
}arr[maxn];
bool cmp(node a,node b){
    return a.x*a.y < b.x*b.y;
}
vector<int> mul(vector<int>a, int b){   // 高精度乘法
    vector<int> res;
    int t = 0;
    for(int i=0;i<a.size();i++){
        t += a[i]*b;
        res.push_back(t%10);
        t /=10;
    }
    while(t){
        res.push_back(t%10);
        t/=10;
    }
    return res;
} 
vector<int> div(vector<int>a, int b){  // 高精度除法
    vector<int> res;
    int t = 0;
    for(int i=a.size()-1;i>=0;i--){
        t = t*10+a[i];
        int x = t/b;
        res.push_back(x);
        t %= b;
    }
    reverse(res.begin(),res.end());
    while(res.size()>1&&!res.back()) res.pop_back();    // 去除前导0
    return res;
} 
vector<int> max_vector(vector<int> a, vector<int> b){   //  比较大小
    if(a.size()>b.size()) return a;
    if(a.size()<b.size()) return b;    
    if(vector<int>(a.rbegin(),a.rend())>vector<int>(b.rbegin(),b.rend()))
        return a;
    else
        return b;
}
int main(){
    int n;
    cin >> n;
    for(int i=0;i<=n;i++){
        cin >> arr[i].x >> arr[i].y;
    }
    sort(arr+1,arr+n+1,cmp);
    vector<int> res(1,0), a(1,1);
    for(int i=0;i<=n;i++){
        if(i) res = max_vector(res,div(a,arr[i].y));
        a = mul(a,arr[i].x); 
    }
    for(int i=res.size()-1;i>=0;i--){
        cout << res[i];
    }
    cout << endl;
    return 0;
}

NC16649 校门外的树

L和 M版本
直接模拟，时间复杂度：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e5+10;
int f[maxn];
int main(){
    int L,M,x,y,res=0;
    cin >> L >> M;
    while(M--){
        cin >> x >> y;
        for(int i=x;i<=y;i++){
            f[i]=1;
        }
    } 
    for(int i=0;i<=L;i++){
        res += (f[i]==0);
    }
    cout << res << endl;
    return 0;
}

用差分+前缀和来做，时间复杂度：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e5+10;
int diff[maxn];
int main(){
    int L,M,x,y,res=0;
    cin >> L >> M;
    while(M--){
        cin >> x >> y;
        diff[x]--;
        diff[y+1]++;
    } 
    res += diff[0]==0;
    for(int i=1;i<=L;i++){
        diff[i] += diff[i-1];
        res += diff[i]==0;
    }
    cout << res << endl;
    return 0;
}

离散化的写法，复杂度：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;

struct node{
    int x,y;
}arr[maxn];
bool cmp(node a,node b){
    if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}
int main(){
    int L,M,x,y,res=0;
    cin >> L >> M;
    for(int i=1;i<=M;i++){
        cin >> arr[i].x >> arr[i].y;
    }
    sort(arr+1,arr+M+1,cmp);
    res += arr[1].y-arr[1].x+1;
    int right=arr[1].y;
    for(int i=2;i<=M;i++){
        if(arr[i].x>right){
            res += arr[i].y-arr[i].x+1;
            right = arr[i].y;
        }
        else if(arr[i].y>=right){
            res += arr[i].y-right;
            right = arr[i].y;
        }
    }
    cout << L-res+1 << endl;
    return 0;
}