結果

問題 No.2065 Sum of Min
ユーザー 👑 NachiaNachia
提出日時 2022-09-02 21:26:35
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 309 ms / 2,000 ms
コード長 6,447 bytes
コンパイル時間 1,713 ms
コンパイル使用メモリ 113,892 KB
実行使用メモリ 26,808 KB
最終ジャッジ日時 2023-08-10 03:17:56
合計ジャッジ時間 8,663 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 162 ms
26,712 KB
testcase_05 AC 107 ms
26,648 KB
testcase_06 AC 231 ms
26,712 KB
testcase_07 AC 93 ms
26,568 KB
testcase_08 AC 253 ms
26,644 KB
testcase_09 AC 214 ms
26,588 KB
testcase_10 AC 124 ms
26,636 KB
testcase_11 AC 125 ms
26,576 KB
testcase_12 AC 305 ms
26,700 KB
testcase_13 AC 304 ms
26,808 KB
testcase_14 AC 302 ms
26,564 KB
testcase_15 AC 307 ms
26,564 KB
testcase_16 AC 306 ms
26,644 KB
testcase_17 AC 308 ms
26,692 KB
testcase_18 AC 307 ms
26,692 KB
testcase_19 AC 309 ms
26,696 KB
testcase_20 AC 309 ms
26,572 KB
testcase_21 AC 309 ms
26,716 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "nachia\\multi-dimensional\\two-d-rectangle-query.hpp"

#include <vector>
#include <cstdint>
#include <algorithm>
#include <utility>


namespace nachia{



template<class PosX, class PosY>
struct TwoDRectangleQuery{
private:

    struct BitVectorRank {
        using u64 = ::std::uint64_t;
        using u32 = ::std::uint32_t;

        static u32 popcountll(u64 c){
        #ifdef __GNUC__
            return __builtin_popcountll(c);
        #else
            c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
            c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
            c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
            c = (c * (~0ull/255)) >> 56;
            return c;
        #endif
        }
        
        ::std::vector<::std::pair<u64, u32>> a;
        BitVectorRank(const ::std::vector<bool>& b = {}){
            int n = b.size();
            a.assign(n/64 + 1, ::std::make_pair((u64)0, (u32)0));
            auto p = b.begin();
            u32 sum = 0;
            u64 tmp = 0;
            for(int i=0; i<=n; i+=64){
                tmp = 0;
                int maxd = ::std::min<int>(n - i, 64);
                for(int d=0; d<maxd; d++){
                    tmp |= (u64)(*p ? 1 : 0) << d;
                    ++p;
                }
                a[i/64] = ::std::make_pair(tmp, sum);
                sum += popcountll(tmp);
            }
        }
        ::std::uint32_t rank(::std::uint32_t i) const {
            auto [b, s] = a[i >> 6];
            return (u32)(popcountll(b & ~(~u64(0) << (i & 63)))) + s;
        }
        bool get(::std::uint32_t i) const { return (a[i >> 6].first >> (i & 63)) & 1; }
    };
    
    int n;
    int N;
    int logN;
    ::std::vector<PosX> Xsorted;
    ::std::vector<PosY> Ysorted;
    ::std::vector<int> rankX;
    ::std::vector<::std::vector<int>> Idx;
    ::std::vector<int> Z;
    ::std::vector<BitVectorRank> L;

public:

