#1140868 (C++17) No.3411 Range Clamp Sum

• 問題: No.3411 Range Clamp Sum
• ユーザー: GOTKAKO
• 提出日時: 2025-12-18 02:06:27
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,819 bytes
• コンパイル時間: 1,950 ms
• コンパイル使用メモリ: 205,384 KB
• 実行使用メモリ: 165,188 KB
• 最終ジャッジ日時: 2025-12-18 02:07:22
• 合計ジャッジ時間: 44,663 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 11 WA * 17

ソースコード

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

using SS = pair<int,long long>;
class SegmentTree2D{ //二次元セグ木 計算量O(logH*logW) メモリO(2H+N).
    private:
    using Typepos = int;
    class DynamicSegmentTree{ //動的再帰セグ木 二分探索はない.
        public:
        SS op(SS a,SS b){return {a.first+b.first,a.second+b.second};}
        static inline const SS e = {0,0};
 
        private:
        struct Node{
            Typepos pos; //葉posの頂点.
            SS v,all; //v->posの値,all->部分木全部.
            Node *LR[2]; //二分木.
            Node(Typepos p,SS vv):pos(p),v(vv),all(vv),LR{nullptr,nullptr}{}
        };
        Node *root;
        public:
        Typepos siz = 1<<30;
        DynamicSegmentTree(){root = nullptr;}
        void make(Typepos N){siz = 1; while(siz < N) siz *= 2;}
        void setsiz(Typepos N){assert(N==(N&-N)); siz = N;}
 
        private:
        SS getval(Node *p){return p?p->all:e;} //ノードpのallを返す. nullptrの場合分け省く用.
        //葉でない[a,b)の頂点にも[a,b)の1つを割り振ることにより空間をO(N)にする 適宜割り振る所は更新.
        Node* update(Typepos a,Typepos b,Typepos pos,Node *p,SS &v){ //p<-op(p,v); 更新する.
            if(p == nullptr) return new Node(pos,v);
            if(p->pos == pos){
                p->v = op(p->v,v);
                p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1])));
                return p;
            }
            Typepos m = (a+b)/2;
            if(pos < m){
                if(pos > p->pos) swap(pos,p->pos),swap(v,p->v);//左の子のposは親のposより小さくする.
                p->LR[0] = update(a,m,pos,p->LR[0],v);
            }
            else{
                if(pos < p->pos) swap(pos,p->pos),swap(v,p->v); //右の子は親より大きく.
                p->LR[1] = update(m,b,pos,p->LR[1],v);
            }
            p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1])));
            return p;
        }
        Node* set(Typepos a,Typepos b,Typepos pos,Node *p,SS &v){ //p<-v　設定する.
            if(p == nullptr) return new Node(pos,v);
            if(p->pos == pos){
                p->v = v;
                p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1])));
                return p;
            }
            Typepos m = (a+b)/2;
            if(pos < m){
                if(pos > p->pos) swap(pos,p->pos),swap(v,p->v); //左の子のposは親のposより小さくする.
                p->LR[0] = set(a,m,pos,p->LR[0],v);
            }
            else{
                if(pos < p->pos) swap(pos,p->pos),swap(v,p->v); //右の子は親より大きく.
                p->LR[1] = set(m,b,pos,p->LR[1],v);
            }
            p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1])));
            return p;
        }
        public:
        void update(Typepos pos,SS x){
            assert(0 <= pos && pos < siz);
            root = update(0,siz,pos,root,x);
        }
        void set(Typepos pos,SS x){
            assert(0 <= pos && pos < siz);
            root = set(0,siz,pos,root,x);
        }
        private:
        SS findans(Typepos L,Typepos R,Typepos a,Typepos b,Node *p){
            if(p == nullptr || R <= a || b <= L) return e;
            if(L <= a && b <= R) return p->all;
            Typepos m = (a+b)/2;
            SS ret = findans(L,R,a,m,p->LR[0]);
            if(L <= p->pos && p->pos < R) ret = op(ret,p->v);
            return op(ret,findans(L,R,m,b,p->LR[1]));
        }
        public:
        SS rangeans(Typepos L,Typepos R){
            assert(0 <= L && L <= siz && 0 <= R && R <= siz); // L>Rは許容する.
            if(L >= R) return e; 
            return findans(L,R,0,siz,root);
        }
        SS allrange(){return getval(root);}
        SS get(Typepos pos){return rangeans(pos,pos+1);} //O(logsiz).
    };
 
    int h = 1; Typepos w = 1;
    vector<DynamicSegmentTree> dat;
    public:
    SegmentTree2D(int H,Typepos W){
        h = 1,w = 1;
        while(h < H) h <<= 1;
        while(w < W) w <<= 1;
        dat.resize(h*2);
        for(auto &d : dat) d.setsiz(w);
    }
    void update(int x,Typepos y,SS v){ //(x,y)にvを加える.
        assert(0 <= x && x < h && 0 <= y && y < w);
        x += h;
        while(x > 0) dat.at(x).update(y,v),x >>= 1;
    }
    void set(int x,Typepos y,SS v){ //(x,y)をvにする.
        assert(0 <= x && x < h && 0 <= y && y < w);
        x += h;
        while(x > 0) dat.at(x).set(y,v),x >>= 1;
    }
    SS rangeans(int x1,int x2,Typepos y1,Typepos y2){ //(x1,y1)~(x2,y2)の区間の総和.
        assert(0 <= min(x1,x2) && max(x1,x2) <= h && 0 <= min(y1,y2) && max(y1,y2) <= w); //x1>x2,y1>y2はok.
        x1 += h,x2 += h;
        SS ret = dat.at(0).e;
        while(x1 < x2){
            if(x1&1) ret = dat.at(0).op(ret,dat.at(x1++).rangeans(y1,y2));
            if(x2&1) ret = dat.at(0).op(dat.at(--x2).rangeans(y1,y2),ret);
            x1 >>= 1; x2 >>= 1;
        }
        return ret;
    }
};

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

    SegmentTree2D Z(100001,100001);
    int N,Q; cin >> N >> Q;
    vector<int> A(N);
    for(auto &a : A) cin >> a;
    for(int i=0; i<N; i++) Z.update(i,A.at(i),{1,A.at(i)});

    while(Q--){
        int t; cin >> t;
        if(t == 1){
            int x,y; cin >> x >> y,x--;
            Z.update(x,A.at(x),{-1,-A.at(x)});
            A.at(x) = y;
            Z.update(x,A.at(x),{1,A.at(x)});
        }
        else{
            int l,r,a,b; cin >> l >> r >> a >> b,l--,b++;
            long long answer = Z.rangeans(l,r,a,b).second;
            answer += Z.rangeans(l,r,0,a).first*a;
            answer += Z.rangeans(l,r,b,100001).first*(b-1);
            cout << answer << "\n";
        }
    }
}