#bzoj3187#区间修改的RMQ问题(zkw线段树版)

区间修改的RMQ问题

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给出N(1 ≤ N ≤ 50,000)个数的序列A，下标从1到N，每个元素值均不超过1000。有两种操作： (1)  Q i j：询问区间[i, j]之间的最大值与最小值的差值 (2) C i j k：将区间[i, j]中的每一个元素增加k，k是一个整数，k的绝对值不超过1000。 一共有M (1 ≤ M ≤ 200,000) 次操作，对每个Q操作，输出一行，回答提问。

输入

第1行：2个整数N, M 第2行：N个元素 接下来M行，每行一个操作

输出

对每个Q操作，在一行上输出答案

样例输入

5 4 1 2 3 4 5 Q 2 4 C 1 1 1 C 1 3 2 Q 1 5

样例输出

2 1

才略懂了一点zkw线段树，本来觉得自己并没有灵活掌握全部，但是理解是靠熟练一点点堆起来的，

所以才慢慢写一篇题解，想看看自己是不是真的懂了一点点，

以下全部都是我自己对于zkw线段树的理解，仅作参考，如果有问题，还望指教。

使用差分思想，令Tr[i]中维护它与其父亲节点的差值（待会儿会写另一篇来详细介绍我对其的理解）

为什么是差值呢？

因为这样能够方便修改，当一个节点的整个子树都被包含在内的时候，只需要修改此节点及以上，就可以达到修改整个子树的目的，以节约时间。

即维持下方节点差值不变，将上方差值增大，这样可以保证结果不变。

因为，对于每个子节点的真实值，都需要从子节点一路累加到根节点。

写在前面：

我的zkw树下标和网上的不太一样，我并没有用开区间，全部代码都为闭区间。

以下代码仅以求最小值为例。

请仔细阅读build()：

void build(){ for(X=1; X<=N; X<<=1); --X; for(int i=X+1; i<=X+N; ++i)scanf("%d",&Tr[i]); for(int i=X; i>=1; --i) Tr[i]=min(Tr[i<<1],Tr[i<<1|1]),Tr[i<<1]-=Tr[i],Tr[i<<1|1]-=Tr[i]; }

单个子节点求真实值代码如下：

int get_value(int pos){ int val=0; for(pos+=X; pos; pos>>=1) val+=Tr[pos]; return val; }对于单个子节点的修改如下：

void add(int pos,int val){ int A; Tr[pos]+=val; for(; pos>1; pos>>=1) A=min(Tr[pos],Tr[pos^1]),Tr[pos]-=A,Tr[pos^1]-=A,Tr[pos>>1]+=A; }对于区间的修改如下：

