제출 #1276393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276393		Jean7	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	299 ms	137396 KiB

apple

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)

using namespace std ;

const int N = 1e5+5 ;

int q ;

struct Segment_Tree_Dynamic {
    int tree[100*N] , ll[100*N] , rr[100*N] , lazy[100*N] , idx = 0 ;
    void push ( int node , int l , int r ) {
        if ( !lazy[node] || l == r ) {
            return ;
        }
        if ( !ll[node] ) {
            ll[node] = ++idx ;
        }
        if ( !rr[node] ) {
            rr[node] = ++idx ;
        }
        tree[ll[node]] = mid - l + 1 ;
        tree[rr[node]] = r - mid ;
        lazy[ll[node]] = 1 ;
        lazy[rr[node]] = 1 ;
        lazy[node] = 0 ;
    }
    void update ( int &node , int l , int r , int x , int y ) {
        if ( l > r || l > y || r < x ) {
            return ;
        }
        if ( node == 0 ) {
            node = ++idx ;
            tree[node] = ll[node] = rr[node] = 0 ;
        }
        if ( l >= x && r <= y ) {
            tree[node] = r - l + 1 ;
            lazy[node] = 1 ;
            return ;
        }
        push ( node , l , r ) ;
        update ( ll[node] , l , mid , x , y ) ;
        update ( rr[node] , mid+1 , r , x , y ) ;
        tree[node] = tree[ll[node]] + tree[rr[node]] ;
    }
    int query ( int node , int l , int r , int x , int y ) {
        if ( l > r || l > y || r < x ) {
            return 0 ;
        }
        if ( l >= x && r <= y ) {
            return tree[node] ;
        }
        push ( node , l , r ) ;
        return query ( ll[node] , l , mid , x , y ) + query ( rr[node] , mid+1 , r , x , y ) ;
    }
} seg ;

inline void solve () {
    cin >> q ;
    int rt = 0 , c = 0 ;
    while ( q-- ) {
        int op , x , y ;
        cin >> op >> x >> y ;
        x += c ;
        y += c ;
        if ( op == 1 ) {
            c = seg.query ( rt , 1 , 1e9 , x , y ) ;
            cout << c << "\n" ;
        }
        else {
            seg.update ( rt , 1 , 1e9 , x , y ) ;
        }
    }
}

signed main () {
    //freopen ( ".in" , "r" , stdin ) ;
    //freopen ( ".out" , "w" , stdout ) ;
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;
    int tc = 1 ;
    //cin >> tc ;
    while ( tc-- ) {
        solve() ;
    }
    return 0 ;
}

///  JJJJJJJ EEEEEEE  AAAAA  NN   NN 7777777
///     JJ   EE      AA   AA NNN  NN     77
///     JJ   EEEEEE  AAAAAAA NN N NN    77
///  JJ JJ   EE      AA   AA NN  NNN   77
///  JJJJJ   EEEEEEE AA   AA NN   NN  77

• Subtask 1: 100 / 100