DDOSvoid's Blog

Uoj 515 【UR-19】前进四

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

题目描述

https://uoj.ac/problem/515

简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次操作，操作有两种：单点修改、查询 $a_x,\cdots,a_n$ 的不同的后缀最小值的个数

$n,m\le 10^6$

Solution

注意到查询不是区间而是一个后缀，这启示我们离线后扫描线，我们用线段树维护以时间为下标，值为后缀最小值的线段树，注意到每次查询的答案即为这个时间后缀最小值变化的次数

我们考察最基本的Segment tree Beats的做法，容易发现我们可以在维护的时候顺便维护每个位置的值的变化次数

时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <vector>
#include <tuple>
#define maxn 1000010
#define INF 1000000010
using namespace std;

struct IO {
    inline char read() {
        static const int Len = 1 << 20 | 1;
        static char buf[Len], *s, *t;
        return (s == t) && (t = (s = buf) + fread(buf, 1, Len, stdin)), s == t ? -1 : *s++;
    }
    template <typename type> inline IO& operator >> (type& x){
        static char c, boo;
        for (c = read(), boo = 0; !isdigit(c); c = read()) {
            if (c == -1) return *this;
            boo |= c == '-';
        }
        for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
        boo && (x=-x); return *this;
    }
} din;

int n, m, p[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int mx, smx, v;
} T[maxn * 4]; 
inline void maintain(int i) {
    T[i].mx = max(T[lc].mx, T[rc].mx); 
    if (T[lc].mx > T[rc].mx) T[i].smx = max(T[lc].smx, T[rc].mx);
    else if (T[rc].mx > T[lc].mx) T[i].smx = max(T[lc].mx, T[rc].smx);
    else T[i].smx = max(T[lc].smx, T[rc].smx); 
}

void build(int i, int l, int r) {
    if (l == r) return T[i] = { INF, -INF, 0 }, void(); 
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i); 
}

inline void Update(int i, int mx, int v) { T[i].mx = mx; T[i].v += v; }

inline void pushdown(int i) {
    int mx = T[i].mx, &v = T[i].v;
    if (T[lc].mx > mx) Update(lc, mx, v);
    if (T[rc].mx > mx) Update(rc, mx, v);
    v = 0; 
}

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L || T[i].mx <= v) return ;
    if (L <= l && r <= R && T[i].smx < v) return Update(i, v, 1);
    int m = l + r >> 1; pushdown(i); 
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i); 
}

int query(int i, int l, int r, int k) {
    if (l == r) return T[i].v;
    int m = l + r >> 1; pushdown(i);
    if (k <= m) return query(lc, l, m, k);
    else return query(rc, m + 1, r, k); 
}


struct Query {
    int l, r, v, k;
} Q[maxn * 2]; int cnt, ans[maxn], cans;
vector<tuple<int, int, int>> A[maxn];
vector<pair<int, int>> B[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    din >> n >> m;
    for (int i = 1, x; i <= n; ++i) din >> x, p[i] = ++cnt, Q[cnt] = { 0, 0, x, i };
    for (int i = 1; i <= m; ++i) {
        int opt, x, y; din >> opt;
        if (opt == 1) {
            din >> x >> y;
            Q[p[x]].r = i - 1;
            p[x] = ++cnt; Q[cnt] = { i, 0, y, x };
        } else {
            din >> x;
            B[x].emplace_back(i, ++cans); 
        }
    } build(1, 0, m); 
    for (int i = 1; i <= cnt; ++i) {
        if (!Q[i].r) Q[i].r = m;
        A[Q[i].k].emplace_back(Q[i].l, Q[i].r, Q[i].v);
    }
    for (int i = n; i; --i) {
        for (auto [l, r, v] : A[i]) update(1, 0, m, l, r, v);
        for (auto [k, id] : B[i]) ans[id] = query(1, 0, m, k); 
    }
    for (int i = 1; i <= cans; ++i) cout << ans[i] << "\n";
    return 0;
}