#1131592 (C++17) No.3314 Library Rearrangement

• 問題: No.3314 Library Rearrangement
• ユーザー: GOTKAKO
• 提出日時: 2025-11-07 20:03:10
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,004 ms / 3,000 ms
• コード長: 14,285 bytes
• コンパイル時間: 2,264 ms
• コンパイル使用メモリ: 216,732 KB
• 実行使用メモリ: 14,540 KB
• 最終ジャッジ日時: 2025-11-07 20:03:41
• 合計ジャッジ時間: 30,199 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 39

ソースコード

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

//range chminchmaxaddset rangeminmaxsum専用.
long long INF = 2e18;
struct SS{long long len,s,l1,l2,lc,h1,h2,hc;};
using FF = long long;
class SegmentTreeBeats{
    //遅延セグ木ではmapping f,xが上手くいかない場合がある.
    //その時再帰的にやるのがBeats! 失敗回数が抑えられたら良い.
    //verify不十分.
    private:
    vector<SS> dat;
    vector<FF> lazy;
 
    SS op(const SS &a,const SS &b){
        if(a.len == 0) return b;
        if(b.len == 0) return a;
        SS ret; ret.len = a.len+b.len,ret.s = a.s+b.s;
        if(a.l1 == b.l1){
            ret.l1 = a.l1,ret.lc = a.lc+b.lc;
            ret.l2 = min(a.l2,b.l2);
        }
        else if(a.l1 < b.l1){
            ret.l1 = a.l1,ret.lc = a.lc;
            ret.l2 = min(a.l2,b.l1);
        }
        else{
            ret.l1 = b.l1,ret.lc = b.lc;
            ret.l2 = min(a.l1,b.l2);
        }
        if(a.h1 == b.h1){
            ret.h1 = a.h1,ret.hc = a.hc+b.hc;
            ret.h2 = min(a.h2,b.h2);
        }
        else if(a.h1 > b.h1){
            ret.h1 = a.h1,ret.hc = a.hc;
            ret.h2 = min(a.h2,b.h1);
        }
        else{
            ret.h1 = b.h1,ret.hc = b.hc;
            ret.h2 = min(a.h1,b.h2);
        }
        return ret;
    }
    SS e(){return {0,0,INF,INF,0,-INF,-INF,0};}
    long long op(long long a,int pos,int type){
        if(type == 0) return min(a,dat.at(pos).l1);
        else if(type == 1) return max(a,dat.at(pos).h1);
        else if(type == 2) return a+dat.at(pos).s;
        else assert(false);
    }
    long long e(int type){
        if(type == 0) return INF;
        else if(type == 1) return -INF;
        else if(type == 2) return 0;
        else assert(false);
    }

