UVA12436 Rip Van Winkle’s Code 题解

题目链接：UVA12436 Rip Van Winkle’s Code

题意：

cxy 对除了妹纸和编程之外的一切都感到厌烦。

有一天，她发现了一个问题，需要执行三种类型的更新操作 $\mathtt{A,B,C}$，

以及一个查询操作 $S$ ，针对一个数组 $\mathtt{data[]}$ ，初始时，$\mathtt{data}$ 的所有元素都等于 $0$ 。

虽然 cxy 要和妹纸玩耍，而且她的代码也非常慢，

但你需要以高效的方式执行相同的更新操作，并输出查询操作 $S$ 的结果。

long long data[250001];
void A( int st, int nd ) {
	for( int i = st; i <= nd; i++ ) data[i] = data[i] + (i - st + 1);
}
void B( int st, int nd ) {
	for( int i = st; i <= nd; i++ ) data[i] = data[i] + (nd - i + 1);
}
void C( int st, int nd, int x ) {
    for( int i = st; i <= nd; i++ ) data[i] = x;
}
long long S( int st, int nd ) {
    long long res = 0;
    for( int i = st; i <= nd; i++ ) res += data[i];
    return res;
}

输入格式：

输入的第一行将包含一个整数 $T\left(T \leq 4 \times 10^5\right)$，表示操作的数量。接下来的 $T$ 行中，每行以一个字符（A、B、C 或 S）开头，该字符表示操作的类型。字符 A、B 或 S 后面将跟随两个整数 $\mathrm{st}$ 和 $\mathrm{nd}$。字符 C 后面将跟随三个整数 $\mathrm{st}$、$\mathrm{nd}$ 和 $x$。假设 $1 \leq \mathrm{st} \leq \mathrm{nd} \leq 2.5\times 10^5$ 且 $-10^5 \leq x \leq 10^5$。这些整数的含义由 Rip Van Winkle 代码解释。

输出格式：

对于每一行以字符 S 开头的行，请按照代码中定义的方式打印出 $S(\mathrm{st}, \mathrm{nd})$。

操作1,2就是区间加等差数列，操作3就是区间赋值，操作4就是查询区间和。

之前维护差分的做法就不是很好做了，毕竟有区间和（之前是单点查询）

考虑直接维护差分。分别记 $\mathtt{setB[],setD[],sufB[],sufD[],preB[],preD[]}$ 用于维护：

1. sum[]：保存每个节点表示的区间内元素的和。即线段树的节点值数组。
2. preB[] 和 preD[]：用于进行增加操作时的前缀和更新。preB保存等差数列的初始值，preD保存等差数列的公差。
3. sufB[] 和 sufD[]：用于进行增加操作时的后缀和更新。sufB保存等差数列的初始值，sufD保存等差数列的公差。
4. setB[] 和 setD[]：用于进行赋值操作时的标记。setB表示是否进行了赋值操作，setD表示赋值的值。

具体维护方式见代码。时间复杂度是 $\mathcal{O}(T \log N)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N (1048576 + 15)
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

const int n = (1ll << 18);
int sum[N], preB[N], preD[N], sufB[N], sufD[N], setB[N], setD[N];
void push_up(int at) {
    sum[at] = sum[ls(at)] + sum[rs(at)];
}
void procSet(int l,int r,int at)
{
    setB[at] = true; setD[at] = setD[at >> 1];
    preB[at] = preD[at] = sufB[at] = sufD[at] = 0;
    sum[at] = (r - l + 1) * setD[at >> 1];
}
void push_down(int l,int r,int at)
{
    int mid = (l + r) >> 1;
    if(setB[at])
    {
        procSet(l, mid, ls(at));
        procSet(mid + 1, r, rs(at));
        setB[at] = false; setD[at] = 0;
    }
    if(preB[at])
    {
        preB[ls(at)] += preB[at]; preD[ls(at)] += preD[at];
        sum[ls(at)] += (2 * preB[at] + (mid - l) * preD[at]) * (mid - l + 1) / 2;
        preB[rs(at)] += preB[at] + preD[at] * (mid - l + 1); preD[rs(at)] += preD[at];
        sum[rs(at)] += (2 * preB[at] + (r - l + mid + 1 - l) * preD[at]) * (r - mid) / 2;
        preB[at] = preD[at] = 0;
    }
    if(sufB[at])
    {
        sufB[ls(at)] += sufB[at] + (r - mid) * sufD[at]; sufD[ls(at)] += sufD[at];
        sum[ls(at)] += (2 * sufB[at] + (r - mid + r - l) * sufD[at]) * (mid - l + 1) / 2;
        sufB[rs(at)] += sufB[at]; sufD[rs(at)] += sufD[at];
        sum[rs(at)] += (2 * sufB[at] + (r - mid - 1) * sufD[at]) * (r - mid) / 2;
        sufB[at] = sufD[at] = 0;
    }
}
void updateA(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr)
    {
        preB[at] += l - nl + 1; preD[at] += 1;
        sum[at] += (2 * (l - nl + 1) + r - l) * (r - l + 1) / 2; return; 
    }
    push_down(l, r, at); int mid = (l + r) >> 1;
    if(nl <= mid) updateA(nl, nr, l, mid, ls(at));
    if(nr > mid) updateA(nl, nr, mid + 1, r, rs(at));
    push_up(at);
}
void updateB(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr)
    {
        sufB[at] += nr - r + 1; sufD[at] += 1;
        sum[at] += (2 * (nr - r + 1) + r - l) * (r - l + 1) / 2; return;
    }
    push_down(l, r, at); int mid = (l + r) >> 1;
    if(nl <= mid) updateB(nl, nr, l, mid, ls(at));
    if(nr > mid) updateB(nl, nr, mid + 1, r, rs(at));
    push_up(at);
}
void updateC(int nl,int nr,int k, int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr)
    {
        setB[at] = true; setD[at] = k;
        preB[at] = preD[at] = sufB[at] = sufD[at] = 0;
        sum[at] = k * (r - l + 1); return ;
    }
    push_down(l, r, at); int mid = (l + r) >> 1;
    if(nl <= mid) updateC(nl, nr, k, l, mid, ls(at));
    if(nr > mid) updateC(nl, nr, k, mid + 1, r, rs(at));
    push_up(at);
}
int query(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr) return sum[at];
    push_down(l, r, at); int mid = (l + r) >> 1, res = 0;
    if(nl <= mid) res += query(nl, nr, l, mid, ls(at));
    if(nr > mid) res += query(nl, nr, mid + 1, r, rs(at));
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; char ch; cin >> Q;
    for(int l,r,k; Q--; )
    {
        if(cin >> ch, ch == 'C') {
            cin >> l >> r >> k;
        }else { cin >> l >> r; }

        if(ch == 'A') updateA(l, r);
        else if(ch == 'B') updateB(l, r);
        else if(ch == 'C') updateC(l, r, k);
        else if(ch == 'S') cout << query(l, r) << '\n';
        else { cout << "Great." << '\n'; }
    }
    return 0;
}