DDOSvoid's Blog

Luogu P2496 [SDOI2012]体育课

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

题目描述

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

简要题意：给定 $n$ 个数 $a_i$，现在有 $m$ 个操作，操作有三种，第一种是区间查询最大值，第二种是交换两个数的位置，第三种是区间加等差数列

$n,m\le 10^5$

Solution

我们分块维护这个东西，对于区间加等差数列，我们将每个点看做 $a_i+d_{bl_i}\times i+add_{bl_i}$，其中 $bl_i$ 表示这个点所属块，容易发现对于一个块，可以 $O(\sqrt n)$ 修改，我们考虑如何维护区间最值

我们将每个点的式子写出来 $t=a_i+d\times i$，我们移项得到 $a_i=(-d)\times i+t$，我们令 $y=a_i,k=-d,x=i,b=t$ 我们需要求 $t$ 最大，现在我们已知 $x$ 和 $y$，那么我们直接考虑每个块内维护上凸壳，那么这样看起来对于一个快我们的询问是 $O(\log n)$ 的，我们考虑这样优化，注意到区间加等差数列的值永远是正的，那么容易得到每个区间的斜率是递减的，也就是说取值最大的点是向右的，我们维护这么一个指针即可

每次区间加和二操作，我们直接重构块即可

时间复杂度 $O(n\sqrt 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
#include <iostream>
#include <cmath>
#include <vector>
#define maxn 100010
#define maxs 400
#define ll long long
using namespace std;

int n, m;

int blo, num, l[maxs], r[maxs], bl[maxn], p[maxs];
ll a[maxn], d[maxs], add[maxs]; vector<int> S[maxs];
void init_blo(int n) {
    blo = sqrt(n); num = (n + blo - 1) / blo;
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
    for (int i = 1; i <= num; ++i) {
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo;
    } r[num] = n; 
}

#define top S[k].back()
#define dtop S[k][S[k].size() - 2]
#define ind(i) S[i][p[i]]
#define nxt(i) S[i][p[i] + 1]
void maintain(int k) {
    while (p[k] < S[k].size() - 1 && a[ind(k)] + d[k] * ind(k) <= a[nxt(k)] + d[k] * nxt(k)) ++p[k];
}

void rebuild(int k) {
    for (int i = l[k]; i <= r[k]; ++i) a[i] += i * d[k] + add[k]; 
    S[k].clear(); add[k] = d[k] = p[k] = 0; 
    for (int i = l[k]; i <= r[k]; ++i) {
        while (S[k].size() > 1 &&
               (a[i] - a[top]) * (top - dtop) >= (a[top] - a[dtop]) * (i - top)) S[k].pop_back();
        S[k].push_back(i);
    } maintain(k); 
}

void update(int L, int R, ll v) {
    int Bl = bl[L], Br = bl[R];
    if (Bl == Br) {
        for (int i = L; i <= R; ++i) a[i] += (i - L + 1) * v;
        return rebuild(Bl); 
    } 
    for (int i = L; i <= r[Bl]; ++i) a[i] += (i - L + 1) * v; rebuild(Bl); 
    for (int i = Bl + 1; i < Br; ++i) {
        add[i] += (1 - L) * v, d[i] += v;
        maintain(i); 
    }
    for (int i = l[Br]; i <= R; ++i) a[i] += (i - L + 1) * v; rebuild(Br); 
}

ll query(int L, int R) {
    int Bl = bl[L], Br = bl[R]; ll ans = a[1] + d[1] + add[1];
    if (Bl == Br) {
        for (int i = L; i <= R; ++i) ans = max(ans, a[i] + i * d[Bl] + add[Bl]);
        return ans - (a[1] + d[1] + add[1]); 
    }
    for (int i = L; i <= r[Bl]; ++i) ans = max(ans, a[i] + i * d[Bl] + add[Bl]);
    for (int i = Bl + 1; i < Br; ++i) ans = max(ans, a[ind(i)] + ind(i) * d[i] + add[i]);
    for (int i = l[Br]; i <= R; ++i) ans = max(ans, a[i] + i * d[Br] + add[Br]);
    return ans - (a[1] + d[1] + add[1]); 
}

inline void solve_1() {
    int x, y; cin >> x >> y;
    cout << query(x, y) << "\n";
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    ll dx = x * d[bl[x]] + add[bl[x]], dy = y * d[bl[y]] + add[bl[y]];
    ll ax = a[x], ay = a[y]; 
    a[x] += (ay - ax) + (dy - dx);
    a[y] += (ax - ay) + (dx - dy);
    rebuild(bl[x]); if (bl[y] != bl[x]) rebuild(bl[y]); 
}

inline void solve_3() {
    int x, y, z; cin >> x >> y >> z;
    update(x, y, z); 
}

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

    cin >> n >> m; init_blo(n); 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= num; ++i) rebuild(i); 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        case 3 : solve_3(); break;
        }
    }
    return 0;
}