    void merge(int u){ //dat[u]更新 子2つから受け取る.
        SS &d = dat.at(u);
        SS &a = dat.at(u*2),&b = dat.at(u*2+1);
        if(a.len == 0){d = b; return;}
        if(b.len == 0){d = a; return;}

        d.len = a.len+b.len,d.s = a.s+b.s;
        if(a.l1 == b.l1){
            d.l1 = a.l1,d.lc = a.lc+b.lc;
            d.l2 = min(a.l2,b.l2);
        }
        else if(a.l1 < b.l1){
            d.l1 = a.l1,d.lc = a.lc;
            d.l2 = min(a.l2,b.l1);
        }
        else{
            d.l1 = b.l1,d.lc = b.lc;
            d.l2 = min(a.l1,b.l2);
        }
        if(a.h1 == b.h1){
            d.h1 = a.h1,d.hc = a.hc+b.hc;
            d.h2 = max(a.h2,b.h2);
        }
        else if(a.h1 > b.h1){
            d.h1 = a.h1,d.hc = a.hc;
            d.h2 = max(a.h2,b.h1);
        }
        else{
            d.h1 = b.h1,d.hc = b.hc;
            d.h2 = max(a.h1,b.h2);
        }
    }    
    void spreadadd(int u,long long x){ //uに+x.
        SS &d = dat.at(u);
        d.s += x*d.len;
        d.l1 += x,d.h1 += x;
        if(d.l2 != INF) d.l2 += x;
        if(d.h2 != -INF) d.h2 += x;
        if(u < siz) lazy.at(u) += x;
    }
    void spreadmin(int u,long long x){ //uにminx,x>uのmax2番目->最大値以外影響0の時. 
        SS &d = dat.at(u);
        d.s += (x-d.h1)*d.hc;
        if(d.h1 == d.l1) d.l1 = x; //値1種類.
        else if(d.h1 == d.l2) d.l2 = x; //2種類.
        d.h1 = x;
    }
    void spreadmax(int u,long long x){ //uにmaxx,x<uのmin2番目->最小値以外影響0の時. 
        SS &d = dat.at(u);
        d.s += (x-d.l1)*d.lc;
        if(d.l1 == d.h1) d.h1 = x; //値1種類.
        else if(d.l1 == d.h2) d.h2 = x; //2種類.
        d.l1 = x;
    }
    void spread(int u){ //uの保持を伝播.
        if(lazy.at(u) != 0){
            spreadadd(u*2,lazy.at(u));
            spreadadd(u*2+1,lazy.at(u));
            lazy.at(u) = 0;
        }
        //異なるならu以前でchmin,chmaxをした 子でもmappingが成功. 
        if(dat.at(u).h1 < dat.at(u*2).h1) spreadmin(u*2,dat.at(u).h1); //u.h>u*2.hは次の行で対応.
        if(dat.at(u).l1 > dat.at(u*2).l1) spreadmax(u*2,dat.at(u).l1); //u.l<u*2.lは前の行で対応.
        if(dat.at(u).h1 < dat.at(u*2+1).h1) spreadmin(u*2+1,dat.at(u).h1);
        if(dat.at(u).l1 > dat.at(u*2+1).l1) spreadmax(u*2+1,dat.at(u).l1);
    }
    void subtreemin(int u,long long x){ //uの部分木にminx,
        if(x >= dat.at(u).h1) return; //部分木max<=xは変化0.
        if(x > dat.at(u).h2){spreadmin(u,x); return;} //この時だけmapping成功.
        spread(u),subtreemin(u*2,x),subtreemin(u*2+1,x),merge(u);
    }
    void subtreemax(int u,long long x){
        if(x <= dat.at(u).l1) return;
        if(x < dat.at(u).l2){spreadmax(u,x); return;}
        spread(u),subtreemax(u*2,x),subtreemax(u*2+1,x),merge(u);
    }

    void update(int pos,int type,long long x){ //pos更新.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        if(type == 0) subtreemin(pos,x);
        else if(type == 1) subtreemax(pos,x);
        else if(type == 2) spreadadd(pos,x);
        else if(type == 3) subtreemin(pos,x),subtreemax(pos,x); //setはchmin&chmaxで代用.
        else assert(false);
        while(pos > 1) pos >>= 1,merge(pos);
    }
    void update(int l,int r,int type,long long x){ //[l,r)更新 type0chmin,1chmax,2add,3set. 
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return;
        l += siz; r += siz;
        for(int i=log; i>0; i--){
            if(((l>>i)<<i) != l) spread(l>>i);
            if(((r>>i)<<i) != r) spread((r-1)>>i); 
        }
        int memoL = l,memoR = r;
        if(type == 0){
            while(l < r){
                if(l&1) subtreemin(l++,x);
                if(r&1) subtreemin(--r,x);
                l >>= 1; r >>= 1;
            }
        }
        else if(type == 1){
            while(l < r){
                if(l&1) subtreemax(l++,x);
                if(r&1) subtreemax(--r,x);
                l >>= 1; r >>= 1;
            }
        }
        else if(type == 2){
            while(l < r){
                if(l&1) spreadadd(l++,x);
                if(r&1) spreadadd(--r,x);
                l >>= 1; r >>= 1;
            }
        }
        else if(type == 3){
            while(l < r){
                if(l&1) subtreemin(l,x),subtreemax(l,x),l++;
                if(r&1) --r,subtreemin(r,x),subtreemax(r,x);
                l >>= 1; r >>= 1;
            }
        }
        else assert(false);
        
        l = memoL,r = memoR;
        while((l&1) == 0) l >>= 1;
        while((r&1) == 0) r >>= 1;
        r--; //-1注意.
        while(l > 1) l >>= 1,merge(l);
        while(r > 1) r >>= 1,merge(r); 
    }
    long long get(int pos,int type){ //type0min,1max,2sum.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        if(type == 0) return dat.at(pos).l1;
        else if(type == 1) return dat.at(pos).h1;
        else if(type == 2) return dat.at(pos).s;
        else assert(false);
    }
    long long rangeans(int l,int r,int type){
        assert(0 <= l && l <= r && r <= n);
        long long ret = e(type);
        if(l == r) return ret;

        l += siz; r += siz;
        for(int i=log; i>0; i--){
            if(((l>>i)<<i) != l) spread(l>>i);
            if(((r>>i)<<i) != r) spread((r-1)>>i); 
        }
        while(l < r){
            if(l&1) ret = op(ret,l++,type);
            if(r&1) ret = op(ret,--r,type);
            l >>= 1; r >>= 1;
        }
        return ret;
    }

