P5524 [Ynoi2012] NOIP2015 充满了希望 Solution

Description

有一序列 $a$，长度为 $n$。
还有一个长度为 $m$ 的操作序列 $b$，每个操作形如：

• $\mathrm{swap}(x,y)$：交换 $a_x$ 和 $a_y$.
• $\mathrm{assign}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow v$.
• $\mathrm{get}(p)$：求 $a_p$ 的值.

现在有 $q$ 个查询，每次给定一个二元组 $(L,R)$，执行下面操作：

• 将 $a$ 每一项设为 $0$.
• 执行操作 $b_L,b_{L+1},\cdots ,b_R$.
• 输出所有 $\mathrm{get}$ 操作的答案之和.

Limitations

$1\le n,m,q\le 10^6$
$1\le k\le 10^9$
$1\le x,y\le n$
$1\le l\le r\le n$
$1\le L\le R\le m$
$1\text{s},512\text{MB}$

Solution

使用线段树维护区间最后一次 $\mathrm{assign}$ 的时刻，遇到 $\mathrm{get}$ 时，查询 $p$ 点的值并记为 $t_i$.

考虑将询问挂在 $r$ 上做扫描线，遇到 $\mathrm{get}$ 时，在 $t_i$ 位置加上第 $t_i$ 次操作的 $k$，对每个询问查询 $[l,r]$ 的和，可以用树状数组.

然后卡卡常数，需要用快读.

Code

$4.52\text{KB},4.07\text{s},119.21\text{MB}\text{(in total, C++ 20 with O2)}$

// Problem: P5524 [Ynoi2012] NOIP2015 充满了希望
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5524
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

#ifdef LOCAL
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif

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

template<class T>
inline void write(T x) {
    if (x < 0) {
        putchar_unlocked('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar_unlocked(x % 10 + '0');
    return;
}

inline int lowbit(int x){
	return x & -x;
}

template<class T>
struct fenwick{
	int n;
	vector<T> c;
	
	inline fenwick() {}
	inline fenwick(int _n): n(_n){
		c.resize(n + 1);
	}
	
	inline fenwick(const vector<T> &a): n(a.size()){
		c.resize(n + 1);
		for(int i = 1; i <= n; i++){
			c[i] = c[i] + a[i - 1];
			int j = i + lowbit(i);
			if(j <= n) c[j] = c[j] + c[i];
		}
	}
	
	inline void add(int x, const T& v){
		for(int i = x + 1; i <= n; i += lowbit(i)) c[i] = c[i] + v;
	}
	
	inline T ask(int x){
		T ans{};
		for(int i = x + 1; i; i -= lowbit(i)) ans = ans + c[i];
		return ans;
	}
	
	inline T ask(int l, int r){
		return ask(r) - ask(l - 1);
	}
};

inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }

struct SegTree {
    struct Node {
        int l, r, tag;
    };
    vector<Node> tr;
    
    inline SegTree() {}
    inline SegTree(int n) {
        tr.resize(n << 2);
        build(0, 0, n - 1);
    }
    
    inline void pushdown(int u) {
        if (tr[u].tag != -1) {
            tr[ls(u)].tag = tr[rs(u)].tag = tr[u].tag;
            tr[u].tag = -1;
        }
    }
    
    inline void build(int u, int l, int r) {
        tr[u].l = l;
        tr[u].r = r;
        tr[u].tag = -1;
        if (l == r) return;
        
        const int mid = (l + r) >> 1;
        build(ls(u), l, mid);
        build(rs(u), mid + 1, r);
    }
    
    inline void assign(int u, int l, int r, int x) {
        if (l <= tr[u].l && tr[u].r <= r) {
            tr[u].tag = x;
            return;
        }
        const int mid = (tr[u].l + tr[u].r) >> 1;
        pushdown(u);
        if (l <= mid) assign(ls(u), l, r, x);
        if (r > mid) assign(rs(u), l, r, x);
    }
    
    inline int get(int u, int p) {
        if (tr[u].l == tr[u].r || tr[u].tag != -1) return tr[u].tag;
        const int mid = (tr[u].l + tr[u].r) >> 1;
        if (p <= mid) return get(ls(u), p);
        else return get(rs(u), p);
    }
};

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	const int n = read<int>(), m = read<int>(), q = read<int>();
	vector<int> op(m), x(m), y(m), val(m);
	SegTree sgt(n);
	
	for (int i = 0; i < m; i++) {
	    op[i] = read<int>();
	    if (op[i] == 1) {
	        x[i] = read<int>(), y[i] = read<int>();
	        x[i]--, y[i]--;
	        
	        int a = sgt.get(0, x[i]), b = sgt.get(0, y[i]);
	        sgt.assign(0, x[i], x[i], b);
	        sgt.assign(0, y[i], y[i], a);
	    }
	    else if (op[i] == 2) {
	        x[i] = read<int>(), y[i] = read<int>(), val[i] = read<int>();
	        x[i]--, y[i]--;
	        sgt.assign(0, x[i], y[i], i);
	    }
	    else {
	        x[i] = read<int>(), x[i]--;
	        y[i] = sgt.get(0, x[i]);
	    }
	}
	
	fenwick<i64> fwk(m);
	vector<vector<pair<int, int>>> queries(m);
	vector<i64> ans(q);
	for (int i = 0, l, r; i < q; i++) {
	    l = read<int>(), r = read<int>();
	    l--, r--;
	    queries[r].emplace_back(l, i);
	}
	
	for (int i = 0; i < m; i++) {
	    if (op[i] == 3 && y[i] != -1) fwk.add(y[i], val[y[i]]);
	    for (auto [pos, id] : queries[i]) ans[id] = fwk.ask(pos, i);
	}
	
	for (const auto& i : ans) {
	    write(i);
	    putchar_unlocked('\n');
	}
	return 0;
}