結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2021-10-08 22:25:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 302 ms / 3,000 ms |
コード長 | 1,479 bytes |
コンパイル時間 | 2,321 ms |
コンパイル使用メモリ | 200,172 KB |
最終ジャッジ日時 | 2025-01-24 22:33:02 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <bits/stdc++.h>using namespace std;int inf = 1001001001;template <typename T>struct SegmentTree {int n;vector<T> dat;SegmentTree() {}SegmentTree(int N) {n = 1;while(n < N) {n *= 2;}dat.resize(2*n-1,{-inf,-inf});}void update(int x, long long val,int val2) {x += (n-1);dat[x].first = val;dat[x].second = val2;while(x > 0) {x = (x-1)/2;dat[x] = max(dat[2*x+1],dat[2*x+2]);}}T query(int a, int b, int k, int l, int r) {if(r <= a || b <= l) return {-inf,-inf};if(a <= l && r <= b) return dat[k];T vl = query(a, b, 2*k+1, l, (l+r)/2);T vr = query(a, b, 2*k+2, (l+r)/2, r);return max(vl, vr);}T query(int a,int b) {//[a,b)return query(a,b,0,0,n);}};int main() {long long N,M;cin >> N >> M;vector<long long>a(M);SegmentTree<pair<long long,int>>Seg(M);for(int i = 0; i < M; i++) {cin >> a[i];Seg.update(i,a[i],i);}int Q;cin >> Q;while (Q--) {long long t,x,y;cin >> t >> x >> y;x--;if(t == 1) {a[x] += y;Seg.update(x,a[x],x);}if(t == 2) {a[x] -= y;Seg.update(x,a[x],x);}if(t == 3) {cout << Seg.query(0,M).second+1 << endl;}}}