제출 #1275498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275498		masterofcpp	원숭이와 사과 나무 (IZhO12_apple)	C++20	컴파일 에러	0 ms	0 KiB

apple

/*
            ,___________________________________________/7_
           |-_______------. `\                             |
       _,/ | _______)     |___\____________________________|
  .__/`((  | _______      | (/))_______________=.
     `~) \ | _______)     |   /----------------_/
       `__y|______________|  /
       / ________ __________/
      / /#####\(  \  /     ))
     / /#######|\  \(     //
    / /########|.\______ad/`
   / /###(\)###||`------``
  / /##########||
 / /###########||
( (############||
 \ \####(/)####))
  \ \#########//
   \ \#######//
    `---|_|--`
       ((_))
        `-`
*/

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define bigint __int128
#define int long long
#define double long double
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define stop(msg) {cout<<msg; return;}
#define all(aba) aba.begin(), aba.end()
#define rall(aba) aba.rbegin(), aba.rend()
#define take(aba) for (int abab=0; abab<aba.size(); abab++) cin>>aba[abab]
#define print(aba,sep) for (auto abab : aba) cout<<abab<<sep
#define pprint(aba,sep1,sep2) for (int abab=0; abab<aba.size(); abab++) cout<<aba[abab].F<<sep1<<aba[abab].S<<sep2
#define line "-------------------\n"
#define nline "\n-------------------\n"
#define linen "-------------------\n"

/// find_by_order (index), order_of_key (lower bound)
template<typename t>
using indexed_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename t>
using indexed_multiset = tree<t, null_type, less_equal<t>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int rand(int l, int r) {return rng()%(r-l+1)+l;}

double estimate_time(double n) {
    double a = 7.1e-9, b = 0.02;
    return max((double)0, a*n+b);
}

// O(1e8) = 1s.

const int MOD = (int)1e9;
const int N = (int)3e6+6;
const int LG = (int)20;
const int INF = (int)1e18;

vector<int> T(N, 0), L(N, 0), R(N, 0), lazy(N, 0);
int node=1;

void push(int v, int l, int r) {
    if (lazy[v]) {
        int ripen = (r-l+1)-T[v];
        T[v] += lazy[v]*ripen;
        if (l != r) {
            if (!L[v]) L[v] = ++node;
            if (!R[v]) R[v] = ++node;
            lazy[L[v]] += lazy[v];
            lazy[R[v]] += lazy[v];
        }
        lazy[v] = 0;
    }
}

void update(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (r < ql || l > qr) return;
    if (ql <= l && r <= qr) {
        lazy[v]++;
        push(v, l, r);
        return;
    }
    int mid = (l+r)/2;
    if (!L[v]) L[v] = ++node;
    if (!R[v]) R[v] = ++node;
    update(L[v], l, mid, ql, qr);
    update(R[v], mid+1, r, ql, qr);
    T[v] = T[L[v]] + T[R[v]];
}

int ask(int v, int l, int r, int ql, int qr) {
    if (r < ql || l > qr) return 0;
    push(v, l, r);
    if (ql <= l && r <= qr) return T[v];
    int mid = (l+r)/2, res1 = 0, res2 = 0;
    if (L[v]) res1 = ask(L[v], l, mid, ql, qr);
    if (R[v]) res2 = ask(R[v], mid+1, r, ql, qr);
    return res1 + res2;
}

void solve() {
    int q, ans=0; cin>>q;
    while (q--) {
        int cmd,l,r; cin>>cmd>>l>>r;
        int ql = l+ans, qr = r+ans;
        if (cmd == 1) {
            int res = ask(1, 1, 1e9, ql, qr);
            cout<<res<<endl;
            ans = res;
        } else update(1, 1, 1e9, ql, qr);
    }
}

signed main(){
    Fast;
    int t=1;
    //cin>>t;
    for (int i=1; i<=t; i++) {
        solve();
    }
    return 0;
}