TIOJ 2174：序列操作問題

TIOJ 2174：序列操作問題

題目大意：有大小為 $n$ 的陣列，每次有兩種操作，第一種是將陣列區間 $[l,r]$ 的值改變 $x$，第二種是問陣列第 $x$ 個數字從開始操作到現在，有多久是 $0$。

解法：可開一個線段數，存區間最小值、最小值個數與懶標，先把輸入都存好，之後由左向右掃過去。如果是第一種操作，代表位置 $[l,r]$ 從時間 $t$ 開始都增加 $x$，則在 $l$ 存 $(t,x)$，在 $r+1$ 存 $(t,-x)$；如果是第二種操作，則是詢問時間 $[1,t-1]$ 有多少 $0$。所以區間加值與區間查詢還有把懶標推推拉拉即可解決這題。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 3e5 + 5;

struct Data {
    int mn, cnt, lazy;
} seg[4 * SIZE];

int n, q;
int ans[SIZE];
// add (time, x), ask (time)
vector<pair<int, int>> add[SIZE];
vector<int> ask[SIZE];

void Push (int pos, int l, int r) {
    seg[pos].mn += seg[pos].lazy;
    if (l < r) {
        seg[lpos].lazy += seg[pos].lazy;
        seg[rpos].lazy += seg[pos].lazy;
    }
    seg[pos].lazy = 0;
}

void Pull (int pos, int l, int r) {
    int mid = (l + r) / 2;
    Push (lpos, l, mid);
    Push (rpos, mid + 1, r);
    seg[pos].mn = min (seg[lpos].mn, seg[rpos].mn);
    seg[pos].cnt = (seg[lpos].mn == seg[pos].mn ? seg[lpos].cnt : 0) + (seg[rpos].mn == seg[pos].mn ? seg[rpos].cnt : 0);
}

void build (int pos, int l, int r) {
    if (l == r) {
        seg[pos] = {0, 1, 0};
    } else {
        int mid = (l + r) / 2;
        build (lpos, l, mid);
        build (rpos, mid + 1, r);
        Pull (pos, l, r);
    }
}

void update (int pos, int l, int r, int L, int R, int x) {
    if (l == L && r == R) {
        seg[pos].lazy += x;
        return;
    }
    Push (pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) {
        update (lpos, l, r, L, mid, x);
    } else if (l > mid) {
        update (rpos, l, r, mid + 1, R, x);
    } else {
        update (lpos, l, mid, L, mid, x);
        update (rpos, mid + 1, r, mid + 1, R, x);
    }
    Pull (pos, L, R);
}

int query (int pos, int l, int r, int L, int R) {
    Push (pos, L, R);
    if (seg[pos].mn) {
        return 0;
    }
    if (l == L && r == R) {
        return seg[pos].cnt;
    }
    int mid = (L + R) / 2;
    if (r <= mid) {
        return query (lpos, l, r, L, mid);
    }
    if (l > mid) {
        return query (rpos, l, r, mid + 1, R);
    }
    return query (lpos, l, mid, L, mid) + query (rpos, mid + 1, r, mid + 1, R);
}

void solve() {
    cin >> n >> q;
    FOR (i, 1, q) {
        ans[i] = -1;
        int ty;
        cin >> ty;
        if (ty == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            l++, r++;
            add[l].pb (i, x);
            add[r + 1].pb (i, -x);
        } else {
            int x;
            cin >> x;
            ask[++x].pb (i);
        }
    }
    build (1, 1, q);
    FOR (i, 1, n) {
        for (auto [t, x] : add[i]) {
            update (1, t, q, 1, q, x);
        }
        for (int t : ask[i]) {
            ans[t] = t == 1 ? 0 : query (1, 1, t - 1, 1, q);
        }
    }
    FOR (i, 1, q) {
        if (ans[i] != -1) {
            cout << ans[i] << '\n';
        }
    }
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！