[TIOJ] 1169

氣球博覽會（2015 TOI 一模 C）

2021-03-14

TIOJ , tutorial

題敘

Link

有一個長度為 $N$ 的陣列，請 $Q$ 次支援：

單點修改
區間查詢不含某數的最長連續序列

想法

區間修改會想到線段樹或分塊，這裡採用分塊（~~其實是不知道線段樹版要怎麼寫~~）

假設 $K$ 個一塊，每次修改要重新計算當下區間的三個值：

以左界為起點的最長區間
任意條件的最長區間
以右界為終點的最長區間

就能輕鬆的合併值了，重算的複雜度是 $\mathcal{O}(K)$。

把原本的序列預處理就要 $\mathcal{O}(NK)$。

由於標示氣球種類的值域到 $2^{24}$，所以用 map 存，不存在的區間要當做可以延續 $K$ 個，合併會最多算到 $2K$ 個零散的值，$\frac{N}{K}$ 個區間，複雜度會是 $\mathcal{O}(\frac{N}{K} \log K + K)$。

總複雜度 $\mathcal{O}(NK + Q(\frac{N}{K} \log K + K))$， $K$ 不好估，但可以確定他大於 $\sqrt{N}$，取 $(4\sim 10)\sqrt{N}$ 都會過。

AC Code

 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
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#pragma pack(0)
#define ll long long
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define F first
#define S second
#define MOD 1000000007
#define MOD2 998244353
#define _INFINITY 9223372036854775807
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int arr[200005], n, q, c, size;
struct Block
{
    int l, mid, r;
};
unordered_map<int, Block> block[450];

inline void cal_block(int i, int j)
{

    int l = 0, mid = 0, tmp = 0, r = 0;
    for (int k = 0; k < size && i * size + k < n && arr[i * size + k] != j; k++)
        l++;
    for (int k = 0; k < size && i * size + k < n; k++)
        if (arr[i * size + k] != j)
            tmp++;
        else
            mid = max(mid, tmp), tmp = 0;
    mid = max(mid, tmp);
    for (int k = min(n - (i * size) - 1, size - 1); k >= 0 && arr[i * size + k] != j; k--)
        r++;

    if (l == size)
        block[i].erase(j);
    else
        block[i][j] = Block{l, mid, r};
}

signed main()
{
    fast;
    cin >> n >> q >> c;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    size = ceil(sqrt(4 * n));
    for (int i = 0; i < ((n + size - 1) / size); i++)
        for (int j = 0; j <= size && i * size + j < n; j++)
            if (block[i].find(arr[i * size + j]) == block[i].end())
                cal_block(i, arr[i * size + j]);

    for (int i = 1; i <= q; i++)
    {
        int x, a, b, c;
        cin >> x;
        if (x == 0)
        {
            cin >> a >> b;
            int p = arr[a];
            arr[a] = b;
            cal_block(a / size, p);
            cal_block(a / size, arr[a]);
        }
        else
        {
            cin >> a >> b >> c;
            int j = a, tmp = 0, val = 0;
            for (; j % size && j < b; j++)
                if (arr[j] != c)
                    tmp++;
                else
                    val = max(tmp, val), tmp = 0;
            for (; j < b - size; j += size)
            {
                auto iter = block[j / size].find(c);
                if (iter == block[j / size].end())
                    tmp += size;
                else
                {
                    val = max({tmp + iter->second.l, iter->second.mid, val});
                    tmp = iter->second.r;
                }
            }
            for (; j < b; j++)
                if (arr[j] != c)
                    tmp++;
                else
                    val = max(tmp, val), tmp = 0;
            val = max(tmp, val);
            cout << val << '\n';
        }
    }
}