线段树推式子版_C

概述题：https://www.luogu.org/problem/P2221#submit 求：ans=i=l∑r?a[i]∗(r−i+1)(i−l+1) #include<bits/stdc++.h>using namespace std;typedef long long ll;#define lson root<<1,l,midd#define rson root<<1|1

题：https://www.luogu.org/problem/P2221#submit

求：ans=i=l∑r?a[i]∗(r−i+1)(i−l+1)

#include<bits/stdc++.h>using namespace std;typedef long long ll;#define lson root<<1,l,mIDd#define rson root<<1|1,mIDd+1,rconst int M=1e5+5;struct node{    ll sum[6];}tree[M<<2];ll lazy[M<<2];ll sum1,sum2,sum3;voID build(int root,ll l,ll r){    if(l==r){        tree[root].sum[4]=l;        tree[root].sum[5]=1ll*l*l;        return ;    }    int mIDd=(l+r)>>1;    build(lson);    build(rson);    tree[root].sum[4]=tree[root<<1|1].sum[4]+tree[root<<1].sum[4];    tree[root].sum[5]=tree[root<<1|1].sum[5]+tree[root<<1].sum[5];}voID up(int root){    tree[root].sum[1]=tree[root<<1].sum[1]+tree[root<<1|1].sum[1];    tree[root].sum[2]=tree[root<<1].sum[2]+tree[root<<1|1].sum[2];    tree[root].sum[3]=tree[root<<1].sum[3]+tree[root<<1|1].sum[3];}voID work(int root,ll len,ll k){    tree[root].sum[1]+=1ll*len*k;    tree[root].sum[2]+=1ll*k*tree[root].sum[4];    tree[root].sum[3]+=1ll*k*tree[root].sum[5];    lazy[root]+=1ll*k;}voID pushdown(int root,ll len){    work(root<<1,len-(len>>1),lazy[root]);    work(root<<1|1,(len>>1),lazy[root]);    lazy[root]=0;}voID update(int L,int R,ll k,int root,ll r){    if(L<=l&&r<=R){        work(root,r-l+1,k);        return ;    }    if(lazy[root])        pushdown(root,r-l+1);    ll mIDd=(l+r)>>1;    if(L<=mIDd)        update(L,R,k,lson);    if(R>mIDd)        update(L,rson);    up(root);}voID query(int L,ll r){    if(L<=l&&r<=R){        sum1+=tree[root].sum[1];        sum2+=tree[root].sum[2];        sum3+=tree[root].sum[3];        return ;    }    if(lazy[root])        pushdown(root,r-l+1);    ll mIDd=(l+r)>>1;    if(L<=mIDd)        query(L,lson);    if(R>mIDd)        query(L,rson);//    up(root);}char op[2];int main(){    int n,m;    scanf("%d%d",&n,&m);    n-=1;    build(1,1,n);    while(m--){        ll l,r;        ll z;        scanf("%s",op);        sum1=0,sum2=0,sum3=0;        if(op[0]==‘C‘){            scanf("%lld%lld%lld",&l,&r,&z);            r-=1;            update(l,r,z,1,n);        }        else{            scanf("%lld%lld",&r);            r--;            query(l,n);                        ll fenzi=(r-l-l*r+1)*sum1+(r+l)*sum2-sum3;            ll fenmu=(r-l+2)*(r-l+1)/2;            ll g=__gcd(fenzi,fenmu);                    //    cout<<fenzi<<"!!!!!!!"<<fenmu<<endl;            printf("%lld/%lld\n",fenzi/g,fenmu/g);        }    }    return 0;}