P3932 浮游大陆的68号岛

P3932 浮游大陆的68号岛

无聊找了个水题做。

大概就是前缀和乱搞一下没了，除了前缀和啥都没有。建议降绿。

考虑对于一个点 \(i\) 到询问点 \(x\)：

  • 如果 \(i \lt x\) 那么 等价于 \(dis_i \cdot val_i - dis_x \cdot val_i\)
  • 如果 \(i \gt x\) 那么 等价于 \((dis_N - dis_i) \cdot val_i - (dis_N - dis_x) \cdot val_i\)
  • 如果 \(i = x\) 那么 你懂的。

然后没啥东西。询问区间拆开分开做就完了。

/*
	Name:
	Author: Gensokyo_Alice
	Date:
	Description:
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
const ll MAXN = 1e6+10, MOD = 19260817;

ll N, M, dis[MAXN], val[MAXN], lt[MAXN], rt[MAXN];

ll lans(ll, ll, ll);
ll rans(ll, ll, ll);

int main() {
	scanf("%lld%lld", &N, &M);
	for (ll i = 2; i <= N; i++) scanf("%lld", &dis[i]);
	for (ll i = 1; i <= N; i++) (dis[i] += dis[i-1]) %= MOD, scanf("%lld", &val[i]), lt[i] = val[i] * dis[i] % MOD;
	for (ll i = 1; i <= N; i++) rt[i] = (dis[N] - dis[i]) % MOD * val[i] % MOD;
	for (ll i = 1; i <= N; i++) (lt[i] += lt[i-1]) %= MOD, (rt[i] += rt[i-1]) %= MOD, (val[i] += val[i-1]) %= MOD;
	for (ll i = 1, x, l, r; i <= M; i++) {
		scanf("%lld%lld%lld", &x, &l, &r);
		if (x == l && x == r) puts("0");
		else if (x < l) {
			printf("%lld\n", lans(x, l, r) % MOD);
		} else if (x > r) {
			printf("%lld\n", rans(x, l, r) % MOD);
		} else if (x == l) {
			printf("%lld\n", lans(x, l+1, r) % MOD);
		} else if (x == r) {
			printf("%lld\n", rans(x, l, r-1) % MOD);
		} else {
			printf("%lld\n", (rans(x, l, x-1) + lans(x, x+1, r) + 2 * MOD) % MOD);
		}
	}
    return 0;
}

// $\sum_{i=l}^{r} lt[i] - dis[x] * val[i]$
ll lans(ll pos, ll l, ll r) {return (((lt[r] - lt[l-1]) % MOD - (dis[pos] * (val[r] - val[l-1]) % MOD)) % MOD + MOD) % MOD;}
// $\sum_{i=l}^{r} rt[i] - (dis[n] - dis[x]) * val[i]$
ll rans(ll pos, ll l, ll r) {return (((rt[r] - rt[l-1]) % MOD - ((dis[N] - dis[pos]) % MOD * (val[r] - val[l-1]) % MOD) % MOD) % MOD + MOD) % MOD;}

/*
5 3
2 3 4 5
1 2 3 4 5
2 3 3
3 3 3
1 5 5
*/
模拟暴力

相关

Cento7 将每小时SSH暴力破解（登陆失败）超过10次的ip加入系统黑名单----系统安全篇

使用webgl(three.js)搭建一个3D智慧园区、3D建筑，3D消防模拟，web版3D,bim管理系统——第

noip多校模拟30

2019.11.8模拟赛

[NOIP模拟赛] 2021.11.16

20211116 NOIP 模拟赛

项目实战：Qt+C#轨道交通行业高性能高流畅度模拟火车移动图像控件

ASP.NET Core管道深度剖析（2）：创建一个“迷你版”的管道来模拟真实管道请求处理流程

NOIP模拟99(多校31)

20210628模拟赛解题报告

20201115gryz模拟赛解题报告

N体模拟数据可视化 LightningChart®

标签