题目:
1297: Tr0y And His Startup
时间限制: 1 Sec 内存限制: 256 MB提交: 18 解决: 8
[提交][状态][讨论版]
题目描述
Tr0y创办了一家安全公司，主要提供抗DDoS服务。
假设有n家公司共用Tr0y的第三方服务器，各公司初始最大承受带宽为xi Gbps，当其受到大于或等于最大承受带宽流量时，会判断为DDoS攻击并进行清洗操作，将流量引到第三方服务器。
下面有Q次攻击，每次使得[Li,Ri]的公司遭受到流量为c Gbps（c为整数，在[1,C]上离散均匀分布）的攻击，且每家公司在承受攻击后会增大qi Gbps的最大承受带宽。
Tr0y的资金有限，他想知道每次攻击时，他的服务器期望承受流量为多少？
答案应该会很大，请膜1e9+7
输入
第一行为三个整数n(1<=n<=1e5),C(1e7<=C<=1e9),Q(1<=n<=1e5)。
第二行含n个整数xi(1<=xi<=10)。
接下来Q行，每行包含三个整数L,R(1<=L<=R<=n),q(1<=q<=10).
输出
共Q行，每行输出服务器期望承受流量.
样例输入
3 10000000 3
1 2 3
1 1 1
1 2 1
1 3 1
样例输出
505000004
581428605
86428702
分析: 求期望,但是有个条件,必须大于等于xi--公式:1/2c*[(c+xi)(c-xi+1)]
1/2c*[c^2+c-xi^2+xi]
这是个区间求和问题 用线段树维护区间和sum1,区间平方和sum2
更新的话,懒惰标记; 其中_sum2=(x1+k)^2+(x2+k)^2+...(xn+k)^2
=x1^2+...+xn^2+2*k*sum1+k*k*n
很好维护的,但是感觉这题有个问题啊
求逆元不是可以随便用的啊 a/b%mod=a*b1(b的逆元)%mod 前提必须是a可以整除b.
这道题不严谨,数据是错的(也欢迎指正
还有错了那么多次,是因为数据类型转化出错了; tag[]是long long类型,在_update()函数中k定义为了int
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define lson l,m,rt*2 4 #define rson m+1,r,rt*2+1 5 typedef long long LL; 6 const LL mod=1e9+7; 7 const int N=1e5+7; 8 LL sum1[N*4],sum2[N*4],tag[N*4]; 9 LL c; int n,q; 10 LL q_pow (LL x,LL k) { 11 LL ans=1; 12 while (k) { 13 if (k&1) ans=ans*x%mod; 14 x=x*x%mod; 15 k=k>>1; 16 } 17 return ans; 18 } 19 void pushup(int rt) { 20 sum1[rt]=(sum1[rt*2]+sum1[rt*2+1])%mod; 21 sum2[rt]=(sum2[rt*2]+sum2[rt*2+1])%mod; 22 } 23 void build (int l,int r,int rt) { 24 if (l==r) { 25 scanf ("%lld",&sum1[rt]); 26 sum2[rt]=sum1[rt]*sum1[rt]%mod; 27 return ; 28 } 29 int m=(l+r)/2; 30 build (lson); 31 build (rson); 32 pushup(rt); 33 return ; 34 } 35 void _update (LL k,int l,int r,int rt) { 36 // 千万注意 LL->int 会爆炸!!!! 37 tag[rt]=(tag[rt]+k)%mod; 38 sum2[rt]=(sum2[rt]+sum1[rt]*2*k%mod+k*k%mod*(r-l+1)%mod)%mod; 39 sum1[rt]=(sum1[rt]+k*(r-l+1)%mod)%mod; 40 } 41 void pushdown(int l,int r,int rt) { 42 if (tag[rt]!=0) { 43 int m=(l+r)/2; 44 _update(tag[rt],l,m,rt*2); 45 _update(tag[rt],m+1,r,rt*2+1); 46 tag[rt]=0; 47 } 48 } 49 LL update (int L,int R,int k,int l,int r,int rt) { 50 if (l>R||r<L) return 0; 51 if (l>=L&&r<=R) { 52 LL ans=(sum2[rt]-sum1[rt]+mod)%mod; 53 _update(k,l,r,rt); 54 return ans; 55 } 56 pushdown(l,r,rt); 57 int m=(l+r)/2; 58 LL ans=(update(L,R,k,lson)+update(L,R,k,rson))%mod; 59 pushup(rt); 60 return ans; 61 } 62 int main () 63 { 64 while (~scanf ("%d %lld %d",&n,&c,&q)) { 65 memset (tag,0,sizeof(tag)); 66 build (1,n,1); 67 LL t1=q_pow (2*c,mod-2); LL t2=c*(c+1)%mod; 68 for (int i=1;i<=q;i++) { 69 int l,r,k; scanf ("%d %d %d",&l,&r,&k); 70 LL ans=update (l,r,k,1,n,1); 71 printf("%lld ",((r-l+1)*t2%mod-ans+mod)*t1%mod); 72 } 73 } 74 return 0; 75 }