DDOSvoid's Blog

Luogu U71972 鸽子的序列

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

题目描述

https://www.luogu.com.cn/problem/U71972

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，操作分两种，每次操作给定三个整数 $l,r,k$，第一种操作是将给定 $[l,r]$ 的数字都置为 $k$，第二种是查询区间 $[l,r]$ 的第 $k$ 小数

$n,m\le 10^5,1\le a_i,k\le 10^9$

Solution

首先我们考虑整体二分，类比单点修改，区间查询第 $k$ 小的做法

那么我们现在的问题是，不能暴力修改区间 $[l,r]$，但是注意到修改操作只有区间覆盖，那么我们知道区间总连续段的个数是 $O(n)$ 的，因为每次覆盖都至多会使连续段的个数增加 $2$，我们用线段树维护这个东西，注意到每一个连续段的势都是 $O(\log n)$ 的，所以总的时间复杂度依然是 $O(n\log n)$

那么我们用线段树维护，每次把连续段都拿出来做当做一次区间修改扔到操作里，注意这里我们线段树会把一个连续段分成 $O(\log n)$ 个，所以我们还需要手动合并一次，然后我们带着这些操作做整体二分即可

时间复杂度 $O(n\log^2 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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#define maxn 100010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m, a[maxn];

struct Query {
    int opt, l, r, k, id; // 0 for query, -1 for del, 1 for add
} Q[maxn * 10], t1[maxn * 10], t2[maxn * 10]; int num;

int b[maxn * 10], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[++cnt] = a[i];
    for (int i = 1; i <= num; ++i) if (Q[i].opt) b[++cnt] = Q[i].k;
    sort(b + 1, b + cnt + 1); cnt = unique(b + 1, b + cnt + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
    for (int i = 1; i <= num; ++i)
        if (Q[i].opt) Q[i].k = lower_bound(b + 1, b + cnt + 1, Q[i].k) - b;
}

struct Fenwick {
    int B1[maxn], B2[maxn], s[maxn];
    void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i))
            B1[i] += v, B2[i] += x * v;
    }

    int get_sum(int x) {
        int s = 0;
        for (int i = x; i; i -= lowbit(i))
            s += (x + 1) * B1[i], s -= B2[i];
        return s; 
    }

    void update(int l, int r, int v) { add(l, v); add(r + 1, -v); }

    int query(int l, int r) { return s[r] - s[l - 1] + get_sum(r) - get_sum(l - 1); } 
} Bit;

#define lc i << 1
#define rc i << 1 | 1
struct Segment {
    int v, tag;
} T[maxn * 4]; 
inline void maintain(int i) { T[i].v = T[lc].v == T[rc].v ? T[lc].v : 0; }

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

inline void pushdown(int i) {
    int &tag = T[i].tag; if (!tag) return ;
    T[lc].v = T[lc].tag = T[rc].v = T[rc].tag = tag;
    tag = 0; 
}

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

int ans[maxn], cans;
void solve(int l, int r, int L, int R) {
    if (L > R) return ;
    if (l == r) {
        for (int i = L; i <= R; ++i)
            if (!Q[i].opt) ans[Q[i].id] = b[l];
        return ;
    }
    int m = l + r >> 1, c1 = 0, c2 = 0;
    for (int i = L; i <= R; ++i) {
        int opt = Q[i].opt, l = Q[i].l, r = Q[i].r, k = Q[i].k;
        if (opt) {
            if (k <= m) Bit.update(l, r, opt), t1[++c1] = Q[i];
            else t2[++c2] = Q[i];
        }
        else {
            int v = Bit.query(l, r);
            if (k <= v) t1[++c1] = Q[i];
            else Q[i].k -= v, t2[++c2] = Q[i];
        }
    }
    for (int i = L; i <= R; ++i)
        if (Q[i].opt && Q[i].k <= m) Bit.update(Q[i].l, Q[i].r, -Q[i].opt);
    for (int i = 1; i <= c1; ++i) Q[L + i - 1] = t1[i];
    for (int i = 1; i <= c2; ++i) Q[L + c1 + i - 1] = t2[i];
    solve(l, m, L, L + c1 - 1); solve(m + 1, r, L + c1, R); 
    
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], Q[++num] = { 1, i, i, a[i], 0 };
    build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        int opt, l, r, k; cin >> opt >> l >> r >> k;
        if (opt == 2) {
            if (k > r - l + 1) ans[++cans] = 0;
            else Q[++num] = { 0, l, r, k, ++cans };
        }
        else {
            vector<tuple<int, int, int>> A, B;
            update(1, 1, n, l, r, k, B);
            for (int i = 0, p = 0; i < B.size(); i = p) {
                while (p < B.size() && get<2>(B[i]) == get<2>(B[p])) ++p;
                A.emplace_back(get<0>(B[i]), get<1>(B[p - 1]), get<2>(B[i]));
            }
            for (auto [l, r, k] : A) Q[++num] = { -1, l, r, k, 0};
            Q[++num] = { 1, l, r, k, 0 };
        }
    } init_hash(); solve(1, cnt, 1, num); 
    for (int i = 1; i <= cans; ++i)
        if (ans[i]) cout << ans[i] << "\n";
        else cout << "INF" << "\n";
    return 0;
}