P8421 [THUPC2022 决赛] rsraogps是什么算法？
摘要：$text{Solution}$ 肯定扫描线在考虑维护什么东西，假设 $r$ 右移时可以暴力得到所有新值，发现需要维护区间历史版本和以及区间当前值之和 这三个操作对于一个数来说变化次数都是 $O(logV)$ 的，所以可以暴力修改发生变化
\(\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