P8421 [THUPC2022 决赛] rsraogps

\(\text{Solution}\)

肯定扫描线在考虑维护什么东西，假设 \(r\) 右移时可以暴力得到所有新值，发现需要维护区间历史版本和以及区间当前值之和

这三个操作对于一个数来说变化次数都是 \(O(logV)\) 的，所以可以暴力修改发生变化的值的位置

这显然是一段后缀，可以直接暴力更新，原因是考虑到每个位置的数在变化的情况下至多操作 \(O(logV)\) 次便不再变化

那么前缀值不变的呢？需要维护区间历史版本和和当前值之和

这个经典问题一般打标记解决，其实具体来说是维护一些形如 \(Pt+Q\) 的值

\(P\) 是当前值，\(t\) 是更新为这个值的时间，\(Q\) 是更新前历史版本和

那么在 \(T\) 时刻（\(t\) 到 \(T\) 时刻不发生修改，若发生修改则需更新这些值）这个位置的贡献是 \(P(T-t+1)+Q\)

区间贡献和就是维护 \(\sum P_i(T-t_i+1)+Q_i=(T+1)\sum P_i+\sum P_i t_i + \sum Q_i\) 这三部分值的区间和

因为可以暴力更改一段后缀，前缀这三部分值不需要更新，所以可以暴力扫一次后缀更新出新的前缀和

\(O(n logV+q)\)

\(\text{Code}\)

#include <bits/stdc++.h>

#define IN inline

using namespace std;

template<typename Tp>

IN void read(Tp &x) {

    x = 0; char ch = getchar(); int f = 0;

    for(; !isdigit(ch); f |= (ch == '-'), ch = getchar());

    for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());

    if (f) x = ~x + 1;

}

int num[55];

IN void write(auto x) {

    if (!x) return putchar('0'), void();

    if (x < 0) putchar('-'), x = -x;

    while (x) num[++num[0]] = x % 10, x /= 10;

    while (num[0]) putchar(num[num[0]] + '0'), --num[0];

}

typedef unsigned int uint;

const int N = 1e6 + 5, M = 5e6 + 5;

int n, m;

uint a[N], b[N], c[N], ans[M], hvs[N], tg[N], s0[N], s1[N], s2[N];

struct Que{int l, r, id;}Q[M];

IN uint Query(int x, int T){return s0[x] + s1[x] * (T + 1) - s2[x];}

int main() {

    read(n), read(m);

    for(int i = 1; i <= n; i++) read(a[i]);

    for(int i = 1; i <= n; i++) read(b[i]);

    for(int i = 1; i <= n; i++) read(c[i]);

    for(int i = 1; i <= m; i++) read(Q[i].l), read(Q[i].r), Q[i].id = i;

    sort(Q + 1, Q + m + 1, [](Que x, Que y){return x.r < y.r;});

    for(int i = 1, R = 1; i <= n; i++) {

        int j; tg[i] = i;

        for(j = i - 1; j; j--) {

            uint u = a[j] & a[j + 1], v = b[j] | b[j + 1], w = __gcd(c[j], c[j + 1]);

            if (u == a[j] && v == b[j] && w == c[j]) break;

            hvs[j] += a[j] * b[j] * c[j] * (i - tg[j]), tg[j] = i;

            a[j] = u, b[j] = v, c[j] = w;

        }

        for(int k = j + 1; k <= i; k++)

            s0[k] = s0[k - 1] + hvs[k], s1[k] = s1[k - 1] + a[k] * b[k] * c[k], s2[k] = s2[k - 1] + a[k] * b[k] * c[k] * tg[k];

        while (R <= m && Q[R].r == i) ans[Q[R].id] += Query(Q[R].r, i) - Query(Q[R].l - 1, i), ++R;

    }

    for(int i = 1; i <= m; i++) write(ans[i]), puts("");

}

巴特西

P8421 [THUPC2022 决赛] rsraogps

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章