2017-08-30 19:53:27

writer：pprp

#include 
     
      using namespace std;#define MAXN 10000struct Tree{    int val;//此区间存的值    int addnum;//整个区间被增加的值    bool lazy;//区间是否被整体修改过    int lazy_chg;//区间被整体修改后的值(lazy==true时有效)} tree[MAXN*4];int arr[MAXN];//用于初始化的数组int lson(int rt){    return rt<<1;}int rson(int rt){    return (rt<<1)|1;}//更新此区间存的值//@param: rt:根的编号void tree_update(int rt){    tree[rt].val=max(tree[lson(rt)].val,tree[rson(rt)].val)+tree[rt].addnum;    //可更改(max/min/sum)}//将编号rt的区间全变为val//@param: void tree_chg(int left,int right,int rt,int val){    tree[rt].val=val;/**可更改(求和则为v*(right-left+1))**/    tree[rt].lazy=true;    tree[rt].lazy_chg=val;    tree[rt].addnum=0;}//将整体修改的信息向下传递void pushDown(int left,int right,int rt){    if(tree[rt].lazy)    {        tree[rt].lazy=false;        int mid=(left+right)>>1;        tree_chg(left,mid,lson(rt),tree[rt].lazy_chg);        tree_chg(mid+1,right,rson(rt),tree[rt].lazy_chg);    }}void tree_init(){    memset(tree,0,sizeof(tree));//清0}//建立一个线段树void tree_build(int left,int right,int rt)//初始化维护某个数组{    tree[rt].lazy=false;    tree[rt].addnum=0;    if(left==right)    {        tree[rt].val=arr[left];/**需对应为原数组的名称**/    }    else    {        int mid=(left+right)>>1;        tree_build(left,mid,lson(rt));        tree_build(mid+1,right,rson(rt));        tree_update(rt);    }}//区间增加//把l到r间的值都增加vvoid tree_add(int left,int right,int rt,int l,int r,int val){    if(l<=left&&right<=r)    {        tree[rt].val+=val;        tree[rt].addnum+=val;    }    else    {        pushDown(left,right,rt);        int mid=(left+right)>>1;        if(l<=mid)tree_add(left,mid,lson(rt),l,r,val);        if(r>mid)tree_add(mid+1,right,rson(rt),l,r,val);        tree_update(rt);    }}//区间修改//把l到r间的值都修改为vvoid tree_change(int left,int right,int rt,int l,int r,int v){    if(l<=left&&right<=r)tree_chg(left,right,rt,v);    else    {        pushDown(left,right,rt);        int mid=(left+right)>>1;        if(l<=mid)tree_change(left,mid,lson(rt),l,r,v);        if(r>mid)tree_change(mid+1,right,rson(rt),l,r,v);        tree_update(rt);    }}//区间查询//查询区间[l,r]维护的值int tree_find(int left,int right,int rt,int l,int r,int val){    if(l<=left&&right<=r)return tree[rt].val;    else    {        pushDown(left,right,rt);        int mid=(left+right)>>1;        if(l<=mid&&r>mid)            return max(tree_find(left,mid,lson(rt),l,r,val)                       ,tree_find(mid+1,right,rson(rt),l,r,val));        /**可更改(max/min/sum)**/        if(l<=mid)return tree_find(left,mid,lson(rt),l,r,val);        return tree_find(mid+1,right,rson(rt),l,r,val);    }}int main(){    return 0;}