#807559 (C++17) No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに

• 問題: No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに
• ユーザー: bayashiko
• 提出日時: 2022-10-15 00:53:26
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2,019 ms / 6,000 ms
• コード長: 11,108 bytes
• コンパイル時間: 4,129 ms
• コンパイル使用メモリ: 232,460 KB
• 最終ジャッジ日時: 2025-02-08 05:40:14
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 42

ソースコード

#if defined(LOCAL)
#include<stdc++.h>
#else
#include<bits/stdc++.h>
#endif
#include<random>
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
//#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define MINF (lint)(2e18)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define flc(x) __builtin_popcountll(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
//#define vec vector<lint>
#define nep(x) next_permutation(all(x))
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=3e5+5;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//vector<int> bucket[MAX_N/1000];
//constexpr int MOD=1000000007;
constexpr int MOD=998244353;
/*#include<atcoder/all>
using namespace atcoder;
typedef __int128_t llint;*/

// Segment Tree Beats
// - l<=i<r について、 A_i の値を min(A_i, x) に更新
// - l<=i<r について、 A_i の値を max(A_i, x) に更新
// - l<=i<r の中の A_i の最大値を求める
// - l<=i<r の中の A_i の最小値を求める
// - l<=i<r の A_i の和を求める
// - l<=i<r について、 A_i の値に x を加える
// - l<=i<r について、 A_i の値を x に更新

class SegmentTreeBeats{
    static const lint inf = 1e18;
    struct Node{
        Node *left, *right;
        lint max_v, smax_v, max_c;
        lint min_v, smin_v, min_c;
        lint sum;
        lint len, ladd, lval;

        Node() : left(0), right(0), ladd(0), lval(inf) {}

        void init(lint x){
            max_v = min_v = sum = x;
            smax_v = -inf;
            smin_v = inf;
            max_c = min_c = 1;
        }

        void init_empty(){
            max_v = smax_v = -inf;
            min_v = smin_v = inf;
            max_c = min_c = 0;
        }

        void update_max(lint x){
            sum += (x - max_v) * max_c;

            if (max_v == min_v){
                max_v = min_v = x;
            }
            else if (max_v == smin_v){
                max_v = smin_v = x;
            }
            else{
                max_v = x;
            }

            if (lval != inf && x < lval){
                lval = x;
            }
        }

        void update_min(lint x){
            sum += (x - min_v) * min_c;

            if (max_v == min_v){
                max_v = min_v = x;
            }
            else if (max_v == smin_v){
                min_v = smax_v = x;
            }
            else{
                min_v = x;
            }

            if (lval != inf && lval < x){
                lval = x;
            }
        }

        void addalint(lint x)
        {
            max_v += x;
            if (smax_v != -inf) smax_v += x;
            min_v += x;
            if (smin_v != inf) smin_v += x;
            sum += len * x;
            if (lval != inf){
                lval += x;
            }
            else{
                ladd += x;
            }
        }

        void updatealint(lint x){
            max_v = min_v = x;
            smax_v = -inf;
            smin_v = inf;
            max_c = min_c = len;

            sum = len * x;
            lval = x;
            ladd = 0;
        }

        void push(){

            if (lval != inf){
                left->updatealint(lval);
                right->updatealint(lval);
                lval = inf;
                return;
            }

            if (ladd != 0){
                left->addalint(ladd);
                right->addalint(ladd);
                ladd = 0;
            }

            if (max_v < left->max_v){
                left->update_max(max_v);
            }
            if (left->min_v < min_v){
                left->update_min(min_v);
            }

            if (max_v < right->max_v){
                right->update_max(max_v);
            }
            if (right->min_v < min_v){
                right->update_min(min_v);
            }
        }

        void update(){
            sum = left->sum + right->sum;

            if (left->max_v < right->max_v){
                max_v = right->max_v;
                max_c = right->max_c;
                smax_v = max(left->max_v, right->smax_v);
            }
            else if (left->max_v > right->max_v){
                max_v = left->max_v;
                max_c = left->max_c;
                smax_v = max(left->smax_v, right->max_v);
            }
            else{
                max_v = left->max_v;
                max_c = left->max_c + right->max_c;
                smax_v = max(left->smax_v, right->smax_v);
            }

            if (left->min_v < right->min_v){
                min_v = left->min_v;
                min_c = left->min_c;
                smin_v = min(left->smin_v, right->min_v);
            }
            else if (left->min_v > right->min_v){
                min_v = right->min_v;
                min_c = right->min_c;
                smin_v = min(left->min_v, right->smin_v);
            }
            else{
                min_v = left->min_v;
                min_c = left->min_c + right->min_c;
                smin_v = min(left->smin_v, right->smin_v);
            }
        }
    };

    int n, n0;
    Node *root;

    void _update_min(lint x, int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a || nd->max_v <= x){
            return;
        }
        if (a <= l && r <= b && nd->smax_v < x){
            nd->update_max(x);
            return;
        }

