結果
問題 | No.776 A Simple RMQ Problem |
ユーザー |
![]() |
提出日時 | 2018-12-23 20:01:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 301 ms / 3,000 ms |
コード長 | 3,412 bytes |
コンパイル時間 | 1,779 ms |
コンパイル使用メモリ | 176,848 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2024-09-25 10:37:21 |
合計ジャッジ時間 | 8,087 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#define fst(t) std::get<0>(t)#define snd(t) std::get<1>(t)#define thd(t) std::get<2>(t)#define fth(t) std::get<3>(t)#define unless(p) if(!(p))#define until(p) while(!(p))using ll = long long;using P = std::tuple<int,int>;const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};constexpr ll INF = 1001001001001001001;int N, Q;struct SegmentTree{struct Node{ll sum, leftSum, rightSum, max;};int numLeaf;std::vector<Node> data;SegmentTree(int n){numLeaf = 1;while(numLeaf < n){numLeaf *= 2;}data.assign(numLeaf * 2, {0, 0, 0, -INF});}Node merge(Node n1, Node n2){ll s = n1.sum + n2.sum,ls = std::max(n1.leftSum, n1.sum + n2.leftSum),rs = std::max(n2.rightSum, n2.sum + n1.rightSum),mx = std::max({n1.rightSum + n2.leftSum, n1.max, n2.max});return {s, ls, rs, mx};}void set(int k, ll v){k += numLeaf;data[k] = {v, v, v, v};while(k > 1){k /= 2;data[k] = merge(data[k*2], data[k*2+1]);}}Node query(int l, int r){if(l >= r){return {0, -INF, -INF, -INF};}std::queue<int> idx_l;std::stack<int> idx_r;l += numLeaf;r += numLeaf;for(;l<r;l/=2,r/=2){if(l & 1){idx_l.emplace(l);l += 1;}if(r & 1){r -= 1;idx_r.emplace(r);}}until(idx_r.empty()){idx_l.emplace(idx_r.top());idx_r.pop();}Node res = data[idx_l.front()];idx_l.pop();until(idx_l.empty()){res = merge(res, data[idx_l.front()]);idx_l.pop();}return res;}};int main(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);std::cin >> N >> Q;SegmentTree seg(N);for(int i=0;i<N;++i){int A;std::cin >> A;seg.set(i, A);}for(int i=0;i<Q;++i){std::string type;std::cin >> type;if(type[0] == 's'){int i;ll x;std::cin >> i >> x;--i;seg.set(i, x);}else{int l1, l2, r1, r2;std::cin >> l1 >> l2 >> r1 >> r2;--l1; --l2; --r1; --r2;r1 = std::max(r1, l1);l2 = std::min(l2, r2);ll res;if(l2 < r1){SegmentTree::Noden1 = seg.query(l1, l2 + 1),n2 = seg.query(l2 + 1, r1),n3 = seg.query(r1, r2 + 1);res = n1.rightSum + n2.sum + n3.leftSum;}else{SegmentTree::Noden1 = seg.query(l1, r1),n2 = seg.query(r1, l2 + 1),n3 = seg.query(l2 + 1, r2 + 1);res = std::max({n2.max,n1.rightSum + n2.leftSum,n2.rightSum + n3.leftSum,n1.rightSum + n2.sum + n3.leftSum});}std::cout << res << std::endl;}}}