题解 P4915 【帕秋莉的魔导书】

此题的弱化版：[P4868 Preprefix sum](https://www.luogu.org/problemnew/show/P4868) ~~暑假的时候出题人请我验了这个idea，然后我随口就口胡了正解。~~ 简化一下题意： 1. 求$$\frac{\sum_{i=l}^r\sum_{j=1}^iw_i}{r-l+1}$$ 2. 单点修改$w_i$。 操作1就是求$\frac{(\sum_{i=1}^r\sum_{j=1}^iw_i)-(\sum_{i=1}^{l-1}\sum_{j=1}^iw_i)}{r-l+1}$，也就是两次查询前缀的前缀和，这样就转化为了上面的原题。 而对于求原题中的$SS_i=\sum^i_{j=1}\sum^j_{k=1}a_k$，展开$SS_i$，发现$SS_i=\sum^i_{j=1}(i-j+1)\times a_j$。 原题可以维护两个树状数组，一个维护$a_i$，另一个维护$b_i=(n-i+1)\times a_i$。这样，我们要查询的$SS_i$即为$\sum^i_{j=1}[(n-j+1)-(n-i)]\times a_j=\sum^i_{j=1}b_j-(n-i)\times\sum^i_{j=1}a_j$。 当然，此题值域较大，需要用动态开点线段树代替树状数组。 ``` #include<cstdio> #include<cctype> #include<climits> #define LL long long int Read() { int x=0;char c=getchar(); while(!isdigit(c)) { c=getchar(); } while(isdigit(c)) { x=x*10+(c^48); c=getchar(); } return x; } struct Node { int ch[2]; LL val,presum; }tree[2000005]; int root=1,cnt=1; void Update(int idx) { tree[idx].val=tree[tree[idx].ch[0]].val+tree[tree[idx].ch[1]].val; tree[idx].presum=tree[tree[idx].ch[0]].presum+tree[tree[idx].ch[1]].presum; } void Add(int pos,int val,int l=0,int r=INT_MAX,int idx=1) { if(l==r) { tree[idx].val+=val; tree[idx].presum+=(LL)val*(INT_MAX-pos+1); } else { int mid=l+r>>1; if(pos<=mid) { if(!tree[idx].ch[0])//这就是动态开点 { tree[idx].ch[0]=++cnt; } Add(pos,val,l,mid,tree[idx].ch[0]); } else { if(!tree[idx].ch[1]) { tree[idx].ch[1]=++cnt; } Add(pos,val,mid+1,r,tree[idx].ch[1]); } Update(idx); } } LL Query(int pos,int l=0,int r=INT_MAX,int idx=1) { if(r<=pos) { return tree[idx].presum-tree[idx].val*(INT_MAX-pos); } else { int mid=l+r>>1; LL res=Query(pos,l,mid,tree[idx].ch[0]); if(mid<pos) { res+=Query(pos,mid+1,r,tree[idx].ch[1]); } return res; } } int main() { int n=Read(),m=Read(),a,w; while(n--) { a=Read(),w=Read(); Add(a,w); } while(m--) { if(Read()==1) { a=Read(),w=Read(); double res=((long double)Query(w)-Query(a-1))/(w-a+1); printf("%.4lf\n",res); } else { a=Read(),w=Read(); Add(a,w); } } return 0; } ```