「JSOI2014」序列维护

标签：ext   sea   getchar   tps   define   temp   end   www   stdout   

「JSOI2014」序列维护

传送门
其实这题就是luogu的模板线段树2，之所以要发题解就是因为被 \(\color{black}{\text{M}} \color{red}{\text{_sea}}\) 告知了一种比较NB的 \(\text{update}\) 的方式。
我们可以把修改操作统一化，视为 \(ax + b\) 的形式，然后我们按照原来的套路来维护两个标记，分别代表 \(a\) 和 \(b\) ，那么我们的更新就可以这么写：

inline void f(int p, int atag, int mtag, int l, int r) {
    t[p].sum = (t[p].sum * mtag % P + 1ll * atag * (r - l + 1) % P) % P;
    t[p].atag = (t[p].atag * mtag + atag) % P;
    t[p].mtag = t[p].mtag * mtag % P;
}

然后我们就只需要写一个维护 \(ax + b\) 操作的修改就可以了。
其实我们还可以发现这个东西还可以用于区间赋值 \((a = 0)\)。
简直很妙有没有
参考代码：

#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
typedef long long LL;
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' > 1;
    build(lc(p), l, mid), build(rc(p), mid + 1, r), pushup(p);
}
 
inline void update(int ql, int qr, LL atag, LL mtag, int p = 1, int l = 1, int r = n) {
    if (ql > 1;
    pushdown(p, l, r, mid);
    if (ql  mid) update(ql, qr, atag, mtag, rc(p), mid + 1, r);
    pushup(p);
}
 
inline LL query(int ql, int qr, int p = 1, int l = 1, int r = n) {
    if (ql > 1; LL res = 0;
    pushdown(p, l, r, mid);
    if (ql  mid) res = (res + query(ql, qr, rc(p), mid + 1, r)) % P;
    return res;
}
 
int main() {
#ifndef ONLINE_JUDGE
    file("cpp");
#endif
    read(n), read(P);
    for (rg int i = 1; i 

「JSOI2014」序列维护

标签：ext   sea   getchar   tps   define   temp   end   www   stdout   

原文地址：https://www.cnblogs.com/zsbzsb/p/12249903.html