题解 平方和

题目描述

给出一个 N 个整数构成的序列，有 M 次操作，每次操作有一下三种：
①Insert Y X，在序列的第 Y 个数之前插入一个数 X；
②Add L R X，对序列中第 L 个数到第 R 个数，每个数都加上 X；
③Query L R，询问序列中第 L 个数到第 R 个数的平方和。

输入格式

第一行一个正整数 N，表示初始序列长度。
第二行 N 个整数 Ai，表示初始序列中的数。
第三行一个正整数 M，表示操作数。
接下来 M 行，每行一种操作。

输出格式

对于每一个 Query 操作输出答案。由于答案可能很大，请 mod 7459 后输出。

数据范围

100%的数据满足 $N≤10^5，M≤10^5$，且 Add 和 Insert 操作中$|X|≤1000，|A_i|≤1000$。

解题思路

考场第一题就是这道数据结构，写了160+行代码喜提0分，然后改错从160行->270行，这不写篇题解庆祝一下。

显然，如果没有操作一，就是一道线段树水题，但是这个操作一就很烦，但这个题很良心，直接线段树做可以有50分。对于操作一，加入一个数并不会改变之前的数的相对位置，所以可以这样处理，先求出所有操作一后的序列，用这个序列来建立一个线段树，对于每一次修改操作，就相当于一次单点修改。剩下的直接线段树就完了。

那么问题来了，如何求出这个最终的序列，插入一个数，似乎可以链表，但是很显然，链表在这道题中需要 $O(n^2)$
插入，这就和暴力没啥区别了。可以用 Splay 来维护，考场上为了偷懒直接用了平板电视，结果假了。所以还是老老实实打粘了个 Splay 的板子上去，然后嘛，每次操作一直接在 Splay 中插入就行了，这样就可以求出每一次修改在线段树中的下标位置了。对于操作二和三，就可以直接用平板电视中的平衡数维护区间第 L 个数与第 R 个数了。
时间复杂度 $O(nlogn)$。然而 std 只有 100+行。

上面的做法纯属sb做法，直接Splay在线维护就行，当时脑抽了还加了个线段树。

代码

#include<iostream>
#include<unordered_map>
#include<cstdio>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include<ctime>
using namespace __gnu_pbds;
using namespace std;
const int N = 1e5 + 5;
const int MOD = 7459;
const int INF = 0x3f3f3f3f;
typedef long long ll;

ll id[2 * N], a[N], b[2 * N], n, m, tot;
struct query
{
    char opt[11];
    ll x, y, z;
} q[N];
struct Tree
{
    ll l, r, sum1, sum2, lz, len;
} tr[8 * N];
struct Splay
{
    struct tr
    {
        ll s[2], p, v, siz;
    } tree[8 * N];
    ll root, idx, cnt;

    void pushup(ll p)
    {
        tree[p].siz = tree[tree[p].s[0]].siz + tree[tree[p].s[1]].siz + 1;
    }

    void rotate(ll x)
    {
        ll y = tree[x].p, z = tree[y].p;
        ll k = tree[y].s[1] == x;
        tree[z].s[tree[z].s[1] == y] = x, tree[x].p = z;
        tree[y].s[k] = tree[x].s[k ^ 1], tree[tree[x].s[k ^ 1]].p = y;
        tree[x].s[k ^ 1] = y, tree[y].p = x;
        pushup(y), pushup(x);
    }

