题目链接：
id=3264">http://poj.org/problem?
id=3264
这是一个单点更新的模板题，就不详解了，HDU敌兵布阵那题我有详解；链接：http://blog.csdn.net/wlxsq/article/details/46897219
#include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; /* 这是一个线段树单点更新的模板题。只是每一个节点存两个数据。最大值和最小值； */ const int inf=0xffffff0; int MinV,MaxV; int q,n,a,b; struct node { int l,r,MinV,MaxV; }node[200010]; void PushUp(int rt,int v) // 更新父节点； { node[rt].MinV=min(node[rt].MinV,v); node[rt].MaxV=max(node[rt].MaxV,v); } void build(int l,int r,int rt) { int mid=(l+r)>>1; node[rt].l=l; node[rt].r=r; node[rt].MinV=inf; node[rt].MaxV=-inf; if(l==r) return; else{ build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); } } void Insert(int rt,int p,int v) { int l=node[rt].l; int r=node[rt].r; if(l==r&&p==l){ node[rt].MinV=v; node[rt].MaxV=v; return; } //node[rt].MinV=min(v,node[rt].MinV); //node[rt].MaxV=max(v,node[rt].MaxV); int mid=(l+r)>>1; if(p<=mid) Insert(rt<<1,p,v); else Insert(rt<<1|1,p,v); PushUp(rt,v); } void query(int l,int r,int rt) { if(node[rt].MaxV<=MaxV&&node[rt].MinV>=MinV) return; // 往下搜没有什么意义了，能够直接退出； if(l==node[rt].l&&r==node[rt].r){ MinV=min(node[rt].MinV,MinV); MaxV=max(node[rt].MaxV,MaxV); return; } int mid=(node[rt].l+node[rt].r)>>1; if(r<=mid) query(l,r,rt<<1); else if(l>mid) query(l,r,rt<<1|1); else{ query(l,mid,rt<<1); query(mid+1,r,rt<<1|1); } } int main() { while(~scanf("%d%d",&n,&q)){ build(1,n,1); for(int i=1;i<=n;i++){ scanf("%d",&a); Insert(1,i,a); } for(int i=1;i<=q;i++){ scanf("%d%d",&a,&b); MinV=inf; MaxV=-inf; query(a,b,1); printf("%d\n",MaxV-MinV); } } return 0; }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章