        nd->push();
        _update_min(x, a, b, nd->left, l, (l + r) / 2);
        _update_min(x, a, b, nd->right, (l + r) / 2, r);
        nd->update();
    }

    void _update_max(lint x, int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a || x <= nd->min_v){
            return;
        }
        if (a <= l && r <= b && x < nd->smin_v){
            nd->update_min(x);
            return;
        }

        nd->push();
        _update_max(x, a, b, nd->left, l, (l + r) / 2);
        _update_max(x, a, b, nd->right, (l + r) / 2, r);
        nd->update();
    }

    void _add_val(lint x, int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return;
        }
        if (a <= l && r <= b){
            nd->addalint(x);
            return;
        }

        nd->push();
        _add_val(x, a, b, nd->left, l, (l + r) / 2);
        _add_val(x, a, b, nd->right, (l + r) / 2, r);
        nd->update();
    }

    void _update_val(lint x, int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return;
        }
        if (a <= l && r <= b){
            nd->updatealint(x);
            return;
        }

        nd->push();
        _update_val(x, a, b, nd->left, l, (l + r) / 2);
        _update_val(x, a, b, nd->right, (l + r) / 2, r);
        nd->update();
    }

    lint _query_max(int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return -inf;
        }
        if (a <= l && r <= b){
            return nd->max_v;
        }
        nd->push();
        lint lv = _query_max(a, b, nd->left, l, (l + r) / 2);
        lint rv = _query_max(a, b, nd->right, (l + r) / 2, r);
        return max(lv, rv);
    }

    lint _query_min(int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return inf;
        }
        if (a <= l && r <= b){
            return nd->min_v;
        }
        nd->push();
        lint lv = _query_min(a, b, nd->left, l, (l + r) / 2);
        lint rv = _query_min(a, b, nd->right, (l + r) / 2, r);
        return min(lv, rv);
    }

    lint _query_sum(int a, int b, Node *nd, int l, int r){
        if (b <= l || r <= a){
            return 0;
        }
        if (a <= l && r <= b){
            return nd->sum;
        }
        nd->push();
        lint lv = _query_sum(a, b, nd->left, l, (l + r) / 2);
        lint rv = _query_sum(a, b, nd->right, (l + r) / 2, r);
        return lv + rv;
    }

public:
    SegmentTreeBeats(int n, vector<lint> a) : n(n){
        n0 = 1;
        while (n0 < n) n0 <<= 1;

        Node *nds = new Node[2 * n0];
        root = nds;

        nds[0].len = n0;
        for (int i = 0; i < n0 - 1; ++i){
            nds[i].left = &nds[2 * i + 1];
            nds[i].right = &nds[2 * i + 2];
            nds[2 * i + 1].len = nds[2 * i + 2].len = (nds[i].len >> 1);
        }

        for (int i = 0; i < n; ++i) nds[n0 - 1 + i].init(a[i]);
        for (int i = n; i < n0; ++i) nds[n0 - 1 + i].init_empty();
        for (int i = n0 - 2; i >= 0; i--) nds[i].update();
    }
    SegmentTreeBeats(int n) : n(n){
        n0 = 1;
        while (n0 < n) n0 <<= 1;

        Node *nds = new Node[2 * n0];
        root = nds;

        nds[0].len = n0;
        for (int i = 0; i < n0 - 1; ++i){
            nds[i].left = &nds[2 * i + 1];
            nds[i].right = &nds[2 * i + 2];
            nds[2 * i + 1].len = nds[2 * i + 2].len = (nds[i].len >> 1);
        }

        for (int i = 0; i < n; ++i) nds[n0 - 1 + i].init(0);
        for (int i = n; i < n0; ++i) nds[n0 - 1 + i].init_empty();
        for (int i = n0 - 2; i >= 0; i--) nds[i].update();
    }

    void update_min(int a, int b, lint x){
        _update_min(x, a, b, root, 0, n0);
    }

    void update_max(int a, int b, lint x){
        _update_max(x, a, b, root, 0, n0);
    }

    void add_val(int a, int b, lint x){
        _add_val(x, a, b, root, 0, n0);
    }

    void update_val(int a, int b, lint x){
        _update_val(x, a, b, root, 0, n0);
    }

    lint query_max(int a, int b){
        return _query_max(a, b, root, 0, n0);
    }

    lint query_min(int a, int b){
        return _query_min(a, b, root, 0, n0);
    }

    lint query_sum(int a, int b){
        return _query_sum(a, b, root, 0, n0);
    }
};


int main(void){
    lint N;
    cin >> N;
    lint A[N],T[N];
    rep(i,N) cin >> A[i] >> T[i];
    vector<pair<plint,plint>> qs;
    int Q;
    cin >> Q;
    lint ans[Q]={};
    rep(i,Q){
        lint D,L,R;
        cin >> D >> L >> R;
        L--;
        qs.push_back({{D,i},{L,R}});
    }
    sort(all(qs));
    SegmentTreeBeats plus(N),minus(N);
    lint lastday=0;
    rep(i,N){
        plus.update_val(i,i+1,A[i]+T[i]-1);
        minus.update_val(i,i+1,T[i]-1);
    }
    for(auto e:qs){
        lint D=e.fi.fi,q=e.fi.se,L=e.se.fi,R=e.se.se;
        plus.add_val(0,N,-(D-lastday));
        minus.add_val(0,N,-(D-lastday));
        minus.update_max(0,N,0);
        plus.update_max(0,N,0);
        ans[q]=plus.query_sum(L,R)-minus.query_sum(L,R);
        lastday=D;
    }
    rep(i,Q) cout << ans[i] << endl;
}