資料結構--ST表

前言：雖然ST表功能不是很多，但是如果涉及到取MAX或取MIN時，ST表無疑是一種很好的選擇。

https://www.luogu.com.cn/problem/P3865（模闆題）

#include<bits/stdc++.h>
#define re register
using namespace std;
const int maxn=1e6+10;
int n,m,f[maxn][23];
int query(int x,int y){
    int k=log2(y-x+1);
    return max(f[x][k],f[y-(1<<k)+1][k]);
}
int main(){
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>f[i][0];
    int k=log2(n);
    for(int j=1;j<=21;j++){
        for(int i=1;i+(1<<j)-1<=n;++i){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    for(re int i=1;i<=m;++i){
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
    return 0;
}      

View Code

https://www.luogu.com.cn/problem/P1198最大數

大概每次能在最後面動态加點，花log的時間修改即可

#include<bits/stdc++.h>
using namespace std;
const long long inf=-(1<<62);
int m,cnt;
char op[2];
long long data[800005],x,t,p;
void add(int s,int k,int o,int l,int r)
{
    if(l==r)
    {
        data[o]=k;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=s) add(s,k,o<<1,l,mid);
    if(mid<s) add(s,k,o<<1|1,mid+1,r);
    data[o]=max(data[o<<1],data[o<<1|1])%p;
}
long long ask(int ll,int rr,int o,int l,int r)
{
    if(ll<=l&&rr>=r) return data[o];
    int mid=(l+r)>>1;
    long long a=inf,b=inf;
    if(mid>=ll) a=ask(ll,rr,o<<1,l,mid);
    if(mid<rr) b=ask(ll,rr,o<<1|1,mid+1,r);
    return max(a,b);
}
int main()
{
    scanf("%d %lld",&m,&p);
    for(int i=0; i<m; i++)
    {
        scanf("%s %lld",op,&x);
        if(op[0]=='A')
        {
            add(cnt+1,(x+t)%p,1,1,m);
            cnt++;
        }
        if(op[0]=='Q')
        {
            if(x==0) t=0;
            else t=ask(cnt-x+1,cnt,1,1,m)%p;
            printf("%lld\n",t);
        }
    }
    return 0;
}      

https://www.luogu.com.cn/problem/P2048

超級鋼琴

之前就一直聽說過得資料結構題。

打暴力的話大概就是處理每一個長度在l-r的區間，排序。

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
long long sum[maxn],f[maxn][22];
struct node{
    int o,l,r,t;
    bool operator < (const node &tt) const{
    return sum[t]-sum[o-1]<sum[tt.t]-sum[tt.o-1];}
};
priority_queue<node> q;
void init(int n){
    for(int i=1;i<=n;++i) f[i][0]=i;
    for(int j=1;(1<<j)<=n;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            int x=f[i][j-1],y=f[i+(1<<(j-1))][j-1];
            f[i][j]=sum[x]>sum[y]?x:y;
        }
    }

}    
int query(int l,int r){
        int k=log2(r-l+1);
        int x=f[l][k],y=f[r-(1<<k)+1][k];
        return sum[x]>sum[y]?x:y;
    }
int n,k,l,r;
int main(){
    cin>>n>>k>>l>>r;
    for(int i=1;i<=n;++i){
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }
    init(n);
    for(int i=1;i<=n;++i){
        if(i+l-1<=n)
        q.push(node{i,i+l-1,min(i+r-1,n),query(i+l-1,min(i+r-1,n))});
    }
    long long ans=0;
    while(k--){
        int o=q.top().o;
        int l=q.top().l;
        int r=q.top().r;
        int t=q.top().t;
        q.pop();
        ans+=sum[t]-sum[o-1];
        if(l!=t) q.push(node{o,l,t-1,query(l,t-1)});
        if(r!=t) q.push(node{o,t+1,r,query(t+1,r)});
    }
    cout<<ans<<endl;
    return 0;
}