题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2752
题意：区间加，询问区间随机两个端点的期望权值和。
$$ans=\frac{len_i*（i-l+1)*(r-i)}{(R-L)*(R-L+1)/2}$$
暴力展开，发现只需要维护\(len_i\)，\(len_i*i\) 和\(len_i*i*i\) 的和即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);} int n,m; ll bin[N],bin2[N]; ll sum1[N<<2],sum2[N<<2],sum3[N<<2]; ll add[N<<2]; void cal(int x,int l,int r,ll v) { sum1[x]+=v*(ll)(r-l+1); sum2[x]+=(ll)v*(bin[r]-bin[l-1]); sum3[x]+=(ll)v*(bin2[r]-bin2[l-1]); } void pushup(int x) { int l=x<<1,r=x<<1|1; sum1[x]=sum1[l]+sum1[r]; sum2[x]=sum2[l]+sum2[r]; sum3[x]=sum3[l]+sum3[r]; } void pushdown(int x,int l,int r) { if(add[x]) { int mid=(l+r)>>1; add[x<<1]+=add[x],cal(x<<1,l,mid,add[x]); add[x<<1|1]+=add[x],cal(x<<1|1,mid+1,r,add[x]); add[x]=0; } } ll L,R,V; void update(int x,int l,int r) { if(l>=L&&r<=R) { add[x]+=V; cal(x,l,r,V); return ; } pushdown(x,l,r); int mid=(l+r)>>1; if(L<=mid) update(x<<1,l,mid); if(R>mid) update(x<<1|1,mid+1,r); pushup(x); } ll query(int x,int l,int r) { if(l>=L&&r<=R) return sum1[x]*(R-L*R)+sum2[x]*(R+L-1)-sum3[x]; pushdown(x,l,r); int mid=(l+r)>>1; ll ret=0; if(L<=mid) ret+=query(x<<1,l,mid); if(R>mid) ret+=query(x<<1|1,mid+1,r); return ret; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) bin[i]=bin[i-1]+i,bin2[i]=bin2[i-1]+(ll)i*i; while(m--) { char opt=getchar(); while(opt!='C'&&opt!='Q')opt=getchar(); L=read(),R=read(); if(opt=='C') { R--; V=read(); update(1,1,n); } else { ll tmp=(R-L)*(R-L+1)/2ll; ll ans=query(1,1,n); ll ret=gcd(ans,tmp); printf("%lld/%lld\n",ans/ret,tmp/ret); } } } |
Comments | NOTHING