编织幻梦

复习中……还是zkw代码量少啊。。

#include <cstdio>
#include <algorithm>
using namespace std;
struct normal_tree{
	struct node{
		int l,r;
		int cmax,cmin;
		node *ch[2];
		inline bool range(int x){
			return (x>=l&&x<=r);
		}
		inline pair<int,int> range(int x,int y){
			pair<int,int> rst;
			rst.first = max(x,l);
			rst.second = min(y,r);
			return rst;
		}
	}*top,pool[(1<<18)+2];int ps;
	int query_max(int l,int r);
	int query_min(int l,int r);
	int query_max_dfs(int l,int r,node * f);
	int query_min_dfs(int l,int r,node * f);
	void change(int x,int value);
	void change_dfs(int x,int value,node * f);
	void build(int n); // [0,n]
	void build(int l,int r,node* f);
	node* node_alloc(int l,int r){pool[ps].l=l,pool[ps].r=r;return &pool[ps++];};
	normal_tree(){ps=0;top=0;memset(pool,0,sizeof(pool));}
}T;
void normal_tree::build(int n){
	top=node_alloc(0,n);
	build(0,n,top);
}
void normal_tree::build(int l,int r,node* f){
	if (l==r) return;
	f->ch[0]=node_alloc(l,(l+r)/2);
	f->ch[1]=node_alloc((l+r)/2+1,r);
	build(l,(l+r)/2,f->ch[0]);
	build((l+r)/2+1,r,f->ch[1]);
};
void normal_tree::change(int x,int value){
	change_dfs(x,value,top);
};
void normal_tree::change_dfs(int x,int value,node*f){
	if (f->l==x&&f->r==x){
		f->cmax=f->cmin=value;return ;
	};
	if (f->ch[0]->range(x)){
		change_dfs(x,value,f->ch[0]);
		f->cmax = max(f->ch[1]->cmax,f->ch[0]->cmax);
		f->cmin = min(f->ch[1]->cmin,f->ch[0]->cmin);
	}else
	{
		change_dfs(x,value,f->ch[1]);
		f->cmax = max(f->ch[1]->cmax,f->ch[0]->cmax);
		f->cmin = min(f->ch[1]->cmin,f->ch[0]->cmin);
	}
};
int normal_tree::query_max(int l,int r){
	return query_max_dfs(l,r,top);
}
int normal_tree::query_min(int l,int r){
	return query_min_dfs(l,r,top);
};
int normal_tree::query_max_dfs(int l,int r,node * f){
	if (f->l==l&&f->r==r) return f->cmax;
	pair<int,int> t;
	int rst = 0;
	if (f->ch[0]->range(l)){
		t = f->ch[0]->range(l,r);
		rst = max(rst,query_max_dfs(t.first,t.second,f->ch[0]));
	}
	if (f->ch[1]->range(r)){
		t = f->ch[1]->range(l,r);
		rst = max(rst,query_max_dfs(t.first,t.second,f->ch[1]));
	}
	return rst;
}
int normal_tree::query_min_dfs(int l,int r,node * f){
	if (f->l==l&&f->r==r) return f->cmin;
	pair<int,int> t;
	int rst = 0x3fffffff;
	if (f->ch[0]->range(l)){
		t = f->ch[0]->range(l,r);
		rst = min(rst,query_min_dfs(t.first,t.second,f->ch[0]));
	}
	if (f->ch[1]->range(r)){
		t = f->ch[1]->range(l,r);
		rst = min(rst,query_min_dfs(t.first,t.second,f->ch[1]));
	}
	return rst;
};
int main(){
	int n,q;scanf("%d%d",&n,&q);
	T.build(n);//[0,n]
	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);
	}
};