回『原創/不分類題庫』
b491. 史蒂芙的政務工作
標籤 : 伸展樹 區間反轉
通過比率 : 10人/12人 ( 83% ) [非即時]
評分方式：
Tolerant

最近更新 : 2015-08-17 11:34

內容

背景

史蒂芙接管人類最後國家的政務工作，卻時常受到熊孩子搗亂，文書資料原本按照編號 [1⋯N] 排成一疊，熊孩子每一次搗亂都會翻轉位置 [L,R] 的資料，使得編號整個反過來。

史蒂芙已經無暇處理這些熊孩子，她只想知道某個資料現在到底在哪個位置上。

題目描述

給定 N 個整數 1⋯N 以及 Q 個操作，一開始文書編號 i 在位置 i 上。

  • 0 L R
    反轉區間位置 [L,R] 的文書
  • 1 x
    詢問文書編號 x 的位置
輸入說明

多組測資。

每組第一行有兩個整數 N,Q，分別為文書總數、操作總數，接下來有 Q 行，每一行為一筆操作，有以下兩種

  • 0 L R
    反轉區間位置 [L,R] 的文書
  • 1 x
    詢問文書編號 x 在哪個位置

條件約束

  • 1≤N≤108
  • 1≤Q≤105
  • 1≤L,R,x≤N,L≤R
輸出說明
對於每一個詢問輸出一行整數。
範例輸入 #1 
7 6
1 7
0 3 5
1 5
0 1 3
1 3
1 1

5 5
0 1 3
0 4 5
1 1
1 3
1 5

5 5
0 1 4
0 2 5
1 1
1 3
1 5
範例輸出 #1 
7
3
5
3
3
1
4
3
5
2
測資資訊：
記憶體限制： 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 2.0s , <10M
公開 測資點#4 (20%): 2.0s , <10M
提示 ：
標籤:
伸展樹 區間反轉
出處:
[管理者： morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」