PKU 3264 Balanced Lineup
segtreeがやたら書きたくなったのでPKU漁ったら出てきた問題。
解法
区間の最大値と最小値の差を出力する問題。普通に2つのsegtreeで区間の最大値、最小値を求めて引き算しました。
ソースコード
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <complex> #include <string> #include <sstream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <functional> #include <iostream> #include <map> #include <set> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define pu push #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define sz(x) ((int)(x).size()) #define fi first #define sec second #define SORT(x) sort((x).begin(),(x).end()) #define all(x) (x).begin(),(x).end() #define EQ(a,b) (abs((a)-(b))<EPS) int seg1[(1<<18)-1],seg2[(1<<18)-1]; int n,q; void init() { scanf("%d %d",&n,&q); fill(seg1,seg1+(1<<18-1),INF); memset(seg2,-1,sizeof(seg2)); return ; } void update(int k,int x) { k+=(1<<17)-1; seg1[k]=x; seg2[k]=x; while(k) { k=(k-1)/2; seg1[k]=min(seg1[k*2+1],seg1[k*2+2]); seg2[k]=max(seg2[k*2+1],seg2[k*2+2]); } return; } int min_query(int a,int b,int k,int l,int r) { if(b<=l||r<=a)return INF; if(a<=l&&r<=b)return seg1[k]; return min(min_query(a,b,k*2+1,l,(l+r)/2),min_query(a,b,k*2+2,(l+r)/2,r)); } int max_query(int a,int b,int k,int l,int r) { if(b<=l||r<=a)return -1; if(a<=l&&r<=b)return seg2[k]; return max(max_query(a,b,k*2+1,l,(l+r)/2),max_query(a,b,k*2+2,(l+r)/2,r)); } int main() { init(); for(int i=0;i<n;i++) { int x; scanf("%d",&x); update(i,x); } for(int i=0;i<q;i++) { int a,b; scanf("%d %d",&a,&b); printf("%d\n",max_query(a-1,b,0,0,1<<17)-min_query(a-1,b,0,0,1<<17)); } return 0; }