    public:
    int siz = -1,n = -1,log = 0;
    SegmentTreeBeats(int N){ //初期化を配列で与えないなら0で初期化.
        siz = 1; n = N; log = 0;
        while(siz < n) siz <<= 1,log++;
        dat.resize(siz*2);
        lazy.resize(siz,0);
        for(int i=0; i<n; i++){
            SS &d = dat.at(i+siz);
            long long a = 0; //Ai=0.
            d.len = 1,d.s = a,d.l1 = a,d.h1 = a,d.lc = 1,d.hc = 1;
            d.l2 = INF,d.h2 = -INF;
        }    
        for(int i=siz-1; i>0; i--) merge(i);
    }
    SegmentTreeBeats(const vector<long long> &A){//配列サイズに合わせる.
        siz = 1; n = A.size(); log = 0;
        while(siz < n) siz <<= 1,log++;
        dat.resize(siz*2);
        lazy.resize(siz,0);
        for(int i=0; i<n; i++){
            SS &d = dat.at(i+siz);
            long long a = A.at(i);
            d.len = 1,d.s = a,d.l1 = a,d.h1 = a,d.lc = 1,d.hc = 1;
            d.l2 = INF,d.h2 = -INF;
        }    
        for(int i=siz-1; i>0; i--) merge(i);
    }
    
    //変数抜かして区間更新->1点更新になってないか注意.
    void updatemin(int pos,long long x){update(pos,0,x);} //1点chmin.
    void updatemin(int l,int r,long long x){update(l,r,0,x);} //区間chmin.
    void updatemax(int pos,long long x){update(pos,1,x);} //1点chmax.
    void updatemax(int l,int r,long long x){update(l,r,1,x);} //区間chmax.
    void updateadd(int pos,long long x){update(pos,2,x);} //1点加算.
    void updateadd(int l,int r,long long x){update(l,r,2,x);} //区間加算.
    void set(int pos,long long x){update(pos,3,x);} //1点変更.
    void set(int l,int r,long long x){update(l,r,3,x);} //区間変更 全てxにする.
 
    SS get(int pos){ //1点取得.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        return dat.at(pos);
    }
    long long getmin(int pos){return get(pos,0);}
    long long getmax(int pos){return get(pos,1);}
    long long getsum(int pos){return get(pos,2);}
    SS rangeans(int l,int r){ //区間取得.
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return e();
        l += siz; r += siz;
        for(int i=log; i>0; i--){
            if(((l>>i)<<i) != l) spread(l>>i);
            if(((r>>i)<<i) != r) spread((r-1)>>i); 
        }
 
        SS retl = e(),retr = e();
        while(l < r){
            if(l&1) retl = op(retl,dat.at(l++));
            if(r&1) retr = op(dat.at(--r),retr);
            l >>= 1; r >>= 1;
        }
        return op(retl,retr);
    }
    long long rangeansmin(int l,int r){return rangeans(l,r,0);}
    long long rangeansmax(int l,int r){return rangeans(l,r,1);}
    long long rangeanssum(int l,int r){return rangeans(l,r,2);}
    SS allrange(){return dat.at(1);} //全体取得.
    long long allrangesum(){return dat.at(1).s;}
    long long allrangemin(){return dat.at(1).l1;}
    long long allrangemax(){return dat.at(1).h1;}

