题目:
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
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt*2
#define rson m+1,r,rt*2+1
typedef long long LL;
const LL mod=1e9+;
const int N=1e5+;
LL sum1[N*],sum2[N*],tag[N*];
LL c; int n,q;
LL q_pow (LL x,LL k) {
LL ans=;
while (k) {
if (k&) ans=ans*x%mod;
x=x*x%mod;
k=k>>;
}
return ans;
}
void pushup(int rt) {
sum1[rt]=(sum1[rt*]+sum1[rt*+])%mod;
sum2[rt]=(sum2[rt*]+sum2[rt*+])%mod;
}
void build (int l,int r,int rt) {
if (l==r) {
scanf ("%lld",&sum1[rt]);
sum2[rt]=sum1[rt]*sum1[rt]%mod;
return ;
}
int m=(l+r)/;
build (lson);
build (rson);
pushup(rt);
return ;
}
void _update (LL k,int l,int r,int rt) {
// 千万注意 LL->int 会爆炸!!!!
tag[rt]=(tag[rt]+k)%mod;
sum2[rt]=(sum2[rt]+sum1[rt]**k%mod+k*k%mod*(r-l+)%mod)%mod;
sum1[rt]=(sum1[rt]+k*(r-l+)%mod)%mod;
}
void pushdown(int l,int r,int rt) {
if (tag[rt]!=) {
int m=(l+r)/;
_update(tag[rt],l,m,rt*);
_update(tag[rt],m+,r,rt*+);
tag[rt]=;
}
}
LL update (int L,int R,int k,int l,int r,int rt) {
if (l>R||r<L) return ;
if (l>=L&&r<=R) {
LL ans=(sum2[rt]-sum1[rt]+mod)%mod;
_update(k,l,r,rt);
return ans;
}
pushdown(l,r,rt);
int m=(l+r)/;
LL ans=(update(L,R,k,lson)+update(L,R,k,rson))%mod;
pushup(rt);
return ans;
}
int main ()
{
while (~scanf ("%d %lld %d",&n,&c,&q)) {
memset (tag,,sizeof(tag));
build (,n,);
LL t1=q_pow (*c,mod-); LL t2=c*(c+)%mod;
for (int i=;i<=q;i++) {
int l,r,k; scanf ("%d %d %d",&l,&r,&k);
LL ans=update (l,r,k,,n,);
printf("%lld\n",((r-l+)*t2%mod-ans+mod)*t1%mod);
}
}
return ;
}