MnZn 求助线段树
查看原帖
MnZn 求助线段树
420129
Nt_Tsumiki楼主2024/7/11 16:04

rt,大概是细节写挂了

#include <algorithm>
#include <iostream>
#include <cstdio>

#define N 100001
#define LL long long

using namespace std;
int n,m;

struct Tree { LL sum,ssuml,ssumr,ssum,len,tag; }t[N<<2];
// sum 是 [l,r] 的区间和,ssuml 是 [l,r] 所包含区间中以 l 为左端点的和,ssumr 同理,ssum 为所包含区间的和

Tree pushup(Tree a,Tree b) {
    return Tree{a.sum+b.sum,a.ssuml+b.ssuml+a.sum*b.len,a.ssumr+b.ssumr+b.sum*a.len,
                a.ssum+b.ssum+a.ssumr*b.len+b.ssuml*a.len,a.len+b.len,0};
}

void build(int x,int l,int r) {
    if (l==r) return t[x]={0,0,0,0,1,0},void();
    int mid=(l+r>>1);
    build(x<<1,l,mid); build(x<<1|1,mid+1,r);
    t[x]=pushup(t[x<<1],t[x<<1|1]);
}

void pushdown(int x) {
    if (t[x].tag) {
        t[x<<1].sum+=t[x].tag*t[x<<1].len,t[x<<1|1].sum+=t[x].tag*t[x<<1|1].len;
        t[x<<1].ssuml+=t[x].tag*((t[x<<1].len+1)*t[x<<1].len/2),t[x<<1|1].ssuml+=t[x].tag*((t[x<<1|1].len+1)*t[x<<1|1].len/2);
        t[x<<1].ssumr+=t[x].tag*((t[x<<1].len+1)*t[x<<1].len/2),t[x<<1|1].ssumr+=t[x].tag*((t[x<<1|1].len+1)*t[x<<1|1].len/2);
        t[x<<1].ssum+=t[x].tag*(t[x<<1].len*(t[x<<1].len+1)*(t[x<<1].len+2)/6),
        t[x<<1|1].ssum+=t[x].tag*(t[x<<1|1].len*(t[x<<1|1].len+1)*(t[x<<1|1].len+2)/6);
        t[x].tag=0;
    }
}

void upd(int x,int l,int r,int L,int R,int k) {
    if (L>R) return;
    if (L<=l and r<=R) {
        t[x].sum+=t[x].len*k,
        t[x].ssuml+=((t[x].len+1)*t[x].len/2)*k,
        t[x].ssumr+=((t[x].len+1)*t[x].len/2)*k,
        t[x].ssum+=(t[x].len*(t[x].len+1)*(t[x].len+2)/6)*k;
        t[x].tag+=k;
        return;
    }
    int mid=(l+r>>1); pushdown(x);
    if (L<=mid) upd(x<<1,l,mid,L,R,k);
    if (R>mid) upd(x<<1|1,mid+1,r,L,R,k);
    t[x]=pushup(t[x<<1],t[x<<1|1]);
}

Tree ask(int x,int l,int r,int L,int R) {
    if (L>R) return {0,0,0,0,0,0};
    if (L<=l and r<=R) return t[x];
    int mid=(l+r>>1); pushdown(x);
    if (R<=mid) return ask(x<<1,l,mid,L,R);
    else if (L>mid) return ask(x<<1|1,mid+1,r,L,R);
    else return pushup(ask(x<<1,l,mid,L,R),ask(x<<1|1,mid+1,r,L,R));
}

int main() {
    scanf("%d",&n);
    build(1,1,n);
    scanf("%d",&m);
    for (int i=1,u,v,w;i<=m;i++) {
        char c; cin>>c;
        if (c=='C') {
            scanf("%d%d%d",&u,&v,&w);
            if (u>v) swap(u,v);
            upd(1,1,n,u+1,v,w);
        } else {
            scanf("%d%d",&u,&v);
            if (u>v) swap(u,v);
            Tree ans=ask(1,1,n,u+1,v);
            LL d=__gcd(ans.ssum,ans.len*(ans.len+1)/2);
            printf("%lld/%lld\n",ans.ssum/d,(ans.len*(ans.len+1)/2)/d);
        }
    }
    return 0;
}
2024/7/11 16:04
加载中...