在一个无限长的数轴上有 \(n\) 个点。第 \(i\) 个点上面有 \(a_i\) 件物品,且第 \(i\) 个点到第 \(i+1\) 个点的距离为 \(b_i\)。
定义从第 \(i\) 个点上面的 \(x\) 件物品搬到第 \(j\) 个点的花费为 \(x\times\operatorname{dist}(i,j)\),其中 \(\operatorname{dist}(i,j)\) 即表示第 \(i\) 和第 \(j\) 个点的距离。
现在有 \(m\) 次询问,每次询问给定三个正整数 \(x,l,r\),求将所有下标在区间 \([l,r]\) 内的所有点上面的物品全部搬到第 \(x\) 个点的总花费是多少。
答案对 \(\bf 19260817\) 取模。
数据范围:\(1\leqslant n,m\leqslant 2\times 10^5\),\(1\leqslant a_i,b_i\leqslant 2\times 10^9\)。
首先我们不难写出这样的一个表示答案的式子:
\[\sum\limits_{i=l}^r a_i\times\operatorname{dist}(x,i)
\]
直接进行暴力模拟对于这道题目来说肯定是不可行的,所以我们来想一下如何优化。
首先就是这个 \(\operatorname{dist}(x,i)\)。我们根据定义可以直接推出其用 \(b_i\) 表示的式子:
\[\operatorname{dist}(x,i)=\begin{cases}\sum\limits_{j=i}^{x-1}b_j&i<x\\0&i=x\\\sum\limits_{j=x}^{i-1}b_j&\text{otherwise.}\end{cases}
\]
乍一看这式子貌似还是不太好看,我们不妨根据 \(l,r\) 和 \(x\) 的关系分类讨论以分别对应唯一的 \(\operatorname{dist}(x,i)\) 的值。
这里以 \(r<x\) 为例来具体讲讲。
在这种情况下,所有点上的东西全部往右移。容易发现 \(\forall i\in[l,r],i<x\)。因此我们直接用上面那坨式子的第一种情况化简成:
\[\sum\limits_{i=l}^r(a_i\times\sum\limits_{j=i}^{x-1}b_j)
\]
看到 \(\sum\limits_{j=i}^{x-1}b_j\) 马上想到什么?前缀和优化!
设 \(dis_i=\sum\limits_{j=1}^{i-1}b_j\),不难想到其实际意义就是第 \(i\) 个点到第 \(1\) 个点的距离。然后 \(\sum\limits_{j=i}^{x-1}b_j=\sum\limits_{j=1}^{x-1}b_j-\sum\limits_{j=1}^{i-1}b_j=dis_x-dis_i\)。
于是又可以开始愉快地化简了:
\[\begin{aligned}&\sum\limits_{i=l}^ra_i\times(dis_x-dis_i)\\=&\sum\limits_{i=l}^ra_i\cdot dis_x-\sum\limits_{i=l}^ra_i\cdot dis_i\\=&dis_x\cdot\sum\limits_{i=l}^ra_i-\sum\limits_{i=l}^ra_i\cdot dis_i\end{aligned}
\]
然后,仿照上面的套路,我们设 \(s_i=\sum\limits_{j=1}^ia_j\),\(S_i=\sum\limits_{j=1^i}a_j\cdot dis_j\)。原式子就可以化简成:
\[dis_x\cdot (s_r-s_{l-1})-(S_r-S_{l-1})
\]
然后你再把 \(dis_i,s_i,S_i\) 这三样东西全部都在询问之前先 \(\mathcal O(n)\) 预处理一下,就可以 \(\mathcal O(1)\) 回答每一次询问了。
\(l>x\) 的话,就是所有的东西全部向左移,直接用上面那坨式子的第三种情况化简一下,然后转换成我们设的这三个东西(\(dis_i,s_i,S_i\))即可。
\(l\leqslant x\leqslant r\) 这个情况稍微复杂一些。我们把区间 \([l,r]\) 以 \(x\) 为分界点分开。左边那一部分按照 \(r
这样,本题的思路就呼之欲出了:
另外,这题目要时时刻刻注意取模的问题。由于频繁取模写一大堆东西太麻烦,我这里直接用函数实现了两数相加取模、两数相减取模和两数相乘取模,这样写起来就方便很多。
虽然但是,我自己写的时候发现最终表示起来也挺复杂的。
为了少考虑些整型溢出的情况,使用了 #define int ll
。
namespace Solution {
#define int ll
const int N = 2e5 + 7, mod = 19260817;
int n, q, x, l, r, dis[N], s1[N], s2[N];
ii Add(int x, int y) {return (x + y) % mod;}
ii Del(int x, int y) {return ((x - y) % mod + mod) % mod;}
ii Mul(int x, int y) {return 1ll * x * y % mod;}
iv Main() {
read(n, q);
F(int, i, 2, n) read(dis[i]), dis[i] %= mod, dis[i] = Add(dis[i], dis[i - 1]);
F(int, i, 1, n) {
int x; read(x), x %= mod;
s1[i] = Add(s1[i - 1], x);
s2[i] = Add(s2[i - 1], Mul(x, dis[i]));
// printf("%d %d\n", s1[i], s2[i]);
}
while(q--) {
read(x, l, r);
if(r < x) println(Del(Mul(dis[x], Del(s1[r], s1[l - 1])), Del(s2[r], s2[l - 1])));
else if(l > x) println(Del(Del(s2[r], s2[l - 1]), Mul(dis[x], Del(s1[r], s1[l - 1]))));
else println(Add(Del(Mul(dis[x], Del(s1[x - 1], s1[l - 1])), Del(s2[x - 1], s2[l - 1])), Del(Del(s2[r], s2[x]), Mul(dis[x], Del(s1[r], s1[x])))));
}
return;
}
#undef int
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章