题意：修改区间内的数、询问区间内任意子段和的期望值。

然后我们尝试把每次的答案求出来。然后对这个式子乱搞。发现对于每个数a[i]，维护a[i],i*a[i],i*i*a[i]就好了、

那么线段树维护就行了。好了没了。（其实是我懒得写题解了、、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson l,mid,ls
#define rson mid+1,r,rs
#define root 1,n,1
typedef long long ll;
const int maxn=500005;
ll a[maxn]={0},b[maxn]={0},c[maxn]={0},add[maxn]={0};
char buf[5000000],*pt=buf,buf2[5000000],*o=buf2;
inline ll getint(){
    ll r=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++; if(*pt=='-')f=-1, pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;   return r*f;
}inline char getop(){
    while(*pt!='C'&&*pt!='Q')pt++;  return *pt;
}inline void print(ll x){
    char str[30],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}inline void pushup(ll rt){
    a[rt]=a[ls]+a[rs], b[rt]=b[ls]+b[rs], c[rt]=c[ls]+c[rs];
}inline void pushdown(ll l,ll r,ll rt){
    ll lc=mid-l+1, rc=r-mid, rr=mid, ll=mid+1;  
    if(add[rt]){
        add[ls]+=add[rt];
        a[ls]+=lc*add[rt];
        b[ls]+=(l+rr)*lc*add[rt]>>1;
        c[ls]+=(rr*(rr+1)*(rr<<1|1)-(l-1)*l*(l-1<<1|1))/6*add[rt];
        add[rs]+=add[rt];
        a[rs]+=rc*add[rt];
        b[rs]+=(ll+r)*rc*add[rt]>>1;
        c[rs]+=(r*(r+1)*(r<<1|1)-(ll-1)*ll*(ll-1<<1|1))/6*add[rt];
        add[rt]=0;
    }
}void update(ll L,ll R,ll d,ll l,ll r,ll rt){
    if(L<=l&&r<=R){
        add[rt]+=d;
        a[rt]+=(r-l+1)*d;
        b[rt]+=(l+r)*(r-l+1)*d>>1;
        c[rt]+=(r*(r+1)*(r<<1|1)-(l-1)*l*(l-1<<1|1))/6*d;
        return;
    }pushdown(l,r,rt);
    if(L<=mid)  update(L,R,d,lson);
    if(mid<R)   update(L,R,d,rson);
    pushup(rt);
}void query(ll L,ll R,ll&A,ll&B,ll&C,ll l,ll r,ll rt){
    if(L<=l && r<=R){
        A=a[rt],B=b[rt],C=c[rt]; return;
    }pushdown(l,r,rt);
    ll SA=0,SB=0,SC=0,TA,TB,TC;
    if(L<=mid)  query(L,R,TA,TB,TC,lson), SA+=TA, SB+=TB, SC+=TC;
    if(mid<R)   query(L,R,TA,TB,TC,rson), SA+=TA, SB+=TB, SC+=TC;
    A=SA,B=SB,C=SC;
}inline ll gcd(ll a,ll b){
    return (!b)?a:gcd(b,a%b);
}int main(){ 
    fread(pt,1,5000000,stdin);  ll n,q,u,v,w,TA,TB,TC,A,B,C;
    for(n=getint(),q=getint();q;q--){
        if(getop()=='C'){
            u=getint(),v=getint(),w=getint();
            update(u,v-1,w,root);
        }else{
            u=getint(),v=getint();
            query(u,v-1,TA,TB,TC,root);
            A=(u+v-1)*TB+TA*(v-v*u)-TC;
            B=(v-u+1)*(v-u)>>1;
            C=gcd(A,B);
            print(A/C);*o++='/';print(B/C);*o++='\n';
        }
    }fwrite(buf2,1,o-buf2,stdout);return 0;
}

• 相关文章