結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2021-10-21 18:53:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 209 ms / 3,000 ms |
コード長 | 3,527 bytes |
コンパイル時間 | 2,026 ms |
コンパイル使用メモリ | 200,412 KB |
最終ジャッジ日時 | 2025-01-25 02:28:27 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include "bits/stdc++.h"#define int long longusing namespace std;using ll = long long;using P = pair<ll, ll>;const ll INF = (1LL << 61);ll mod = 1000000007;/* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体set(int i, T x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)update(i,x): i 番目の要素を x に更新。O(log(n))query(a,b): [a,b) での最小の要素を取得。O(log(n))find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))*/template <typename T>struct RMQ {const T e = numeric_limits<T>::max();function<T(T, T)> fx = [](T x1, T x2) -> T { return min(x1, x2); };int n;vector<T> dat;RMQ(int n_) : n(), dat(n_ * 4, e) {int x = 1;while (n_ > x) {x *= 2;}n = x;}void set(int i, T x) { dat[i + n - 1] = x; }void build() {for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);}void update(int i, T x) {i += n - 1;dat[i] = x;while (i > 0) {i = (i - 1) / 2; // parentdat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);}}// the minimum element of [a,b)T query(int a, int b) { return query_sub(a, b, 0, 0, n); }T query_sub(int a, int b, int k, int l, int r) {if (r <= a || b <= l) {return e;}else if (a <= l && r <= b) {return dat[k];}else {T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);return fx(vl, vr);}}int find_rightest(int a, int b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }int find_leftest(int a, int b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }int find_rightest_sub(int a, int b, T x, int k, int l, int r) {if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1return a - 1;}else if (k >= n - 1) { // 自分が葉ならその位置をreturnreturn (k - (n - 1));}else {int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturnreturn vr;}else { // 左の部分木を見て値をreturnreturn find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);}}}int find_leftest_sub(int a, int b, T x, int k, int l, int r) {if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn breturn b;}else if (k >= n - 1) { // 自分が葉ならその位置をreturnreturn (k - (n - 1));}else {int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);if (vl != b) { // 左の部分木を見て b 以外ならreturnreturn vl;}else { // 右の部分木を見て値をreturnreturn find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);}}}};signed main() {ios::sync_with_stdio(false);cin.tie(0);int N, M; cin >> N >> M;RMQ<int>rmq(M);for (int i = 0; i < M; i++) {int a; cin >> a;rmq.update(i, -a);}int Q; cin >> Q;for (int i = 0; i < Q; i++) {int T, X, Y; cin >> T >> X >> Y; X--;if (T == 1) {int now = rmq.query(X, X + 1);rmq.update(X, now - Y);}else if (T == 2) {int now = rmq.query(X, X + 1);rmq.update(X, now + Y);}else {int now = rmq.query(0, M);cout << rmq.find_rightest(0, M, now) + 1 << endl;}}return 0;}