fork download
copy 
  1. /*==============================================*/
  2. //!  Captain_Luffy_
  3. /*==============================================*/
  4. #include <bits/stdc++.h>
  5. #define ll long long
  6. #define el '\n'
  7. #define all(v) v.begin() , v.end()
  8. #define allr(v) v.rbegin() , v.rend()
  9. #define YES cout << "YES" << el ;
  10. #define NO cout << "NO" << el ;
  11. const ll N = 1e6 + 5 , M = 1e2 + 5 , mod2 = 1e9 + 7 , mod = 998244353 , INF = 1e18 , OO = 0x3f3f3f3f ;
  12. #define RAMY ios_base::sync_with_stdio(0) , cout.tie(0) , cin.tie(0) ;
  13. using namespace std ;
  14. /*==============================================*/
  15. //! Look Down :)
  16. /*==============================================*/
  17. class segment_tree_lazy
  18. {
  19. private:
  20.  
  21.     struct node
  22.     {
  23.         ll sum = 0 ;
  24.         bool lazy = 0 ;
  25.  
  26.         void apply_build ( ll lx , ll rx , ll val ) 
  27.         {
  28.             sum = val ;
  29.             lazy = 0 ;
  30.         }
  31.  
  32.         void apply_lazy ( ll lx , ll rx ) 
  33.         {
  34.             sum = ( rx - lx + 1 ) - sum ;
  35.             lazy = !lazy ;
  36.         }
  37.  
  38.         void merge ( node L , node R )
  39.         {
  40.             sum = L.sum + R.sum ;
  41.         }
  42.     };
  43.  
  44.     ll sz = 1 ; 
  45.     vector < node > seg ;
  46.  
  47.     void propagate ( ll x , ll lx , ll rx )
  48.     {
  49.         if ( !seg[x].lazy || ( lx == rx ) ) return ;
  50.  
  51.         ll left_child = ( (2 * x) + 1 ) ; 
  52.         ll right_child = ( (2 * x) + 2 ) ; 
  53.         ll mid = ( lx + rx ) / 2 ;
  54.  
  55.  
  56.         seg[left_child].apply_lazy( lx , mid ) ;
  57.         seg[right_child].apply_lazy( mid + 1 , rx ) ;
  58.  
  59.         seg[x].lazy = 0 ;
  60.     }
  61.  
  62.     void build ( ll x , ll lx , ll rx , vector <ll>& v )
  63.     {
  64.         if ( lx == rx )
  65.         {
  66.             if ( lx < (ll)v.size() )
  67.             {
  68.                 seg[x].apply_build ( lx , rx , v[lx] ) ;
  69.             }
  70.             return ;
  71.         }
  72.  
  73.         ll left_child = ( (2 * x) + 1 ) ; 
  74.         ll right_child = ( (2 * x) + 2 ) ; 
  75.         ll mid = ( lx + rx ) / 2 ;
  76.  
  77.         build ( left_child , lx , mid , v ) ;
  78.         build ( right_child , mid + 1 , rx , v ) ;
  79.  
  80.         seg[x].merge ( seg[left_child] , seg[right_child] ) ;
  81.     }
  82.  
  83.     void update ( ll x , ll lx , ll rx , ll l , ll r ) 
  84.     {
  85.         if ( lx > r || rx < l ) return ;
  86.         if ( lx >= l && rx <= r )
  87.         {
  88.             seg[x].apply_lazy( lx , rx ) ;
  89.             return ;
  90.         }
  91.         propagate ( x , lx , rx ) ;
  92.  
  93.         ll left_child = ( (2 * x) + 1 ) ; 
  94.         ll right_child = ( (2 * x) + 2 ) ; 
  95.         ll mid = ( lx + rx ) / 2 ;
  96.  
  97.         update ( left_child , lx , mid , l , r ) ;
  98.         update ( right_child , mid + 1 , rx , l , r ) ;
  99.  
  100.         seg[x].merge( seg[left_child] , seg[right_child] ) ;
  101.     }
  102.  
  103.     ll query ( ll x , ll lx , ll rx , ll k )
  104.     {
  105.         if ( lx == rx ) return lx ;
  106.         propagate( x , lx , rx ) ;
  107.  
  108.         ll left_child = ( (2 * x) + 1 ) ; 
  109.         ll right_child = ( (2 * x) + 2 ) ; 
  110.         ll mid = ( lx + rx ) / 2 ;
  111.  
  112.         if ( seg[left_child].sum > k )
  113.         return query ( left_child , lx , mid , k ) ;
  114.         else 
  115.         return query ( right_child , mid + 1 , rx , k - seg[left_child].sum ) ;
  116.     }
  117.  
  118. public:
  119.     segment_tree_lazy( vector <ll>& v )
  120.     {
  121.         while ( sz < (ll)v.size() )
  122.         {
  123.             sz *= 2 ;
  124.         }
  125.  
  126.         seg.assign( 2 * sz , node() ) ;
  127.  
  128.         build ( 0 , 0 , sz - 1 , v ) ;
  129.     };
  130.     void update ( ll l , ll r )
  131.     {
  132.         update ( 0 , 0 , sz - 1 , l , r ) ;
  133.     }
  134.     ll query( ll k )
  135.     {
  136.         return query ( 0 , 0 , sz - 1 , k ) ;
  137.     }
  138. };
  139.  
  140. void Captain()
  141. { 
  142.     ll n , q ; cin >> n >> q ;
  143.     vector < ll > v(n) ;
  144.  
  145.     segment_tree_lazy st ( v ) ;
  146.  
  147.     while ( q -- )
  148.     {
  149.         ll op ; cin >> op ;
  150.         if ( op == 1 )
  151.         {
  152.             ll l , r ;
  153.             cin >> l >> r ;
  154.             r -- ;
  155.             st.update ( l , r ) ;
  156.         }
  157.         else 
  158.         {
  159.             ll k ; cin >> k ;
  160.             cout << st.query( k ) << el ;
  161.         }
  162.     }
  163. }
  164. /*==============================================*/
  165. void pre()
  166. {
  167.  
  168. }
  169. /*==============================================*/
  170. int main()
  171. {
  172.     RAMY
  173.     ll test = 1 ;
  174.     if ( fopen("input.txt","r") )
  175.     {
  176.         freopen("input.txt","r",stdin) ;
  177.         freopen("output.txt","w",stdout) ;
  178.     }
  179.     // cin >> test ;
  180.     pre() ;
  181.  
  182.     while ( test -- )
  183.     { Captain() ; }
  184.  
  185.     return 0 ;
  186. }
  187. /*==============================================*/
  188. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⡴⠚⢉⡃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣉⠛⠻⢶⢦⣀
  189. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠖⢫⢗⣴⡿⣻⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠑⢰⣜⣎⣎⠷⢄
  190. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⢁⣴⢣⣫⠌⣽⢃⣀⡤⠤⠀⠀⠀⠀⠀⠀⠀⠤⠤⠤⢤⣀⣠⡟⣟⣘⠘⡆⠑⣄⠀
  191. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀  ⠀⡴⠃⣰⡿⣴⡧⠷⠚⠉⠁⣀⣠⠤⢤⣒⣒⣂⣀⣠⣠⣄⣠⣤⣶⣿⡟⠙⠻⢼⣾⡞⡆⠈⣷⡀
  192. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡜⢁⣾⠟⠋⠙⣿⣶⣶⣶⣷⣶⣶⣾⣿⣿6⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⣤⣌⣙⠿⣕⡀⠿⡄
  193. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣎⠴⠋⠀⣠⠔⣢⣼⣿⣿⣿⣿⣿⡿⠉⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠛⢫⡙⠈⠳⣄⢻⡄
  194. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡄⠀⠀⣠⠞⠁⢀⡤⣚⣵⣿⣿⣿⣿⣿⣿⣿⠏⠀⠀⠀⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⠈⠲⣄⠈⣳⣇
  195. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣶⣴⣉⣀⣴⣫⣾⣿⣿⣿⣿⣿⡟⣿⣿⠋⠀⠀⠀⠀⠀⢿⣿⣿⣿⣿⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⡈⢧⡈⢙⣆
  196. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢸⣿⠇⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⣿⠀⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠙⣄⠹⣦⡀
  197. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⠋⠀⡙⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⣸⣟⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⠀⠀⠘⣿⣿⣿⡿⣿⣿⣿⣿⣿⣿⡟⢿⡜⣎⢦⠙⣷⡀
  198. //? ⠀⠀⠀⠀⠀⠀⠀⠀⡼⠃⢠⣯⣾⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⣻⡧⣀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⣿⢀⣤⠶⢻⣿⣿⡷⢿⣿⣿⣿⣿⣿⣿⣴⡿⡜⣾⡇⠈⣷
  199. //? ⠀⠀⠀⠀⠀⠀⠀⣼⠁⢠⣿⣿⠟⠋⣽⣿⣿⣿⣿⣿⣧⠶⠚⢻⡏⢿⠲⢦⣀⠀⠀⣠⠀⠀⠀⢿⣿⠋⠀⠀⠸⣿⣿⠀⢸⣿⣿⣿⣿⣿⣿⣿⡅⠙⠀⠘⣄⠙⣧
  200. //? ⠀⠀⠀⠀⠀⠀⢸⠃⠀⣼⡟⠁⠀⣠⣿⣿⣿⣿⣿⣿⠁⠀⠀⠈⢇⠀⢣⠉⠈⠑⠀⠙⢦⠀⠀⢸⡏⠀⢀⣠⣶⣿⠇⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣄⠀⠀⢸⠀⠸⡇
  201. //? ⠀⠀⠀⠀⠀⠀⢸⠀⠀⡇⠁⠄⣰⣿⣿⣿⣿⣿⣿⣇⠀⠀⠠⣄⣿⣶⣦⣆⡄⠀⠀⢄⣿⠆⠀⠘⠃⣰⣿⣷⡿⠿⠶⣦⡀⣿⣿⢻⣿⣿⣿⣿⡝⠻⣦⣠⠀⠇⠀⢳
  202. //? ⠀⠀⠀⠀⠀⠀⢸⠇⠀⢁⣴⡾⠿⢻⣿⣿⣿⣿⣿⣿⠀⣠⣾⠟⠉⠠⠶⠛⠇⠀⠀⣿⠁⠀⠀⠀⠈⠛⣙⣉⣉⣀⣠⡴⠛⣿⡏⣿⣿⣿⣿⣿⡇⠀⠀⠙⠈⢡⠀⣼
  203. //? ⠀⠀⠀⠀⠀ ⣾⠄⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣟⢿⡇⠀⠁⠀⠀⠀⠂⠐⠀⠀⠀⠉⠣⠘⠂⠀⣀⣐⣀⣈⣁⡤⠤⠷⠶⣟⠀⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠱⠀⣧
  204. //? ⠀⠀⠀⠀⠀ ⢯⡆⠐⡄⠀⠀⠀⣾⣿⡇⣿⣿⣿⣆⢹⣷⠞⠚⠋⠉⠉⠉⡉⠉⠉⠉⠉⠉⠉⠉⠉⠁⠀⠀⢀⠀⠀⢀⠀⢸⢀⣿⣿⣿⣿⠹⣇⠀⠀⠀⠀⡇⠀⣸
  205. //? ⠀⠀⠀⠀⠀⠀⢸⡃⠀⢳⢰⡀⣄⠈⣿⡀⣼⣛⢻⡏⣿⠃⠀⡆⠀⢠⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡇⠀⣸⡤⢸⢸⡿⣿⢻⣿⡄⠉⠀⠀⠀⢸⠀⢠⡏
  206. //? ⠀⠀⠀⠀⠀⠀⠀⢧⠀⠈⣧⢷⡙⣮⢯⡧⣇⣯⣷⢹⣸⡆⠦⢽⣄⣘⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠤⠤⠒⠚⡟⠋⠹⢀⡟⡾⣾⣿⢸⠈⢻⣦⣄⣠⢄⡟⣀⡞
  207. //? ⠀⠀⠀⠀⠀⠀⠀⠈⢣⣤⠘⢿⡻⠈⠉⠁⠹⣜⢯⡓⢧⢳⡀⢸⡁⠈⡇⠀⠠⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠀⢀⡼⣽⢗⣫⢏⡞⠀⠛⠿⡿⢃⡞⠀⡞
  208. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠳⣅⠀⠝⣆⠺⣔⢴⣬⣳⢭⣩⣦⢳⣄⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡞⣱⢗⣋⡽⢋⡀⠀⠀⡀⣠⠊⣰⡜
  209. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠢⣄⠈⢳⣌⡛⠋⠉⠁⠀⠈⠳⢼⡷⢤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⡾⢋⣴⡿⠉⠱⣶⠿⢟⡵⣺⠞⢁⣴⠋
  210. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠓⠤⣀⢀⠀⢦⡿⣔⠯⣷⠆⢻⣶⣬⣳⠲⠤⣄⣀⣀⣀⣤⠤⠤⢖⡻⣟⣭⣴⣿⠏⢳⣺⠴⢀⡀⢉⡜⡁⣠⠞⠁
  211. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⢥⣀⠉⠻⣋⠀⠀⠨⠓⢻⢎⠙⠒⠯⣄⡀⢀⣐⡶⠾⠛⠋⡽⣸⠃⠉⠀⠀⠀⢚⡩⠞⢡⣾⠟⠁
  212. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡬⠵⣶⡤⣄⡐⠦⠄⢸⢸⠀⠁⠀⠀⠉⠉⠀⠀⠀⠀⣸⠁⡏⠄⣀⣀⣤⠮⣭⣤⠚⠋
  213. //? ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡾⢃⣴⣿⣿⣿⣿⣿⣷⣦⡟⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⠀⣷⣛⣉⣬⣤⣤⡈⠹⢳⡄
  214. //? ⠀⠀⠀⠀⠀⠀⠀⠀⣠⠴⠚⠉⠛⠒⢲⡏⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⡞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣧⠀⢻⣿⣿⣿⣿⣿⣿⣧⠈⠙⠦⣄⡤⠴⠦⣤⡀
  215. //? ⠀⠀⠀⠀⠀⠀⢀⡞⢉⣴⣾⣿⣿⣷⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⣰⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡀⠸⣿⣿⣿⣿⣿⣿⣿⣷⣄⣤⣤⣤⣴⣶⣭⡙⢦⡀
  216. //? ⠀⠀⠀⠀⠀⢠⠏⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⡴⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢳⡀⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡄⠱⡄
  217. //? ⠀⠀⠀⠀⠀⡟⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡫⠞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢤⡙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⣿⡀
  218. //? ⠀⠀⢀⡴⠞⣡⣬⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠻⠥⠯⢤⣄⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⣤⠤⠽⠦⠭⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡞⢿⣦
  219. //? ⠀⣰⠏⣡⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⡀⠀⠀⠀⠀⠉⠙⠲⢤⠀⠀⠀⠀⠤⠒⠋⠉⠁⠀⠀⠀⠀⠀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣜⠛⣆
  220. //? ⠼⠁⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠘⢆
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/v1sogL
language:
C++ (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!