f997: DZ 的平均值遊戲
Tags : 動態開點 線段樹
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-09 11:07

Content

DZ 是一個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「取因數」的遊戲,而現在要講的,是 DZ 出生後七十一個月二十二天大的故事。

DZ 與朋友在走自己的路上時,發現了一家桌遊店,裡面有各種遊戲,例如「碰撞機器人」。Caido 在走了 $\color{black}{207}\ $ 步後終於通關,DZ 看了一眼,卻說:「這很顯然 $\color{black}{49}\ $ 步就能完成了。」

DZ 對這種簡單的桌遊不屑一顧,真正令他嚮往的是「平均值遊戲」,這個桌遊由大小為 $\color{black}{1\times n}\ $ 的方格組成,一格長度只有 $\color{black}{1}\ $ 奈米。在別人的眼裡,這些方格不過是一條線或是一塊一塊的綠豆糕,但 DZ 兩眼的視力高達 $\color{black}{600.0}\ $,他看到的是許多數字。原來這個桌遊的每個方格上面都有一個數字,且一開始皆為 $\color{black}{0}\ $,玩家可以進行許多操作。

玩家可以把其中一個方格的數字換成其他數字,或是選一個區間 $\color{black}{[l,r]}\ $,詢問對手這個區間裡所有子區間的最大平均值,例如 $\color{black}{n=5}\ $,數列為 $\color{black}{[1, 49, 49, 0, 49]}\ $,假設選的區間是 $\color{black}{[2, 4]}\ $,那麼可能的子區間有 $\color{black}{[2, 2], [3, 3], [4, 4], [2, 3], [3, 4], [2, 4]}\ $,選擇區間 $\color{black}{[2, 3]}\ $ 可以得到最大的平均值 $\color{black}{49.0}\ $。

因為 DZ 非常討厭超級常數優化,所以輸入非常少,只會輸入 $\color{black}{n, q, l_0, r_0, p_0, k_0}\ $,$\color{black}{n}\ $ 為數列長度,$\color{black}{q}\ $ 為操作次數,$\color{black}{l_0, r_0, p_0, k_0}\ $ 分別為詢問左界、詢問右界、改值位置與修改數值的初始值。要利用這些數值與之前得到的答案更新這些數值。

因為可能會有改值與詢問兩種操作,假設現在到了第 i 筆操作,那麼如果 $\color{black}{(l_{i}+r_{i}+p_{i}+k_{i})}\ $ 為奇數,代表現在要進行改值,否則要進行詢問。

令 $\color{black}{ans_0 = 0}\ $,$\color{black}{ans_i}\ $ 為第 $\color{black}{i}\ $ 筆詢問的答案向下取整後的結果,如果第 $\color{black}{i}\ $ 筆的操作是改值,那麼令 $\color{black}{ans_i = 0}\ $。$\color{black}{l_i, r_i, p_i, k_i}\ $ 的計算方式如下:

  • $\color{black}{l_i = (71224949 \times l_{i - 1} + 94942217 \times ans_{i - 1} + 12345 \times i + 600 \times r_{i - 1}) \% n + 1}\ $
  • $\color{black}{r_i = (48763 \times r_{i - 1} + 999888 \times ans_{i - 1} + 12345678 \times p_{i - 1})\% n + 1}\ $
  • $\color{black}{p_i = (600600 \times p_{i - 1} + 7777777 \times ans_{i - 1} + 56789 \times k_{i - 1})\% n + 1}\ $
  • $\color{black}{k_i = (88888888 \times k_{i - 1} + 89487 \times ans_{i - 1})\%(10^9+1)}\ $

以上的各種係數皆是經由亂數生成器取得,並無特別涵義。在得到了這些值後,就可以進行操作了,如果現在的操作是改值,那麼把數列的第 $\color{black}{p_i}\ $ 格改成 $\color{black}{k_i}\ $;如果是詢問,那就是詢問 $\color{black}{[min(l_i,r_i),max(l_i,r_i)]}\ $ 區間的答案。

DZ 覺得上面的東西其實只是另一種輸入方法而已,只要照著式子打就好了,並不會很複雜,所以如果只是看到上面式子就不陪 DZ 玩遊戲的人,DZ 就會對你說:「真的是太遜了!」

Input

輸入只有一行,有 $\color{black}{6}\ $ 個數字,$\color{black}{n, q, l_0, r_0, p_0, k_0}\ $,代表數列長度、操作次數、詢問左界的初始值、詢問右界的初始值、改值位置的初始值與修改數值的初始值。

  • $\color{black}{1≤n≤10^9}\ $
  • $\color{black}{1≤q≤2\times 10^6}\ $
  • $\color{black}{1≤l_0,r_0,p_0≤n}\ $
  • $\color{black}{0≤k_0≤10^9}\ $
Output

假設 $\color{black}{q}\ $ 筆操作裡有 $\color{black}{t}\ $ 筆詢問要回答,那麼對這 $\color{black}{t}\ $ 個答案向下取整後可以得到 $\color{black}{ans_{j_1}\sim ans_{j_t}}\ $,其餘的 $\color{black}{q-t}\ $ 筆操作的 $\color{black}{ans}\ $ 皆為 $\color{black}{0}\ $。

因為 DZ 非常討厭超級常數優化,所以只要輸出一行 $\color{black}{ANS}\ $,其中 $\color{black}{ANS = ans_1\ \text{xor}\ ans_2\ \text{xor}\ ... \text{xor}\ ans_q}\ $。

 
Sample Input #1
5 10 9 8 3 7122
Sample Output #1
807677268
測資資訊:
記憶體限制: 100 MB
不公開 測資點#0 (33%): 3.0s , <1K
不公開 測資點#1 (33%): 3.0s , <1K
不公開 測資點#2 (34%): 3.0s , <1K
Hint :

這題雖然是在動態開點線段樹,但目的是要精簡記憶體,以下有幾點可以注意一下,像是盡量使用陣列存取節點,還有我在出題的時候,最後的記憶體用量約 $\color{black}{50\text{MB}}\ $,但是記憶體限制開 $\color{black}{80\text{MB}}\ $ 卻會 $\color{black}{\text{RE}}\ $,開了 $\color{black}{100\text{MB}}\ $ 後才通過,另外,原本開的陣列大小是 $\color{black}{4\times \text{SIZE}}\ $,與之後改的 $\color{black}{2\times \text{SIZE}}\ $,雖然結果都是 $\color{black}{50\text{MB}}\ $,但前面會 $\color{black}{\text{RE}}\ $,後面才會 $\color{black}{\text{AC}}\ $,所以可以注意一下。然後這一題感覺用普通的動態開點方法會 $\color{black}{\text{MLE}}\ $,需要有一些特別的方法來減少記憶體。

-----------------------------------------

$\color{black}{100\%:無特別限制}\ $

Tags:
動態開點 線段樹
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」