2025年12月6日：离散化-st表
2025-12-06 19:50:27
发布于：广东
39阅读
0回复
0点赞
//离散化:将大数据按照顺序重新标号
// 1134198 193275918 12938791875 13294719238741
// 1 2 3 4
// 映射
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
void solve(){
map<int,int>mp;//红黑树---》平衡树
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
mp[x]++;//先记录有那些出现过的数字
}
// auto //自动类型
int inx=1;
int &x=inx;
x=2;
for(auto &cur:mp){//
cur.second=inx++;//不会改底层结构
}
auto cur=mp.upper_bound(1);//返回一个迭代器
cout<<(*cur).first<<' '<<(*cur).second<<endl;
cur++;
cout<<(*cur).first<<' '<<(*cur).second<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
//倍增
//dp动态规划
//记忆化搜素，递推，递归
//状态转移方程
//f(i)=f(i-1)+f(i-2);//状态转移方程
//通过已知推导未知
//f(1)=1;f(2)=1;f(3)=f(2)+f(1);
// int ans[N];//记忆化数组，将需要重复求解的答案存储起来
// int f(int inx){
// if(inx<=2)return 1;
// if(ans[inx])return ans[inx];
// return f(inx-1)+f(inx-2);
// }
//
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
// int ans[N][N];//记忆化数组-》ans[l][r]表示区间[l,r]的最大值.
// int a[N];//存储数组
//ans[i][i]=a[i]===>>l=r的情况
//ans[i][i+1]=max(a[i],a[i+1]);
//ans[i][i+2]=max(ans[i][i+1],a[i+2]);
//ans[l][r]=max(ans[l][r-1],a[r]);//状态转移方程 l<r
//莫队算法nlog =>>nsqrt(n);
// int ans[N][40];//记忆数组---》ans[i][inx]，从起点i开始2^inx个数字的最大值
//ans[i][0]=a[i];
//ans[i][1]=a[i],a[i+1]总共两个数字
//ans[i][2]=max(ans[i][1],ans[i+2][1]) 总共四个
//ans[i][3]=max(ans[i][2],ans[i+4][2]);
//ans[i][inx]=max(ans[i][inx-1],ans[i+2^(inx-1)][inx-1]);;//状态转移方程
int mx_ans[N][100],mi_ans[N][100];
int a[N];
void solve(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
mx_ans[i][0]=mi_ans[i][0]=a[i];//初始化从起点i开始1个数字的最大值
}
for(int inx=1;inx<30;inx++)
for(int i=1;i<=n;i++){
if(i+(1<<inx)>n+1)continue;
mx_ans[i][inx]=max(mx_ans[i][inx-1],mx_ans[i+(1<<(inx-1))][inx-1]);
mi_ans[i][inx]=min(mi_ans[i][inx-1],mi_ans[i+(1<<(inx-1))][inx-1]);
}
while(q--){
int l,r;
cin>>l>>r;
int x=l;//记录跳的位置
//从i开始计算100 64 32 4
int len=r-l+1;//跳的距离
int inx=0;//记录跳多少 2^inx个
int mx_a=a[l];
int mi_a=a[l];
while(len){
if(len&(1<<inx)){//判断是否要跳2^inx 同1为1否则为0
mx_a=max(mx_a,mx_ans[x][inx]);
mi_a=min(mi_a,mi_ans[x][inx]);
x+=(1<<inx);//x跳到下一块区域
len-=(1<<inx);
}
inx++;
}
// cout<<mx_a<<' '<<mi_a<<endl;
cout<<mx_a-mi_a<<endl;
}
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
有帮助，赞一个