Line 1: Two space-separated integers, N and Q. Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.示例1
6 3 1 7 3 4 2 5 1 5 4 6 2 2
6 3 0
易错点:这种两个小于号的写法,是所求区间不变,查询区间挨个变小,比较的时候也要用查询区间和所求区间比较,不然很容易出bug。。
//-------------------------代码---------------------------- //#define int ll const int N = 1e5+10; int n,m; int a[N]; int tr1[4*N]; int tr2[4*N]; void init(int p,int l,int r) { if(l == r) { tr1[p] = a[l]; tr2[p] = a[l]; rt; } int mid = l + r >>1; init(2 * p,l,mid); init(2 * p + 1,mid + 1,r); tr1[p] = max(tr1[p * 2],tr1[p * 2 + 1]); tr2[p] = min(tr2[p * 2],tr2[p * 2 + 1]); } int calc(int p,int x,int y,int l,int r,bool q) { if(x <= l && r <= y ) { if(q == 1)return tr1[p]; else return tr2[p]; } int mid = l + r >> 1; int mx = 0; int mn = 1e9; if(x <= mid) { if(q)mx = max(mx , calc(p << 1, x, y, l, mid,1)); if(!q)mn = min(mn , calc(p << 1, x, y, l, mid,0)); } if(y > mid ) { if(q)mx = max(mx , calc(p << 1 | 1, x, y, mid + 1, r,1)); if(!q)mn = min(mn , calc(p << 1 | 1, x, y, mid + 1, r,0)); } if(q == 1) return mx; else return mn; } void solve() { // cin>>n>>m; cin>>n>>m; fo(i,1,n) { cin>>a[i]; } init(1,1,n); fo(i,1,m) { int l,r; cin>>l>>r; cout<<calc(1,l,r,1,n,1) - calc(1,l,r,1,n,0)<<endl; } } void main_init() {} signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); // while(cin>>n,n) // while(cin>>n>>m,n,m) // int t;cin>>t;while(t -- ) solve(); // {solve(); } return 0; } /*样例区 */ //------------------------------------------------------------