编织幻梦

复习中。。。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxh = 17; 
const int maxm = 1<<(maxh-1);
struct zkw_segment{
	int zkw_max[(maxm<<1)+1]; // max
	int zkw_min[(maxm<<1)+1]; // min
	int query_max(int l,int r);
	int query_min(int l,int r);
	void change(int x,int delta);
}T;
int zkw_segment::query_max(int left,int right){
	int ans=-1;
	for (int l=maxm+left-1,r=maxm+right+1;l^r^1;l>>=1,r>>=1){
		if (~l&1) ans=max(ans,zkw_max[l^1]);
		if (r&1) ans=max(ans,zkw_max[r^1]);
	};
	return ans;
};
int zkw_segment::query_min(int left,int right){
	int ans=0x3fffffff;
	for (int l=maxm+left-1,r=maxm+right+1;l^r^1;l>>=1,r>>=1){
		if (~l&1) ans=min(ans,zkw_min[l^1]);
		if (r&1) ans=min(ans,zkw_min[r^1]);
	};
	return ans;
};
void zkw_segment::change(int x,int value){
	int p=maxm+x;
	zkw_max[p]=value;zkw_min[p]=value;p>>=1;
	for (;p!=0;p>>=1){
		zkw_max[p]=max(zkw_max[p<<1],zkw_max[(p<<1)+1]);
		zkw_min[p]=min(zkw_min[p<<1],zkw_min[(p<<1)+1]);
	}
};
int main(){
	int n,q;scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++) {
		int x;scanf("%d",&x);T.change(i,x);
	}
	for (int i=1;i<=q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		int rst = T.query_max(l,r)-T.query_min(l,r);
		printf("%d\n",rst);
	}
};