线段树

#include<iostream>
#include<cstdio>
using namespace std;
const int INF=1e9,MAXN=1000;
struct node{int a,b,lc,rc;} tree[MAXN+1];
struct lazy{int ch,det} tag[MAXN+1];
int na[MAXN+1],sum[MAXN+1],mx[MAXN+1];
int n,cnt,root;
void update(now)
{
    int lc=tree[now].lc,rc=tree[now].rc;
    mx=max(mx[lc],mx[rc]);
    sum=su[lc]+su[rc]; 
}
void buildTree(int l,int r)//递归建树 
{
    cnt++;
    int now=cnt;//由于cnt在递归过程中会发生改变，所以需要now记录当前的cnt 
    tree[now].a=l,tree[now].b=r;
    if(l==r)
    {
        mx[now]=na[l],sum[now]=na[l];
        return now;
    }
    int mid=(l+r)>>1;
    tree[now].lc=build(l,mid);
    tree[now].rc=build(mid+1,r);
    update(now);
    return now;
}
void pushDown(int o)
{
    int lc=tree[o].lc,rc=tree[o].rc;
    if(tag[o].ch)
    {
        mx[o]=tag[o].ch;
        sum[o]=(tree[o].b-tree[o].a+1)*tag[o].ch;
        if(lc) tag[lc].ch=tag[o].ch;
        if(rc) tag[rc].ch=tag[o].ch;
        tag[o].ch=0;
    }
    if(tag[o].det)
    {
        mx[o]+=tag[o].det;
        su[o]+=(tree[o].b-tree[o].a+1]*tag[o].det;
        if(lc) tag[lc].det+=tag[o].det;
        if(rc) tag[rc].det+=tag[o].det;
        tag[o].det=0;
    }
}
int ql,qr;//询问的范围
int calMax(int o,int l,int r)
{
    pushDown(o);
    if(ql<=l&&r<=qr) return mx[o];
    int mid=(l+r)>>1,lmx=-INF,rmx=-INF;
    if(ql<=mid) lmx=calMax(tree[o].lc,l,mid);
    if(qr>mid) rmx=calMax(tree[o].rc,mid+1,r);
    return max(lmx,rmx);
}
int calSum(int o,int l,int r)
{
    pushDown(o);
    if(ql<=l&&r<=qr) return sum[o];
    int mid=(l+r)>>1,sum=0;
    if(ql<=mid) sum+=calSum(tree[o].lc,l,mid);
    if(qr>mid) sum+=calSum(tree[o].rc,mid+1,r);
    return sum;
}
int cl,cr;//更改的范围
void chCh(int o,int l,int r,int x)
{
    pushDown(o);
    if(cl<=l&&r<=cr)
    {
        mx[o]=x;
        sum[o]=(r-l+1)*x;
        tag[tree[o].lc].ch=x,tag[tree[o]].ch=x;
        return;
    }
    int mid=(l+r)>>1;
    if(cl<=mid) chCh(tree[o].lc,l,mid);
    if(cr>mid) chCh(tree[o].rc,mid+1,r);
    update(o);
}
void chDet(int o,int l,int r,int x)
{
    pushdown(o);
    if(cl<=l&&r<=cr)
    {
        mx[o]+=x;
        sum[o]+=(r-l+1)*x;
        tag[tree[o].lc].det+=x,tag[tree[o]].det+=x;
        return;
    }
    int mid=(l+r)>>1;
    if(cl<=mid) chDet(tree[o].lc,l,mid);
    if(cr>mid) chDet(tree[o].rc,mid+1,r);
    update(o);
}