P5524 [Ynoi2012] NOIP2015 充满了希望

· · 题解

最简单的 Ynoi？

思路：

先考虑没有交换操作时怎么做。

显然由于是区间覆盖，那么查询一个位置 x 的值的时候，我们应该找到它前面最晚覆盖它的那次操作，记作 pre_x，覆盖值是 v；那么可以看作权值为 v 的二元组 (tim, pre_x)。

那么询问一次执行 [l, r] 的操作后所有询问的和，等价于求所有满足 l \le pre_x < tim \le r 的二元组的权值的和；可以直接离线后二维数点解决。

那如果有交换操作呢？你发现本质上就是交换一下 pre_x, pre_y，后续操作要么还是交换要么就是覆盖，完全没有啥影响。

于是用线段树维护区间最大值（赋值），方便查询 pre_x；时间复杂度为 O(n \log n)。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define lowbit(x) x & (-x)
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1e6 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int n, m, q, op, x, y, l, r;
int id[N];
ll ans[N];
vector<pair<int, int>> E[N];
vector<pair<int, int>> Q[N];
struct Node{
    int l, r;
    int mx, tag;
}X[N << 2];
inline void chkmx(int k, int v){
    X[k].mx = v;
    X[k].tag = v;
}
inline void push_down(int k){
    if(X[k].tag){
        chkmx(k << 1, X[k].tag);
        chkmx(k << 1 | 1, X[k].tag);
        X[k].tag = 0;
    }
}
inline void build(int k, int l, int r){
    X[k].l = l, X[k].r = r;
    if(l == r)
      return ;
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
}
inline void update(int k, int l, int r, int v){
    if(X[k].l == l && r == X[k].r){
        chkmx(k, v);
        return ;
    }
    push_down(k);
    int mid = (X[k].l + X[k].r) >> 1;
    if(r <= mid)
      update(k << 1, l, r, v);
    else if(l > mid)
      update(k << 1 | 1, l, r, v);
    else{
        update(k << 1, l, mid, v);
        update(k << 1 | 1, mid + 1, r, v);
    }
}
inline int ask(int k, int i){
    if(X[k].l == i && i == X[k].r)
      return X[k].mx;
    push_down(k);
    int mid = (X[k].l + X[k].r) >> 1;
    if(i <= mid)
      return ask(k << 1, i);
    else
      return ask(k << 1 | 1, i);
}
namespace BIT{
    ll a[N];
    inline void add(int x, int v){
        for(int i = x; i <= m; i += lowbit(i))
          a[i] += v;
    }
    inline ll ask(int x){
        ll sum = 0;
        for(int i = x; i; i -= lowbit(i))
          sum += a[i];
        return sum;
    }
};
int main() {
    n = read(), m = read(), q = read();
    build(1, 1, n);
    for(int i = 1; i <= m; ++i){
        op = read();
        if(op == 2){
            l = read(), r = read(), x = read();
            id[i] = x;
            update(1, l, r, i);
        }
        else if(op == 1){
            x = read(), y = read();
            int a = ask(1, x), b = ask(1, y);
            update(1, x, x, b);
            update(1, y, y, a);
        }
        else{
            x = read();
            int a = ask(1, x);
            if(a)
              E[i].push_back({a, id[a]});
        }
    }
    for(int i = 1; i <= q; ++i){
        l = read(), r = read();
        Q[r].push_back({l, i});
    }
    for(int i = 1; i <= m; ++i){
        for(auto t : E[i])
          BIT::add(t.fi, t.se);
        for(auto t : Q[i])
          ans[t.se] = BIT::ask(i) - BIT::ask(t.fi - 1);
    }
    for(int i = 1; i <= q; ++i){
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}