【NOIP模拟】聚会
聚会
描述
在成都的一条街道上,一共有 NN户人家,每个家庭有 XiXi 个人,他们和谐的生活在 一起,作为全国和谐街道,他们经常会小范围组织活动,每次活动会选择一户作为聚点, 并要求某些家庭参加,为了方便通知,村长每次邀请位置连续的家庭。因为每户人数不 同,每个家庭之间有一定距离,村长希望你计算出每次邀请的家庭的移动代价。第 ii个家 庭移动到家庭 jj的代价是:Xi∗dis(i,j)Xi∗dis(i,j)
dis(i,j)dis(i,j)表示ii 到jj的距离,村长一共安排了 mm 次聚会,每次邀请[Li,Ri][Li,Ri]的家庭参加
输入
第一行两个数表示 n,m
第二行 n-1 个数,第 i 个数表示第 i 个家庭与第 i+1 个家庭的距离 Di
第三行 n 个数,表示每个家庭的人数 Xi
之后 m 行每行三个数 x l r,表示查询要把区间 [l,r]的家庭移动到 x 点的代价和
输出
对于每个询问输出一个数表示答案,对 19260817 取模
样例输入
5 5
2 3 4 5
1 2 3 4 5
1 1 5
3 1 5
2 3 3
3 3 3
1 5 5
样例输出
125
72
9
0
70
提示
对于 30%的数据, n,m≤1000
对于另外 20%的数据,所有家庭间的距离都为 1
对于另外 20%的数据,所有家庭人数都为 1
对于 100%的数据 , n,m≤200000;Xi,Di <=2*10^9
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
const int Max=200005;
int n,m,ans,pos[Max],num[Max],sum1[Max],sum2[Max];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void print(int x)
{
if(x>9) print(x/10);
putchar('0'+x%10);
}
inline int calc1(int x,int l,int r){return ((sum2[r]-sum2[l-1])%mod+mod)%mod-x%mod*((sum1[r]-sum1[l-1])%mod+mod)%mod;}
inline int calc2(int x,int l,int r){return x%mod*((sum1[r]-sum1[l-1])%mod+mod)%mod-((sum2[r]-sum2[l-1])%mod+mod)%mod;}
inline void solve()
{
while(m--)
{
int x=get_int(),l=get_int(),r=get_int();
if(x<l) ans=calc1(pos[x],l,r)%mod;
else if(x>r) ans=calc2(pos[x],l,r)%mod;
else ans=(calc1(pos[x],x,r)+calc2(pos[x],l,x))%mod;
print((ans%mod+mod)%mod),putchar('\n');
}
}
signed main()
{
n=get_int(),m=get_int();
for(int i=2;i<=n;i++) pos[i]=get_int();
for(int i=2;i<=n;i++) pos[i]=(pos[i]+pos[i-1])%mod;
for(int i=1;i<=n;i++) sum1[i]=num[i]=get_int(),sum2[i]=(num[i]*pos[i])%mod;
for(int i=2;i<=n;i++) sum1[i]=(sum1[i]+sum1[i-1])%mod,sum2[i]=(sum2[i]+sum2[i-1])%mod;
solve();
return 0;
}