SMMR-125: Inf_Array

#include <bits/stdc++.h>

using namespace std;
const int M = 1e5;
using lli = long long;
using pll = pair <lli, lli>;
vector <lli> pst;
lli l[M+10], r[M+10], value[M+10];
lli qs[4*M + 10], qss[4*M + 10]; // ระวังขนาด array เก็บ ตำแหน่ง quicksum และ query
pll query[M+10];
lli m, sz;

lli BinarySearch(lli val){
    lli l = 0, r = sz-1;
    while(l <= r){
        lli mid = (l + r) / 2;
        if(pst[mid] == val) return mid;
        if(pst[mid] < val)
            l = mid + 1;
        else r = mid - 1;
    }
}

int main(){

    lli q;
    scanf("%lld%lld", &m, &q);

    for(int i=1;i<=m;i++) {
        scanf("%lld%lld%lld", &l[i], &r[i], &value[i]);
        pst.push_back(l[i]);
        pst.push_back(r[i]+1);
    }

    for(int i=1;i<=q;i++){
        lli f, s;
        scanf("%lld%lld", &f, &s);
        query[i] = {f-1, s};
        pst.push_back(f-1);
        pst.push_back(s);
    }

    sort(pst.begin(), pst.end());
    pst.resize( unique(pst.begin(), pst.end()) - pst.begin() );
    sz = pst.size();

    for(int i=1;i<=m;i++){
        lli idl = BinarySearch(l[i]);
        qs[idl] += (lli) value[i];
        lli idr = BinarySearch(r[i]+1);
        qs[idr] -= (lli) value[i];
    }

    qss[0] = qs[0];
    for(int i=1;i<sz;i++){
        lli dif = pst[i] - pst[i-1] - 1;
        qs[i] += qs[i-1];
        qss[i] = qss[i-1] + (lli) (qs[i-1] * dif) + qs[i];
    }

    for(int i=1;i<=q;i++) {
        lli idf = BinarySearch(query[i].first);
        lli ids = BinarySearch(query[i].second);
        printf("%lld\n", qss[ids] - qss[idf]);
    }

    return 0;
}
/*

3 2
1 2 1
3 4 2
4 6 3
1 3 4 5 7
1 2 5 3 0

3 10
1 2 1
4 6 2
5 8 1
1 3 4 5 7 9
1 0 2 3 1 0


3 5
1 2 1
4 6 2
5 8 1
3 8
1 6
5 9
9 100
1 1

10 10
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
8 8 8
9 9 9
10 10 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

3 3
1 1 1
4 4 4
7 7 10
1 1
2 2
6 6
*/