ログイン
新規登録
Summer Camp Problems Selection
Permanent Contest
Home
Tasks
Clar
Submissions
Standings
提出 72cf7b18-e253-455b-8a30-1d7bab67dba6
コード
#include <bits/stdc++.h> using namespace std; int main(){ long long N,n = 1; int Q; cin >> N; while(n < N) n *= 2; vector<long long> seg(n*2,0); for(int i = 0;i < N;i++){ cin >> seg[i+n]; } cin >> Q; for(int i = n-1;i > 0;i--) seg[i] = seg[i*2]+seg[i*2+1]; for(int i = 0;i < Q;i++){ int query; cin >> query; if(query == 2){ int l,r; cin >> l >> r; l += (n-1),r += (n-1); long long ans = 0; cerr << "l:" << l << ",r:" << r << ",ans:" << ans << endl; while(l != r && l < r){ if(l % 2 == 1){ ans += seg[l]; l++; } if(r % 2 == 1){ r--; ans += seg[r]; } l /= 2; r /= 2; cerr << "l:" << l << ",r:" << r << ",ans:" << ans << endl; } cout << ans << endl; } else{ int pos,x; cin >> pos >> x; pos += (n-1); seg[pos] = x; while(pos != 0){ pos /= 2; seg[pos] = seg[pos*2] + seg[pos*2+1]; } } } }
結果
問題
点数
言語
結果
実行時間
メモリ
SegTree - segment tree
100
C++
AC
82 ms
3864 KiB