【数据结构】线段数/segmenttree/intervaltree

/*
hdu1754 
找区间最大值 
*/

#include
#include 
#include
using namespace std;

const int INF = -100;
const int maxn = 2000100;
int segtree[maxn];

inline void pushup(int root){
    segtree[root] = max( segtree[root*2], segtree[root*2+1] );
}
void built(int root, int L, int R){
    if(L==R){
        scanf("%d", &segtree[root]);
        return;
    }
    int m = (R+L)/2;
    built(root*2, L, m);
    built(root*2+1, m+1, R);
    pushup(root);
}

//cL current L   cR current right  
int query(int root, int cL, int cR, int qL, int qR){
    if(qL<=cL && cR<=qR) return segtree[root];    //查询区间完全包含当前区间 
    int ans = INF;
    int m = (cR+cL)/2;
    if(qL<=m) ans = max( ans, query(root*2, cL, m, qL, qR) );    //如果查询的区间有部分在当前节点的左子树 
    if(m2+1, m+1, cR, qL, qR) );//如果查询的区间有部分在当前节点的右子树
    return ans; 
}

//修改第p个元素为v 
void update(int root, int cL, int cR, int p, int v){
    if(cL == cR){
        segtree[root] = v;    
        return;
    }
    int m = (cR+cL)/2;
    if(p<=m) update(root*2, cL, m, p, v);
    else update(root*2+1, m+1, cR, p, v);
    pushup(root);
}

int main(){
    int n, m;
    char oder;
    int qL, qR;
    int p, v;
    while(scanf("%d%d", &n, &m)==2){
        built(1, 1, n);
        
        //////    
//            for(int i=1;i<=9;++i) cout <//            cout <
        //////
        
        while(m--){
            getchar(); 
            scanf("%c", &oder);
            if(oder=='Q'){
                scanf("%d%d", &qL, &qR);
                
                //////    
//                    cout <<"qL=" <%d\n", query(1, 1, n, qL, qR));
            }     
            else{
                scanf("%d%d", &p, &v);
                update(1, 1, n, p, v);    
            }
        }
    }
    return 0;
} 

//hdu 1698 成段更新
//基础的线段树模板题
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=100005;
int t,n,q;
ll sum[maxn*4],add[maxn*4];
void pushup(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int len){
    if(add[rt]){
        add[rt<<1]=add[rt];
        add[rt<<1|1]=add[rt];
        sum[rt<<1]=add[rt]*(len-(len>>1));
        sum[rt<<1|1]=add[rt]*(len>>1);
        add[rt]=0;
    }
}
void build(int l,int r,int rt){
    add[rt]=0;
    if(l==r){
        //scanf("%I64d",&sum[rt]);
        sum[rt]=1;
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&R>=r){
        add[rt]=c;
        sum[rt]=(ll)c*(r-l+1);
        return;
    }
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,l,m,rt<<1);
    if(R>m) update(L,R,c,m+1,r,rt<<1|1);
    pushup(rt);
}
ll querry(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r) return sum[rt];
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    ll ans=0;
    if(L<=m) ans+=querry(L,R,l,m,rt<<1);
    if(R>m) ans+=querry(L,R,m+1,r,rt<<1|1);
    return ans;
}
int main()
{
    int x,y,z;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        scanf("%d%d",&n,&q);
        build(1,n,1);
        while(q--){
            scanf("%d%d%d",&x,&y,&z);
            update(x,y,z,1,n,1);
        }
        printf("Case %d: The total value of the hook is %I64d.\n",cas,querry(1,n,1,n,1));
    }
}