P5524 [Ynoi2012] NOIP2015 充满了希望

zuytong · 2022-09-07 09:35:19 · 题解

思路

我们考虑开一棵线段树，表示区间 [l,r] 最后一次操作 2 的时间戳。

对于操作 1：我们交换树上 x 和 y 两点的值。

对于操作 2：我们进行区间 [l,r] 赋值。

对于操作 3：我们查询树上 x 点的值，并记录为 t_i。

考虑将所有的询问离线下来，对 r 做扫描线：遇到操作 3 时，我们在 t_i 的位置加上 val[t_i] 并更新前缀和；对于询问 [l,r]，我们查询 l 的后缀和，这个可以通过树状数组实现。

由于 n,m,q 同阶，时间复杂度为 O(n\log n)。

代码

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt)
inline int reads()
{
    int sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
int n, m, q;
int ty[1000005], x[1000005], y[1000005], val[1000005];
int tr[4000005];
#define ls (now << 1)
#define rs ((now << 1) | 1)
inline void down(int now)
{
    if(tr[now])
    {
        tr[ls] = tr[rs] = tr[now];
        tr[now] = 0;
    }
}
void modify(int now, int l, int r, int L, int R, int ti)
{
    if(L <= l && r <= R) return void(tr[now] = ti);
    down(now); int mid = (l + r) >> 1;
    if(L <= mid) modify(ls, l, mid, L, R, ti);
    if(mid < R) modify(rs, mid + 1, r, L, R, ti);
}
int query(int now, int l, int r, int to)
{
    if(l == r) return tr[now];
    if(tr[now]) return tr[now];
    int mid = (l + r) >> 1;
    if(to <= mid) return query(ls, l, mid, to);
    else return query(rs, mid + 1, r, to);
}
LL sum[1000005];
inline int lb(int x) {return x & (-x);}
inline void add(int x, int val)
{
    if(!x) return;
    while(x <= m)
        sum[x] += val,
        x += lb(x);
}
inline LL get_sum(int x)
{
    if(x < 1) return 0;
    LL re = 0;
    while(x)
        re += sum[x],
        x ^= lb(x);
    return re;
}
#define pii std::pair<int, int>
#define mp std::make_pair
std::vector<pii> qst[1000005];
LL ans[1000005];
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = reads(), m = reads(), q = reads();
    FOR(i, 1, m)
    {
        ty[i] = reads();
        if(ty[i] == 1)
        {
            x[i] = reads(), y[i] = reads();
            int vx = query(1, 1, n, x[i]), vy = query(1, 1, n, y[i]);
            modify(1, 1, n, x[i], x[i], vy), modify(1, 1, n, y[i], y[i], vx);
        }
        else if(ty[i] == 2)
        {
            x[i] = reads(), y[i] = reads(), val[i] = reads();
            modify(1, 1, n, x[i], y[i], i);
        }
        else
        {
            x[i] = reads();
            y[i] = query(1, 1, n, x[i]);
        }
    }
    FOR(i, 1, q)
    {
        int l = reads(), r = reads();
        qst[r].emplace_back(mp(l, i));
    }
    FOR(i, 1, m)
    {
        if(ty[i] == 3) add(y[i], val[y[i]]);
        for(pii j : qst[i]) ans[j.second] = get_sum(i) - get_sum(j.first - 1);
    }
    FOR(i, 1, q) printf("%lld\n", ans[i]);
    return 0;
}