    void splay(ll x, ll k)
    {
        while (tree[x].p != k)
        {
            ll y = tree[x].p, z = tree[y].p;
            if (z != k)
            {
                if ((tree[y].s[1] == x) ^ (tree[z].s[1] == y))
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        if (!k)
            root = x;
    }

    void insert(ll v)
    {
        ll u = root, p = 0;
        while (u)
            p = u, u = tree[u].s[v > tree[u].v];
        u = ++idx;
        if (p)
            tree[p].s[v > tree[p].v] = u;
        tree[u].v = v, tree[u].siz = 1, tree[u].p = p;
        splay(u, 0);
    }

    ll getk(ll k)
    {
        ll u = root;
        while (2333)
        {
            if (tree[tree[u].s[0]].siz >= k)
                u = tree[u].s[0];
            else if (tree[tree[u].s[0]].siz + 1 == k)
                return u;
            else
                k -= tree[tree[u].s[0]].siz + 1, u = tree[u].s[1];
        }
        return -1;
    }

    void dfs(int now)
    {
        if(tree[now].s[0])
            dfs(tree[now].s[0]);
        if (tree[now].v >= 1 && tree[now].v <= 2 * n)
            b[++cnt] = tree[now].v;
        if(tree[now].s[1])
            dfs(tree[now].s[1]);
    }

} t;
tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
unordered_map<ll, ll> pos;

ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

void pushup(ll p)
{
    tr[p].sum1 = (tr[p << 1].sum1 + tr[p << 1 | 1].sum1) % MOD;
    tr[p].sum2 = (tr[p << 1].sum2 + tr[p << 1 | 1].sum2) % MOD;
    tr[p].len = tr[p << 1].len + tr[p << 1 | 1].len;
}

void pushdown(ll p)
{
    Tree &w = tr[p], &l = tr[p << 1], &r = tr[p << 1 | 1];
    ll x = w.lz, xx = w.lz * w.lz % MOD;
    l.sum2 = (l.sum2 + 2 * x * l.sum1 + xx * l.len) % MOD;
    l.sum1 = (l.sum1 + l.len * x) % MOD;
    l.lz = (l.lz + w.lz) % MOD;
    r.sum2 = (r.sum2 + 2 * x * r.sum1 + xx * r.len) % MOD;
    r.sum1 = (r.sum1 + r.len * x) % MOD;
    r.lz = (r.lz + w.lz) % MOD;
    w.lz = 0;
}

void build(ll l, ll r, ll p)
{
    tr[p].l = l, tr[p].r = r;
    if (l == r)
    {       
        if (b[l] <= n)
        {
            tr[p].len = 1;
            tr[p].sum1 = a[b[l]] % MOD;
            tr[p].sum2 = a[b[l]] * a[b[l]] % MOD;
            s.insert(l);
        }
        else
            id[b[l]] = l;
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, p << 1);
    build(mid + 1, r, p << 1 | 1);
    pushup(p);
}

void modify(ll p, ll k, ll x)
{
    if (tr[p].l == tr[p].r)
    {
        tr[p].len = 1;
        tr[p].sum1 = x % MOD;
        tr[p].sum2 = x * x % MOD;
        return;
    }
    pushdown(p);
    ll mid = (tr[p].l + tr[p].r) >> 1;
    if (k <= mid)
        modify(p << 1, k, x);
    else
        modify(p << 1 | 1, k, x);
    pushup(p);
}

void update(ll p, ll l, ll r, ll x)
{
    if (tr[p].l >= l && tr[p].r <= r)
    {
        tr[p].sum2 = (tr[p].sum2 + tr[p].sum1 * 2 * x + x * x * tr[p].len) % MOD;
        tr[p].sum1 = (tr[p].len * x + tr[p].sum1) % MOD;
        tr[p].lz = (tr[p].lz + x) % MOD;
        return;
    }
    pushdown(p);
    ll mid = (tr[p].l + tr[p].r) >> 1;
    if (l <= mid)
        update(p << 1, l, r, x);
    if (r > mid)
        update(p << 1 | 1, l, r, x);
    pushup(p);
}

ll query(ll p, ll l, ll r)
{
    if (tr[p].l >= l && tr[p].r <= r)
        return tr[p].sum2;
    pushdown(p);
    ll mid = (tr[p].l + tr[p].r) >> 1, res = 0;
    if (l <= mid)
        res = (res + query(p << 1, l, r)) % MOD;
    if (r > mid)
        res = (res + query(p << 1 | 1, l, r)) % MOD;
    return res;
}

int main()
{
    n = read();
    ll cnt = n;
    t.insert(-INF), t.insert(INF);
    for (ll i = 1; i <= n; i++)
    {
        a[i] = read();
        t.insert(i);
    }
    m = read();
    ll tot =0;
    for (ll i = 1; i <= m; i++)
    {
        scanf("%s", q[i].opt);
        if (q[i].opt[0] == 'I')
        {
            q[i].x = read(), q[i].y = read();
            ll x = t.getk(q[i].x), y = t.getk(q[i].x + 1);
            t.splay(x, 0), t.splay(y, x);
            t.tree[y].s[0] = ++t.idx;
            t.tree[t.idx].p = y, cnt++;
            t.tree[t.idx].v = n + (++tot), t.tree[t.idx].siz = 1;
            t.pushup(y), t.pushup(x);
            t.splay(t.idx, 0);
        }
        else if (q[i].opt[0] == 'A')
            q[i].x = read(), q[i].y = read(), q[i].z = read();
        else
            q[i].x = read(), q[i].y = read();
    }
    t.dfs(t.root);
    build(1, cnt, 1);
    tot = 0;
    for (ll i = 1; i <= m; i++)
    {
        if (q[i].opt[0] == 'I')
        {
            s.insert(id[n + (++tot)]);
            modify(1, id[n + tot], q[i].y);            
        }
        else if (q[i].opt[0] == 'A')
        {
            ll l = *s.find_by_order(q[i].x - 1);
            ll r = *s.find_by_order(q[i].y - 1);   
            update(1, l, r, q[i].z);            
        }
        else
        {
            ll l = *s.find_by_order(q[i].x - 1);
            ll r = *s.find_by_order(q[i].y - 1);
            printf("%lld\n", (query(1, l, r) % MOD + MOD) % MOD);
        }
    }
    return 0;
}