verify/Datastructure_segtree.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://judge.yosupo.jp/problem/predecessor_problem

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#include "../Utility/template.hpp"
#include "../Datastructure/segtree.hpp"

using S = int;
S op(S l, S r) {
	return l + r;
}

S e() {
	return 0;
}


int main() {
	int N, Q;
	cin >> N >> Q;
	vector<int> T(N, 0);
	string t;
	cin >> t;
    rep(i, 0, N) if(t[i] == '1') {
		T[i] = 1;
	}
	segtree<S, op, e> seg(T);

	while(Q--) {
		int t, k;
		cin >> t >> k;
		if(t==0) {
			seg.set(k, 1);
		}
		else if(t==1) {
			seg.set(k, 0);
		}
		else if(t==2) {
			if(seg.get(k)) cout << 1 << '\n';
			else cout << 0 << '\n';
		}
		else if(t==3) {
			auto nex = [&](int v) {
				return v == 0;
			};
			int res = seg.max_right(k, nex);
			if(res==N) cout << -1 << '\n';
            else  cout << res << '\n';
		}
		else if(t==4) {
			auto pre = [&](int v) {
				return v == 0;
			};
			int res = seg.min_left(k+1, pre);
			cout << res-1 << '\n';
		}
	}

}

#line 1 "verify/Datastructure_segtree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/predecessor_problem"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/segtree.hpp"
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    int sz;
    vector<S> d;

    segtree(int n) : segtree(vector<S>(n, e())) {}

    segtree(const vector<S> &v) : n((int)v.size()), sz(1) {
        while(sz < n) sz <<= 1;
        d.resize(2*sz, e());
        rep(i, 0, n) {
            d[sz+i] = v[i];
        }
        rrep(i, 1, sz) d[i] = op(d[i<<1], d[i<<1|1]);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += sz;
        d[p] = x;
        while(p > 1) {
            p >>= 1;
            d[p] = op(d[p<<1], d[p<<1|1]);
        }
    }

    S get(int p) const {
        assert(0 <= p && p < n);
        return d[p + sz];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        S sml = e(), smr = e();
        l += sz;
        r += sz;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= n);
        assert(f(e()));
        if (l == n) return n;
        l += sz;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < sz) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - sz;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= n);
        assert(f(e()));
        if (r == 0) return 0;
        r += sz;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < sz) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - sz;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
    
};
/*
@brief segtree
@docs doc/segtree.md
*/
#line 4 "verify/Datastructure_segtree.test.cpp"

using S = int;
S op(S l, S r) {
	return l + r;
}

S e() {
	return 0;
}


int main() {
	int N, Q;
	cin >> N >> Q;
	vector<int> T(N, 0);
	string t;
	cin >> t;
    rep(i, 0, N) if(t[i] == '1') {
		T[i] = 1;
	}
	segtree<S, op, e> seg(T);

	while(Q--) {
		int t, k;
		cin >> t >> k;
		if(t==0) {
			seg.set(k, 1);
		}
		else if(t==1) {
			seg.set(k, 0);
		}
		else if(t==2) {
			if(seg.get(k)) cout << 1 << '\n';
			else cout << 0 << '\n';
		}
		else if(t==3) {
			auto nex = [&](int v) {
				return v == 0;
			};
			int res = seg.max_right(k, nex);
			if(res==N) cout << -1 << '\n';
            else  cout << res << '\n';
		}
		else if(t==4) {
			auto pre = [&](int v) {
				return v == 0;
			};
			int res = seg.min_left(k+1, pre);
			cout << res-1 << '\n';
		}
	}

}