9.23 D 暂存

鉴于 5k 和 int_R 等大神都认为这道题 80pts 档是一个普通的线段树，作为一个线段树狂热爱好者果断尝试，但在打出 30 行的 pushup 后蚌埠住了，但还是想切掉，所以暂存一下，什么时候打出来什么时候删置顶。

目前进度：pushup，建树

你们要是能发现问题记得说啊，

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch=getchar();lx x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int,int>
#define fi first
#define se second
const int Ratio=0;
const int N=1e5+5;
const int mod=998244353;
int n,m;
int a[N];
// segment tree
int llen[N<<2]/*左连续正长度*/,rlen[N<<2],zgs[N<<2]/*正连续段个数*/;
unsigned lji[N<<2],rji[N<<2],lv1[N<<2],rv1[N<<2],v1[N<<2],v2[N<<2],v3[N<<2],v4[N<<2];
bool man[N<<2];// 整段为正
namespace Wisadel
{
    #define ls (rt<<1)
    #define rs (rt<<1|1)
    #define mid ((l+r)>>1)
    void Wpushup(int rt)
    {
        if(man[ls]&&man[rs]) llen[rt]=rlen[rt]=llen[ls]+rlen[rs],
                             lji[rt]=rji[rt]=lji[ls]*rji[rs],man[rt]=1;
        else if(!man[ls]&&man[rs]) llen[rt]=llen[ls],lji[rt]=lji[ls],
                                   rlen[rt]=rlen[rs]+rlen[ls],rji[rt]=rji[rs]*rji[ls],man[rt]=0;
        else if(man[ls]&&!man[rs]) rlen[rt]=rlen[rs],rji[rt]=rji[rs],
                                   llen[rt]=llen[ls]+llen[rs],lji[rt]=lji[ls]*lji[rs],man[rt]=0;
        else llen[rt]=llen[ls],rlen[rt]=rlen[rs],lji[rt]=lji[ls],rji[rt]=rji[rs],man[rt]=0;
        if(rlen[ls]&&llen[rs]) zgs[rt]=zgs[ls]+zgs[rs]-1;
        else zgs[rt]=zgs[ls]+zgs[rs];
        lv1[rt]=llen[rt]*lji[rt],rv1[rt]=rlen[rt]*rji[rt];
        if(!llen[rs]||!rlen[ls])
        {// 没有合并块
            v1[rt]=v1[ls]+v1[rs];
            v2[rt]=v2[ls]+v2[rs]+v1[rs]*zgs[ls];
            v3[rt]=v3[ls]+v3[rs]+v1[ls]*zgs[rs];
            v4[rt]=v4[ls]+v4[rs]+zgs[rs]*v2[ls]+zgs[ls]*v3[rs];
        }
        else
        {
            v1[rt]=v1[ls]+v1[rs]-rv1[ls]-lv1[rs]+rji[ls]*lji[rs]*(rlen[ls]+llen[rs]);
            v2[rt]=v2[ls]+v2[rs]-rji[ls]*zgs[ls]-lji[rs]+rji[ls]*lji[rs]*(rlen[ls]+llen[rs])*zgs[ls]+(v1[rs]-lji[rs])*(zgs[ls]-1);
            v3[rt]=v3[ls]+v3[rs]-rji[ls]-lji[rs]*zgs[rs]+rji[ls]*lji[rs]*(rlen[ls]+llen[rs])*zgs[rs]+(v1[ls]-rji[ls])*(zgs[rs]-1);
            v4[rt]=v4[ls]+v4[rs]-rji[ls]*zgs[ls]-lji[rs]*zgs[rs]+zgs[rs]*(v2[ls]-rji[ls]*zgs[ls])+zgs[ls]*(v3[rs]-lji[rs]*zgs[rs])+rji[ls]*lji[rs]*(rlen[ls]+llen[rs])*(zgs[ls]-1)*(zgs[rs]-1);
        }
    }
    void Wbuild(int rt,int l,int r)
    {
        if(l==r)
        {
            man[rt]=1;
            llen[rt]=rlen[rt]=zgs[rt]=1;
            lji[rt]=rji[rt]=a[l];
            lv1[rt]=rv1[rt]=v1[rt]=v2[rt]=v3[rt]=v4[rt]=a[l];
            return;
        }
        Wbuild(ls,l,mid),Wbuild(rs,mid+1,r);
        Wpushup(rt);
    }
    short main()
    {
        freopen(".in","r",stdin),freopen(".out","w",stdout);
        // freopen("a.in","r",stdin),freopen("a.out","w",stdout);
        n=qr,m=qr;
        fo(i,1,n) a[i]=qr;
        Wbuild(1,1,n);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

没完结不撒花