# G. Count the Trains

link : https://codeforces.com/contest/1690/problem/G

tóm tắt đề : đề dài vcl đíu biết tóm tắt ntn cho nó gọn nữa

cho mảng a, lập mảng b bằng cách lấy b[i] = min(a[1], a[i]), có m truy vấn, mỗi truy vấn trừ a[i] đi d đơn vị, hỏi có bao nhiêu giá trị khác nhau trong mảng b.

ý tưởng : dùng seg tree + lazy

code AC :

:::spoiler

#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define rev(i, a, b) for (int i = (a); i >= (b); --i)
#define ll long long

using namespace std;
const int mxn = 1e5 + 7;
struct node
{
    int l, r, diff;
}seg[4*mxn];
int n, m;
int laz[4*mxn], a[mxn], b[mxn];

void build(int l, int r, int p)
{
    if (l == r)
    {
        seg[p].diff = 1;
        seg[p].l = seg[p].r = b[l];
        return;
    }

    int mid = (l + r)>>1;
    int L = (p << 1), R = L + 1;
    build(l, mid, L);
    build(mid + 1, r, R);

    seg[p].diff = seg[L].diff + seg[R].diff;
    if (seg[L].r == seg[R].l) --seg[p].diff;
    seg[p].l = seg[L].l;
    seg[p].r = seg[R].r;
}

void down(int p)
{
    if (laz[p] == -1) return;
    int L = (p << 1), R = L + 1;

    seg[L].diff = 1;
    seg[L].l = seg[L].r = laz[p];
    laz[L] = laz[p];

    seg[R].diff = 1;
    seg[R].l = seg[R].r = laz[p];
    laz[R] = laz[p];

    laz[p] = -1;
}

int get(int l, int r, int p, int x)
{
    if (l == r) return seg[p].l;

    down(p);
    int mid = (l + r)>>1;
    if (x <= mid) return get(l, mid, p << 1, x);
    else return get(mid + 1, r, (p << 1) + 1, x);
}

void update(int l, int r, int L, int R, int p, int val)
{
    if (r < L || R < l) return;
    if (L <= l && r <= R)
    {
        seg[p].diff = 1;
        seg[p].l = seg[p].r = val;
        laz[p] = val;
        return;
    }

    down(p);
    int mid = (l + r)>>1;
    update(l, mid, L, R, p << 1, val);
    update(mid + 1, r, L, R, (p << 1) + 1, val);

    int Le = (p << 1), Ri = Le + 1;
    seg[p].diff = seg[Le].diff + seg[Ri].diff;
    if (seg[Le].r == seg[Ri].l) --seg[p].diff;
    seg[p].l = seg[Le].l;
    seg[p].r = seg[Ri].r;
}

int fi(int x)
{
    int l = x, r = n;
    while (l < r)
    {
        int mid = (l + r)/2 + 1;
        if (get(1, n, 1, mid) < a[x]) r = mid - 1;
        else l = mid;
    }
    return l;
}

int main(){
    //freopen("D:\\test.txt", "r", stdin);
    //freopen("D:\\test2.txt", "w", stdout);
    int t; cin >> t;
    while(t--)
    {
        scanf("%d%d", &n, &m);
        rep(i, 1, n) scanf("%d", &a[i]);

        int mi = b[1] = a[1];
        rep(i, 2, n) mi = b[i] = min(mi, a[i]);
        //rep(i, 1, n) cout << b[i] << ' '; return 0;

        build(1, n, 1);
        memset(laz, -1, sizeof(laz));

        rep(i, 1, m)
        {
            int x, d;
            scanf("%d%d", &x, &d);
            a[x] -= d;
            if (a[x] < get(1, n, 1, x))
            {
                //cout << a[x] << ' ' << get(1, n, 1, x) << "dd\n";
                update(1, n, x, fi(x), 1, a[x]);
            }

            printf("%d ", seg[1].diff);
        }
        printf("\n");
    }
}

:::

bug ngu : fill mảng laz = 0, quên là các giá trị lazy xuống cũng có thể = 0 nữa