結果

問題 No.469 区間加算と一致検索の問題
コンテスト
ユーザー tiger2005
提出日時 2026-05-27 01:12:44
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,727 ms / 5,000 ms
コード長 1,348 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,043 ms
コンパイル使用メモリ 343,736 KB
実行使用メモリ 214,272 KB
最終ジャッジ日時 2026-05-27 01:13:31
合計ジャッジ時間 34,630 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int n, q, len;

int tr[(1 << 22) + 10];
int a[(1 << 20) + 10];

int ID = 0;
map<pair<int, int>, int> mp[22];

int bul(int dep, int x, int l, int r) {
  if (l == r) {
    return 0;
  }
  int m = (l + r) >> 1;
  int L = bul(dep + 1, x << 1, l, m);
  int R = bul(dep + 1, x << 1 | 1, m + 1, r);

  int &res = mp[dep][{L, R}];
  if (res == 0)
    res = ++ ID;
  return tr[x] = res;
}

int add(int dep, int x, int l, int r, int p, int k) {
  if (l == r) {
    a[l] += k;
    return tr[x] = a[l];
  }

  int m = (l + r) >> 1;
  int L = tr[x << 1], R = tr[x << 1 | 1];
  if (p <= m)
    L = add(dep + 1, x << 1, l, m, p, k);
  else
    R = add(dep + 1, x << 1 | 1, m + 1, r, p, k);

  int &res = mp[dep][{L, R}];
  if (res == 0)
    res = ++ ID;
  return tr[x] = res;
}

int main() {
  scanf("%d%d", &n, &q);
  len = 1;
  while (len < n)
    len <<= 1;

  map<int, int> ans;
  int cur = bul(0, 1, 0, len - 1);
  ans[cur] = 0;

  for (int id = 1; id <= q; id ++) {
    char op;
    scanf(" %c", &op);
    if (op == '!') {
      int l, r, x;
      scanf("%d%d%d", &l, &r, &x);
      cur = add(0, 1, 0, len - 1, l, x);
      if (r != n)
        cur = add(0, 1, 0, len - 1, r, -x);
      if (ans.find(cur) == ans.end())
        ans[cur] = id;
    } else {
      printf("%d\n", ans[cur]);
    }
  }
  return 0;
}
0