結果

問題 No.3494 一点挿入区間和取得
コンテスト
ユーザー GOTKAKO
提出日時 2026-04-03 22:00:15
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 119 ms / 6,000 ms
コード長 1,761 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,387 ms
コンパイル使用メモリ 220,452 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2026-04-03 22:00:23
合計ジャッジ時間 3,289 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,Q; cin >> N >> Q;
    vector<deque<long long>> Qs(10000);
    vector<long long> S(10000);
    int B = 300;

    auto insert = [&](int pos,long long x) -> void {
        int p = 0;
        for(int i=0; ; i++){
            if(p+B <= pos){p += B; continue;}
            S.at(i) += x;
            stack<long long> st;
            while(p < pos) st.push(Qs.at(i).front()),Qs.at(i).pop_front(),p++;
            Qs.at(i).push_front(x);
            while(st.size()) Qs.at(i).push_front(st.top()),st.pop();

            while(Qs.at(i).size() > B){
                long long v = Qs.at(i).back(); Qs.at(i).pop_back();
                S.at(i) -= v,S.at(i+1) += v;
                Qs.at(i+1).push_front(v),i++;
            }
            break;
        }
    };
    auto rangeans = [&](int l,int r) -> long long {
        long long ret = 0,pos = 0;
        for(int i=0; pos<r; i++,pos+=B){
            if(pos+B <= l) continue;
            if(pos < l){
                if(pos+B > r){
                    for(int k=l-pos; k<r-pos; k++) ret += Qs.at(i).at(k);
                }
                else{
                    for(int k=l-pos; k<B; k++) ret += Qs.at(i).at(k);
                }
            }
            else{
                if(pos+B > r){
                    for(int k=0; k<r-pos; k++) ret += Qs.at(i).at(k);
                }
                else ret += S.at(i);
            }
        }
        return ret;
    };
    for(int i=0; i<N; i++){
        int a; cin >> a;
        insert(i,a);
    }

    while(Q--){
        int i,x,l,r; cin >> i >> x >> l >> r,i--,l--;
        insert(i+1,x);
        cout << rangeans(l,r) << "\n";
    }
}
0