    TwoDRectangleQuery(const ::std::vector<::std::pair<PosX, PosY>>& pos){
        n = pos.size();

        ::std::vector<int> sortIY(n);
        for(int i=0; i<n; i++) sortIY[i] = i;
        ::std::sort(sortIY.begin(),sortIY.end(),[&pos](int l,int r){ return pos[l].second<pos[r].second; });
        Ysorted.resize(n);
        for(int i=0; i<n; i++) Ysorted[i] = pos[sortIY[i]].second;

        ::std::vector<int> sortIX(n);
        rankX.resize(n);
        for(int i=0; i<n; i++) sortIX[i] = i;
        ::std::sort(sortIX.begin(),sortIX.end(),[&pos](int l,int r){ return pos[l]<pos[r]; });
        Xsorted.resize(n);
        for(int i=0; i<n; i++) Xsorted[i] = pos[sortIX[i]].first;
        for(int i=0; i<n; i++) rankX[sortIX[i]] = i;

        N = 1; logN = 0;
        while(N < n){ N *= 2; logN++; }
        Idx.assign(logN+1, ::std::vector<int>(n,-1));
        L.resize(logN);
        Z.resize(logN);
        for(int i=0; i<n; i++) Idx.back()[i] = sortIY[i];
        for(int i=logN-1; i>=0; i--){
            ::std::vector<bool> Lbuf(n,0);
            auto& preList = Idx[i+1];
            int z = ((n >> (i+1)) << i) + ::std::min(1<<i, (n % (2 << i)));
            Z[i] = z;
            int ai = 0, bi = z;
            for(int k=0; k<n; k++){
                bool chooseb = rankX[preList[k]] & (1<<i);
                if(!chooseb) Idx[i][ai++] = preList[k];
                else Idx[i][bi++] = preList[k];
                Lbuf[k] = !chooseb;
            }
            L[i] = BitVectorRank(Lbuf);
        }

        for(int i=0; i<n; i++) rankX[sortIY[i]] = i;
    }
 
    int get_segment_count() const { return Idx.size(); }
    int size() const { return n; }
    int to_vtx(int d, int i) const { return Idx[d][i]; }


    struct UpdatePoint{ int d, i; };

    ::std::vector<UpdatePoint> get_update_points(int v) const {
        ::std::vector<UpdatePoint> res(logN+1);
        int p = rankX[v];
        int d = logN;
        while(d > 0){
            res[d] = { d,p };
            d--;
            if(L[d].get(p)) p = L[d].rank(p);
            else p = Z[d] + p - L[d].rank(p);
        }
        res[d] = {d,p};
        return res;
    }


    struct Query{ int d,l,r; };
    ::std::vector<Query> get_ranges_from_idx(int xl, int xr, int yl, int yr){
        ::std::vector<Query> res;
        struct Search{ int i, xa, xb, ys, yt; };
        ::std::vector<Search> Q;
        res.reserve((logN+1)*2);
        Q.reserve((logN+1)*2);
        Q.push_back({ logN,0,n,yl,yr });
        for(int i=0; i<(int)Q.size(); i++){
            auto p = Q[i];
            if(p.xa == p.xb) continue;
            if(xr <= p.xa || p.xb <= xl) continue;
            if(xl <= p.xa && p.xb <= xr){
                res.push_back({ p.i, p.ys, p.yt });
                continue;
            }
            p.i--;
            int nxs = L[p.i].rank(p.ys), nxt = L[p.i].rank(p.yt);
            Q.push_back({ p.i,p.xa,p.xa+(1<<p.i),nxs,nxt });
            Q.push_back({ p.i,p.xa+(1<<p.i),p.xb,Z[p.i]+p.ys-nxs,Z[p.i]+p.yt-nxt });
        }
        return res; 
    }
  
    ::std::vector<Query> get_ranges(PosX xl, PosX xr, PosY yl, PosY yr){
        return get_ranges_from_idx(
            lower_bound(Xsorted.begin(),Xsorted.end(),xl) - Xsorted.begin(),
            lower_bound(Xsorted.begin(),Xsorted.end(),xr) - Xsorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yl) - Ysorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yr) - Ysorted.begin()
        );
    }
};

} // namespace nachia
#line 2 "Main.cpp"

#include <iostream>
#include <string>
#line 7 "Main.cpp"
#include <set>

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

int main(){
    int N, Q; cin >> N >> Q;
    vector<pair<int,int>> A(N);
    rep(i,N){
        A[i].first = i;
        cin >> A[i].second;
    }
    
    nachia::TwoDRectangleQuery<int,int> d2(A);
    vector<vector<i64>> rqs(d2.get_segment_count());
    rep(i,rqs.size()){
        rqs[i].resize(N+1);
        rep(j,N) rqs[i][j+1] = rqs[i][j] + A[d2.to_vtx(i, j)].second;
    }

    rep(i,Q){
        int l,r,x; cin >> l >> r >> x; l--;
        i64 sum = (i64)x * (r - l);
        for(auto q : d2.get_ranges(l, r, 0, x)) sum += rqs[q.d][q.r] - rqs[q.d][q.l] - (i64)x * (q.r - q.l);
        cout << sum << '\n';
    }
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0