題敘

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

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

想法

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

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

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

就能輕鬆的合併值了，
重算的複雜度是$\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

#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';
        }
    }
}