[ABC380E] 1D Bucket Tool

维护序列的全相等联通块，感觉是个很常见的东西，确实做法很多，set，dsu 都可以，

原谅我只想到复杂度更劣的 线段树 + 二分 qwq

一眼看上去，是个很可以用线段树维护的 ds 题。

区间修改很简单，

主要是如何维护，给定一个位置，找该位置的颜色的最大连通块，还要是 \log 级别的时间。

一开始是想倍增跳，但是发现不好维护 连续相同。

最后只能是从线段树直接维护的角度想，注意到，找连通块的左右界，是可以二分的。

这是显然的，可以简单考虑为区间长度越长，越更可能 不连续相同，也就是说如果长度更短的区间都不能连续，那么更长的不可能更优。

然后考虑区间连续相同是不是等价于 \bigcap\limits_{i = l}^r a_i = a_k~(k\in[l, r]) 呢？然后 wa 了一大堆。。。

赛后发现随便举出反例 10 & 11 & 10 = 10

其实是可以直接维护这个逻辑的，，，子区间相同或否，pushup 维护一个标志值就可以了。

最后区间查询，发现数据范围比较小，直接开个颜色的桶就可以了。

复杂度 O(q\log^2n)

#include <bits/stdc++.h>
#define re register int 
#define lp p * 2
#define rp p * 2 + 1
#define int long long

using namespace std;
typedef pair<int, int> PII;
const int N = 5e5 + 10;

struct Tree { int l, r, sum, tag, flag; } t[N << 2];
int n, q, num[N];

inline void push_up(int p)
{
    t[p].sum = t[lp].sum + t[rp].sum;
    t[p].flag = ((t[lp].flag == t[rp].flag && t[lp].flag) ? t[lp].flag : 0); // 维护一个区间是否全相等的标志
}

inline void push_down(int p)
{
    if (t[p].tag)
    {
        t[lp].sum = (t[lp].r - t[lp].l + 1) * t[p].tag;
        t[rp].sum = (t[rp].r - t[rp].l + 1) * t[p].tag;
        t[lp].flag = t[rp].flag = t[p].tag;
        t[lp].tag = t[p].tag;
        t[rp].tag = t[p].tag;
        t[p].tag = 0;
    }
}

inline void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;
    if (l == r)
    {
        t[p].sum = t[p].flag = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(lp, l, mid); build(rp, mid + 1, r);
    push_up(p);
}

inline void update(int p, int l, int r, int k)
{
    if (l <= t[p].l && t[p].r <= r)
    {
        t[p].sum = (t[p].r - t[p].l + 1) * k;
        t[p].flag = k;
        t[p].tag = k;
        return;
    }
    push_down(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) update(lp, l, r, k);
    if (r > mid) update(rp, l, r, k);
    push_up(p);
}

inline int query(int p, int l, int r)
{
    if (l <= t[p].l && t[p].r <= r) return t[p].sum;
    push_down(p);
    int res = 0;
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) res += query(lp, l, r);
    if (r > mid) res += query(rp, l, r);

    return res;
}

inline bool ask(int p, int l, int r, int k)
{
    if (l <= t[p].l && t[p].r <= r)
    {
        if (t[p].flag != k) return false;
        return true;
    }
    push_down(p);
    bool res = true;
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) res &= ask(lp, l, r, k);
    if (r >mid) res &= ask(rp, l, r, k);

    return res;
}

inline PII search(int x)
{
    int a = query(1, x, x); 
    int L, R;

    int l = 1, r = x;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (ask(1, mid, x, a)) r = mid; 
        else l = mid + 1;
    }
    L = l;

    l = x, r = n;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (ask(1, x, mid, a)) l = mid;
        else r = mid - 1;
    }
    R = l;

    return {L, R};
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;
    build(1, 1, n); 
    for (re i = 1; i <= n; i ++) num[i] = 1;

    while (q --)
    {
        int op, x, y; cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            PII k = search(x); int l = k.first, r = k.second;

            num[query(1, x, x)] -= (r - l + 1);
            update(1, l, r, y); 
            num[y] += (r - l + 1);

        }
        else 
        {
            cin >> x;
            cout << num[x] << '\n';
        }
    }

    return 0;
}