    int maxright(const function<bool(SS)> f,int l = 0){
        assert(0 <= l && l <= n && f(e()));
        if(l == n) return n;
        l += siz;
        for(int i=log; i>0; i--) spread(l>>i);
        SS now = e();
        do{
            while(l%2 == 0) l >>= 1;
            SS next = op(now,dat.at(l));
            if(f(next) == false){
                while(l < siz){
                    spread(l); l <<= 1;
                    next = op(now,dat.at(l));
                    if(f(next)) now = next,l++;
                }
                return l-siz;
            }
            now = next; l++;
        }while((l&-l) != l);
        return n;
    }
    int maxright(const function<bool(long long)> f,int type,int l = 0){
        assert(0 <= l && l <= n && f(e(type)));
        if(l == n) return n;
        l += siz;
        for(int i=log; i>0; i--) spread(l>>i);
        long long now = e(type);
        do{
            while(l%2 == 0) l >>= 1;
            long long next = op(now,l,type);
            if(f(next) == false){
                while(l < siz){
                    spread(l); l <<= 1;
                    next = op(now,l,type);
                    if(f(next)) now = next,l++;
                }
                return l-siz;
            }
            now = next; l++;
        }while((l&-l) != l);
        return n;
    }
    int minleft(const function<bool(SS)> f,int r = -1){
        if(r == -1) r = n;
        assert(0 <= r && r <= n && f(e()));
        if(r == 0) return 0;
        r += siz;
        for(int i=log; i>0; i--) spread((r-1)>>i);
        SS now = e();
        do{
            r--;
            while(r&1) r >>= 1;
            if(r == 0) r = 1;
            SS next = op(dat.at(r),now);
            if(f(next) == false){
                while(r < siz){
                    spread(r);
                    r <<= 1; r++;
                    next = op(now,dat.at(r));
                    if(f(next)) now = next,r--;
                }
                return r+1-siz;
            }
            now = next;
        }while((r&-r) != r);
        return 0;
    }
    int minleft(const function<bool(long long)> f,int type,int r = -1){
        if(r == -1) r = n;
        assert(0 <= r && r <= n && f(e(type)));
        if(r == 0) return 0;
        r += siz;
        for(int i=log; i>0; i--) spread((r-1)>>i);
        long long now = e(type);
        do{
            r--;
            while(r&1) r >>= 1;
            if(r == 0) r = 1;
            long long next = op(now,r,type);
            if(f(next) == false){
                while(r < siz){
                    spread(r);
                    r <<= 1; r++;
                    next = op(now,r,type);
                    if(f(next)) now = next,r--;
                }
                return r+1-siz;
            }
            now = next;
        }while((r&-r) != r);
        return 0;
    }
};

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

    int N,K,Q; cin >> N >> K >> Q;
    vector<long long> A(N);
    for(auto &a : A) cin >> a;
    vector<tuple<int,int,long long>> U(K),Query(Q);
    for(auto &[l,r,x] : U) cin >> l >> r >> x,l--;
    for(auto &[l,r,x] : Query) cin >> l >> r >> x,l--;

    vector<int> Low(Q,-1),High(Q,K+1);
    while(true){
        vector<vector<int>> Mid(K+1);
        bool end = true;
        for(int i=0; i<Q; i++) if(High.at(i)-Low.at(i) > 1) Mid.at((High.at(i)+Low.at(i))/2).push_back(i),end = false;
        if(end) break;
        
        SegmentTreeBeats Z(A);
        for(int i=0; i<=K; i++){
            for(auto qpos : Mid.at(i)){
                auto [l,r,x] = Query.at(qpos);
                if(Z.rangeanssum(l,r) >= x) High.at(qpos) = i;
                else Low.at(qpos) = i;
            }
            if(i == K) break;
            {
                auto [l,r,x] = U.at(i);
                Z.updatemax(l,r,x);
            }
        }

    }

    for(int i=0; i<Q; i++) cout << (High.at(i)==K+1?-1:High.at(i)) << "\n";
}