void add(int s,int t,int val){ s+=X,t+=X; int A; if(s==t){//注意单点是需要特判的，不然会死循环 Tr[s]+=val; for(; s>1; s>>=1) A=min(Tr[s],Tr[s^1]),Tr[s]-=A,Tr[s^1]-=A,Tr[s>>1]+=A; return ; } Tr[s]+=val;Tr[t]+=val; for(; s^t^1; s>>=1,t>>=1){ if(~s&1)Tr[s^1]+=val;//判断是不是左子，若是就将右子纳入比较 if(t&1)Tr[t^1]+=val;//判断是不是右子，若是就将左子纳入比较 A=min(Tr[s],Tr[s^1]),Tr[s]-=A,Tr[s^1]-=A,Tr[s>>1]+=A;//修改该点与其父亲节点的关系，稍后会在另一篇文章中详细讲述解释（是我自己的理解，仅做参考） A=min(Tr[t],Tr[t^1]),Tr[t]-=A,Tr[t^1]-=A,Tr[t>>1]+=A; } while(s!=1){//因为是把s为子节点去更新s>>1，所以s只能到2就停下，此时(s>>1)=1 A=min(Tr[s],Tr[s^1]),Tr[s]-=A,Tr[s^1]-=A,Tr[s>>1]+=A; s>>=1; } }

本题开两个数组，一个维护最小值，一个维护最大值。

完整代码如下：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int Max=50000; int N,M,X; int Trx[Max*4+5],Trn[Max*4+5]; void build(){ for(X=1; X<=N; X<<=1); for(int i=1; i<=(X<<1); ++i)Trn[i]=0x3f3f3f,Trx[i]=-0x3f3f3f; --X; for(int i=X+1; i<=X+N; ++i)scanf("%d",&Trx[i]),Trn[i]=Trx[i]; for(int i=X; i>=1; --i){ Trx[i]=max(Trx[i<<1],Trx[i<<1|1]),Trx[i<<1]-=Trx[i],Trx[i<<1|1]-=Trx[i]; Trn[i]=min(Trn[i<<1],Trn[i<<1|1]),Trn[i<<1]-=Trn[i],Trn[i<<1|1]-=Trn[i]; } } void add(int s,int t,int val){ s+=X,t+=X; int A; if(s==t){ Trx[s]+=val,Trn[s]+=val; for(; s>1; s>>=1){ A=min(Trn[s],Trn[s^1]),Trn[s]-=A,Trn[s^1]-=A,Trn[s>>1]+=A; A=max(Trx[s],Trx[s^1]),Trx[s]-=A,Trx[s^1]-=A,Trx[s>>1]+=A; } return ; } Trx[s]+=val,Trn[s]+=val,Trx[t]+=val,Trn[t]+=val; for(; s^t^1; s>>=1,t>>=1){ if(~s&1)Trx[s^1]+=val,Trn[s^1]+=val; if(t&1)Trx[t^1]+=val,Trn[t^1]+=val; A=min(Trn[s],Trn[s^1]),Trn[s]-=A,Trn[s^1]-=A,Trn[s>>1]+=A; A=min(Trn[t],Trn[t^1]),Trn[t]-=A,Trn[t^1]-=A,Trn[t>>1]+=A; A=max(Trx[s],Trx[s^1]),Trx[s]-=A,Trx[s^1]-=A,Trx[s>>1]+=A; A=max(Trx[t],Trx[t^1]),Trx[t]-=A,Trx[t^1]-=A,Trx[t>>1]+=A; } while(s!=1){ A=min(Trn[s],Trn[s^1]),Trn[s]-=A,Trn[s^1]-=A,Trn[s>>1]+=A; A=max(Trx[s],Trx[s^1]),Trx[s]-=A,Trx[s^1]-=A,Trx[s>>1]+=A; s>>=1; } } int Query(int s,int t){ s+=X,t+=X; if(s==t){ int ansx=Trx[s],ansn=Trn[s]; while(s){ s>>=1; ansx+=Trx[s],ansn+=Trn[s]; } return ansx-ansn; } int ansxl,ansxr,ansnl,ansnr; ansxl=ansxr=ansnl=ansnr=0; for(; s^t^1; s>>=1,t>>=1){ ansxl+=Trx[s],ansxr+=Trx[t]; ansnl+=Trn[s],ansnr+=Trn[t]; if(~s&1){ ansnl=min(ansnl,Trn[s^1]); ansxl=max(ansxl,Trx[s^1]); } if(t&1){ ansnr=min(ansnr,Trn[t^1]); ansxr=max(ansxr,Trx[t^1]); } } ansxl+=Trx[s],ansxr+=Trx[t],ansnl+=Trn[s],ansnr+=Trn[t]; int ansx=max(ansxl,ansxr),ansn=min(ansnl,ansnr); while(s){ s>>=1; ansx+=Trx[s],ansn+=Trn[s]; } return ansx-ansn; } int main(){ scanf("%d%d",&N,&M); build(); char ord[3]; int l,r,val; while(M--){ scanf("%s%d%d",ord,&l,&r); if(ord[0]=='Q') printf("%d\n",Query(l,r)); else { scanf("%d",&val); add(l,r,val); } } return 0; }