尺取法 前缀和 差分 单调队列

· · 算法·理论

尺取法

算法介绍

参照博客

例题

P1147 连续自然数和
#include<bits/stdc++.h>
using namespace std;
int s;
int a[2000010];
int main(){
    cin>>s;
    for(int i=1;i<=s;i++){
        a[i]=i;
    }
    int l=1,r=1,sum=a[1];
    while(l<s&&r<s){
        if(sum>=s){
            if(sum==s)cout<<l<<" "<<r<<endl;
            sum=sum-a[l++];
            if(l>r)sum=sum+a[++r];
        }
        if(sum<s){
            sum=sum+a[++r];
        }
    }
}

一维前缀和

前缀和：1~i个数的和

例题

P8218 【深进1.例1】求区间和
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int a[100010],b[100010];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    b[1]=a[1];
    for(int i=2;i<=n;i++){
        b[i]=b[i-1]+a[i];
    }
    int k,x,y;
    cin>>k;
    for(int i=1;i<=k;i++){
        cin>>x>>y;
        cout<<b[y]-b[x-1]<<endl;
    }
    return 0;
}

二维前缀和

参考理解

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,q;
int s[N][N];
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    while(q--){
        int x1,x2,y1,y2;
        cin>>x1>>x2>>y1>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
    return 0;
}

一维差分

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    int l,r,c;
    while(m--){
        cin>>l>>r>>c;
        b[l]+=c;
        b[r+1]-=c;
    }
    for(int i=1;i<=n;i++){
        b[i]=b[i]+b[i-1];
        cout<<b[i]<<" ";
    }
    return 0;
}

二维差分

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++ )
        for(int j=1;j<=m;j++ )
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            b[i][j]=a[i][j]+a[i-1][j-1]-a[i-1][j]-a[i][j-1];//构建差分数组 
    while(q--){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];//二维前缀和 
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++)cout<<b[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}

单调队列

P1886 滑动窗口 /【模板】单调队列

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N];//a数组储存元素值，q数组模拟队列
int n,k; 
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    //求滑动窗口的最小值 
    int h=1,t=0;
    for(int i=1;i<=n;i++){
        while(h<=t&&a[q[t]]>=a[i])t--;//队列不空且新元素更优时 
        q[++t]=i;//队列里存储元素下标 
        if(q[h]<i-k+1)h++;//队头元素滑出窗口
        if(i>=k)cout<<a[q[h]]<<" "; //输出最小值 
    }
    cout<<endl;
    //求滑动窗口的最大值 
    h=1,t=0;//初始化首位指针 
    for(int i=1;i<=n;i++){
        while(h<=t&&a[q[t]]<=a[i])t--;//队列不空且新元素更优时 
        q[++t]=i;//队列里存储元素下标 
        if(q[h]<i-k+1)h++;//队头元素滑出窗口
        if(i>=k)cout<<a[q[h]]<<" "; //输出最大值 
    }
    return 0;
}

单调栈

P5788 【模板】单调栈

#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,int >P;
stack<P>s;
int n,ans[3000010],a[3000010];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        while(!s.empty()&&s.top().first<a[i]){
            ans[s.top().second]=i;
            s.pop();
        }
        s.push({a[i],i});
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";

}

离散化

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int len=unique(a+1,a+n+1)-(a+1);
    for(int i=1;i<=len;i++){
        cout<<a[i]<<" ";
        a[i]=lower_bound(a+1,a+n+1,a[i])-a;
        cout<<a[i]<<endl;
    }
    return 0;
}

倍增-ST算法

P3865 【模板】ST 表

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000010];
int f[1010000][50];//f[i][j]以第i为起点，长度为2^j的最大值 
void ST_create(){
    for(int i=1;i<=n;i++)f[i][0]=a[i];
    int k=log2(n);
    for(int j=1;j<=k;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//倍增区间最大值 
        }
    }
}
int ST_query(int l,int r){
    int k=log2(r-l+1);//r-l+1区间长度 
    return max(f[l][k],f[r-(1<<k)+1][k]);//区间最大值 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    ST_create();
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        int ans=ST_query(l,r);
        printf("%d\n",ans);
    }
}