首页 > 代码库 > UESTC 电子科大专题训练 数据结构 A
UESTC 电子科大专题训练 数据结构 A
UESTC 1591
题意:求区间极值之差
思路:线段树裸题,不带更新
ACA代码:
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=5e4+100; const ll mod=1e9+7; int mi[N<<2],ma[N<<2],maa,mii; void push_up(int root){ mi[root]=min(mi[root*2],mi[root*2+1]); ma[root]=max(ma[root*2],ma[root*2+1]); } void creat(int root, int l, int r){ if(l==r){ scanf("%d",&ma[root]); mi[root]=ma[root]; //cout<<l<<"UUUUUUUUUU"<<endl; return; } int mid=l+r>>1; creat(root*2, l, mid); creat(root*2+1, mid+1, r); push_up(root); } void query(int root,int l, int r, int L, int R){ if(l==L && r==R){ maa=max(maa,ma[root]), mii=min(mii,mi[root]); return; } int mid=l+r>>1; if(R<=mid) query(root*2, l, mid, L, R); else if(L>mid) query(root*2+1, mid+1, r, L, R); else{ query(root*2, l, mid, L, mid); query(root*2+1, mid+1, r, mid+1, R); } } int main(){ //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,q,l,r; cin>>n>>q; creat(1,1,n); while(q--){ scanf("%d%d",&l,&r); maa=-inf,mii=inf; query(1,1,n,l,r); printf("%d\n",maa-mii); } return 0; }
UESTC 电子科大专题训练 数据结构 A
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。