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

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

內容

背景

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

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

題目描述

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

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

多組測資。

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

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

條件約束

  • $1 \le N \le 10^8$
  • $1 \le Q \le 10^5$
  • $1 \le L, R, x \le N, \; L \le 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 (碼畜) ]

本題狀況 本題討論 排行

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