Ratio 的线段树

2个月前更新

有不知名 HDK 在看马蜂识人的文章里肆意诋毁我们维什戴尔玩家，写线段树居然用结构体，太可耻了，为此献上一份真实的 Ratio 的线段树马蜂。

这是一棵维护单点修改，区间最大值、最小值以及区间和的标准线段树。

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)((y));(x)<=(z);(x)++)
using namespace std;
const int Ratio=0;
const int N=5e5+5;
int n,m;
int a[N],maxn[N<<2],minn[N<<2],sum[N<<2];
namespace Wisadel
{
    #define ls (rt<<1)
    #define rs (rt<<1|1)
    #define mid ((l+r)>>1)
    void Wpushup(int rt)
    {
        maxn[rt]=max(maxn[ls],maxn[rs]);
        minn[rt]=min(minn[ls],minn[rs]);
        sum[rt]=sum[ls]+sum[rs];
    }
    void Wbuild(int rt,int l,int r)
    {
        if(l==r)
        {
            maxn[rt]=minn[rt]=sum[rt]=a[l];
            return;
        }
        Wbuild(ls,l,mid),Wbuild(rs,mid+1,r);
        Wpushup(rt);
    }
    void Wupd(int rt,int l,int r,int x,int v)
    {
        if(l==r){maxn[rt]=minn[rt]=sum[rt]=v;return;}
        if(x<=mid) Wupd(ls,l,mid,x,v);
        else Wupd(rs,mid+1,r,x,v);
        Wpushup(rt);
    }
    int Wqmax(int rt,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y) return maxn[rt];
        int res=-1e9;
        if(x<=mid) res=max(res,Wqmax(ls,l,mid,x,y));
        if(y>mid) res=max(res,Wqmax(rs,mid+1,r,x,y));
        return res;
    }
    /*code*/
    short main()
    {
        scanf("%d%d",&n,&m);
        fo(i,1,n) scanf("%d",&a[i]);
        Wbuild(1,1,n);
        fo(i,1,m)
        {
            int op,aa,bb;scanf("%d%d%d",&op,&aa,&bb);
            /*code*/
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}