ST表模板

P3865 【模板】ST 表 && RMQ 问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:区间最大值，模板题。

int n,m;
int arr[100005];
int f[100005][25];     (1<<20)=1e6
void init(){                                o(nlogn)for(int i=1;i<=n;i++) f[i][0]=arr[i];for(int j=1;j<=20;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]);}}
}
inline int query(int l,int r){         o(1)int k=log2(r-l+1);return max(f[l][k],f[r-(1<<k)+1][k]);
}
【模板】ST 表 && RMQ 问题
https://www.luogu.com.cn/problem/P3865
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>arr[i];init();while(m--){int l,r; cin>>l>>r;cout<<query(l,r)<<endl;}
}

P2251 质量检测 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:区间最小值，模板题。

int n,m;
int arr[1000006];
int f[1000006][25];   (1<<20)=1e6
void init(){for(int i=1;i<=n;i++) f[i][0]=arr[i];for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}
}
int query(int l,int r){int k=log2(r-l+1);return min(f[l][k],f[r-(1<<k)+1][k]);
}
P2251 质量检测
https://www.luogu.com.cn/problem/P2251
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>arr[i];init();for(int i=1;i+m-1<=n;i++){int l=i,r=i+m-1;cout<<query(l,r)<<endl;}
}

P2880 [USACO07JAN] Balanced Lineup G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:区间极差，也是模板题。

int n,q;
int arr[50004];
int mx[50004][25];
int mi[50004][25];
void init(){for(int i=1;i<=n;i++) mx[i][0]=arr[i],mi[i][0]=arr[i];for(int j=1;j<=20;j++){     枚举区间长度,因为是2^j,所以永远是偶数for(int i=1;i+(1<<j)-1<=n;i++){ 枚举区间起点,i+(1<<j)-1<=n保证了当前枚举的区间起点及长度不会超出nmx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);}}
}
int query(int l,int r){int k=log2(r-l+1);return max(mx[l][k],mx[r-(1<<k)+1][k])-min(mi[l][k],mi[r-(1<<k)+1][k]);
}
纯板子--区间询问极差
P2880 [USACO07JAN] Balanced Lineup G
https://www.luogu.com.cn/problem/P2880
void solve(){cin>>n>>q;for(int i=1;i<=n;i++) cin>>arr[i];init();while(q--){int l,r; cin>>l>>r;cout<<query(l,r)<<endl;}
}

[ABC352D] Permutation Subsequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路: 思维题，换个角度(下标)维护区间最大最小值。思想类似用树状数组求逆序对中,桶的作用转换之后实际上就是求区间长度为k的最小极差。

int n,k;
int arr[200005];
int mx[200005][25];
int mi[200005][25];
void init(){for(int i=1;i<=n;i++) mx[i][0]=arr[i],mi[i][0]=arr[i];for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);}}
}
int query(int l,int r){int x=log2(r-l+1);return max(mx[l][x],mx[r-(1<<x)+1][x])-min(mi[l][x],mi[r-(1<<x)+1][x]);
}
思维题，换个角度(下标)维护区间最大最小值。思想类似用树状数组求逆序对中,桶的作用
转换之后实际上就是求区间长度为k的最小极差
[ABC352D] Permutation Subsequence
https://www.luogu.com.cn/problem/AT_abc352_d
void solve(){cin>>n>>k;for(int i=1;i<=n;i++){int x; cin>>x;arr[x]=i;}init();int ans=INT_MAX;for(int i=1;i+k-1<=n;i++) ans=min(ans,query(i,i+k-1));cout<<ans;
}

P2866 [USACO06NOV] Bad Hair Day S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:ST表＋二分

法二:ST表,比单调栈麻烦,ST表预处理的是每个区间最大值,然后枚举i,二分区间右端点,进行o(1)查询[i+1,mid]是否合法
题目理解为每头牛向右看,有多少个比自己矮的,遇到第一个>=自己的就不算了.

