UOJ #213 圣杯战争

既然是圣杯战争,那主题图片就放一张fate的图咯

pid:70587790_p0

题目:UOJ #213


题意概述:

给你一个序列,定义一个连续子序列的贡献为这个序列中的最大值,分别求对于每种长度的所有连续子序列的贡献,输出异或和。

思路:

看到这道题,大概就能想到对于每一个节点计算贡献。考虑维护每一个端点所统治的区间,进行一番分类讨论:

p r_i – i + 1 i – l_i + 1 中较小的一个, q 为较大的一个。
对于 [1, p) 中的所有长度,加上 a_i \times i
对于 [p, q) 中的所有长度,加上 a_i \times p
对于 [q, p + q) 中的所有长度, 加上 (p + q – i) \times a_i
(只要画张图冷静分析一下就好了)

然后看到区间加的操作,大概想到可以差分,但是这里会加入的是 x \times i ,所以可以考虑维护另一个差分数组,将其前缀和乘上 i 加入答案即可。

hint:

有一个小提示我不得不说……就是 l r 中有一个是 \geq 另一个是<,不然会重复计算贡献,不要搞错了(瞪眼瞪了一万年

代码:

这个LL滥用是因为一开始爆int了,懒得一个一个改了233
还有这个 lr ,我的求法可能和大家不是很一样,其他人基本上写得是单调队列,我写的是类似kmp里面fail数组的求法

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 998244353, N = 1e6 + 100;

LL ori[N], a[N], l[N], r[N], d1[N], d2[N];

int main()
{
    LL n, ans = 0;
    scanf("%lld", &n);
    for (LL i = 1; i <= n; i++) scanf("%lld", a + i);
    for (LL i = 1; i <= n; i++)
        for (l[i] = i; l[i] - 1 >= 1 && a[l[i] - 1] <= a[i]; l[i] = l[l[i] - 1]);
    for (LL i = n; i >= 1; i--)
        for (r[i] = i; r[i] + 1 <= n && a[r[i] + 1] < a[i]; r[i] = r[r[i] + 1]);
    for (LL i = 1; i <= n; i++)
    {
        LL p = i - l[i] + 1, q = r[i] - i + 1; if (p > q) swap(p, q);
        d1[1] += a[i], (d1[p] += MOD - a[i]) %= MOD;
        d2[p] += p * a[i], (d2[q] += MOD - p * a[i] % MOD) %= MOD;
        (d1[q] += MOD - a[i]) %= MOD, d1[p + q] += a[i],
        d2[q] += (p + q) * a[i], (d2[p + q] += MOD - (LL)(p + q) * a[i] % MOD) %= MOD;
    }
    for (LL i = 1; i <= n; i++)
    {
        (d1[i] += d1[i - 1]) %= MOD, (d2[i] += d2[i - 1]) %= MOD;
        ans ^= (d1[i] * i + d2[i] + MOD) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注