int n;
int arr[80004];
法一:单调栈--题目理解为每个牛向左看,能看到多少个比自己高的,那么就是从左到右维护单调递减的栈
P2866 [USACO06NOV] Bad Hair Day S
https://www.luogu.com.cn/problem/P2866
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>arr[i];stack<int> stk;int ans=0;for(int i=1;i<=n;i++){if(stk.size()&&arr[i]<stk.top()) ans+=stk.size();else if(stk.size()&&arr[i]>=stk.top()){     取等,因为是从右往左看，同等身高的不能算while(stk.size()&&arr[i]>=stk.top()) stk.pop();ans+=stk.size();}stk.emplace(arr[i]);}cout<<ans;
}int n;
int arr[80004];
int f[80004][25];
void init(){for(int i=1;i<=n;i++) f[i][0]=arr[i];for(int j=1;j<=20;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]);  1<<(j-1)}}
}
int query(int l,int r){    o(1)int k=log2(r-l+1);return max(f[l][k],f[r-(1<<k)+1][k]);
}
法二:ST表,比单调栈麻烦,ST表预处理的是每个区间最大值,然后枚举i,二分区间右端点,进行o(1)查询[i+1,mid]是否合法
题目理解为每头牛向右看,有多少个比自己矮的,遇到第一个>=自己的就不算了.
P2866 [USACO06NOV] Bad Hair Day S
https://www.luogu.com.cn/problem/P2866
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>arr[i];init();int ans=0;for(int i=1;i<=n-1;i++){   o(nlogn)int l=i+1,r=n,res=i;while(l<=r){int mid=(l+r)>>1;if(query(i+1,mid)<arr[i]){res=mid;l=mid+1;}else r=mid-1;}ans+=res-i;}cout<<ans;
}

P7167 [eJOI2020 Day1] Fountain - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路: 标签:倍增，ST表,应该再加个二分标签。

ST表用作二分找第i个盘的下一个盘,然后建图建图之后倍增。

倍增的过程跟lca的初始化过程同理。

int n,q;
pair<int,int> arr[100005];
int mx[100005][25];
int nex[100005];
void init1(){for(int i=1;i<=n;i++) mx[i][0]=arr[i].first;for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);}}
}
int query(int l,int r){int k=log2(r-l+1);return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
pair<int,int> f[100005][25];   f[i][j]定义为,从第i个点往下跳2^j步,为<累计水容量,到达的层数编号>
void init2(){           往下跳--倍增for(int i=1;i<=n;i++) f[i][0]={arr[i].second+arr[nex[i]].second,nex[i]};for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){int halfIdx=f[i][j-1].second;f[i][j].first=f[i][j-1].first+f[halfIdx][j-1].first-arr[halfIdx].second;f[i][j].second=f[halfIdx][j-1].second;}}
}
标签:倍增，ST表,,应该再加个二分标签
ST表用作二分找第i个盘的下一个盘,然后建图
建图之后倍增，跟lca的初始化过程同理
基本上是一发入魂(最后输出答案的地方判错了一点,导致全wa)！！无敌了，第一次写倍增。
P7167 [eJOI2020 Day1] Fountain
https://www.luogu.com.cn/problem/P7167
void solve(){                   好题,好题.倍增入门题.cin>>n>>q;for(int i=1;i<=n;i++) cin>>arr[i].first>>arr[i].second;   <直径,容量>init1();for(int i=1;i<=n;i++){    o(nlogn)  n次二分,每次check是o(1)的int l=i+1,r=n,res=0;while(l<=r){int mid=(l+r)>>1;if(query(i+1,mid)>arr[i].first){res=mid;r=mid-1;}else l=mid+1;}nex[i]=res;   建图}init2();while(q--){int x,v; cin>>x>>v;if(v<=arr[x].second) cout<<x<<endl;else{int cur=x;j从大到小for(int j=20;j>=0;j--){if(f[cur][j].second!=0&&f[cur][j].first<=v){v-=f[cur][j].first;cur=f[cur][j].second;v+=arr[cur].second;}}if(v<=arr[cur].second) cout<<cur<<endl; v<=arr[cur].second 而不是v==0else cout<<nex[cur]<<endl;}}
}

to be continue...