小藍最近學(xué)習了一種神奇的隊列:分布式隊列。簡單來說,分布式隊列包含 N 個節(jié)點(編號為 0 至 N ? 1,其中 0 號為主節(jié)點),其中只有一個主節(jié)點,其余為副節(jié)點。主/副節(jié)點中都各自維護著一個隊列,當往分布式隊列中添加元素時都是由主節(jié)點完成的(每次都會添加元素到隊列尾部);副節(jié)點只負責同步主節(jié)點中的隊列??梢哉J為主/副節(jié)點中的隊列是一個長度無限的一維數(shù)組,下標為 0, 1, 2, 3 . . . ,同時副節(jié)點中的元素的同步順序和主節(jié)點中的元素添加順序保持一致。
由于副本的同步速度各異,因此為了保障數(shù)據(jù)的一致性,元素添加到主節(jié)點后,需要同步到所有的副節(jié)點后,才具有可見性。
給出一個分布式隊列的運行狀態(tài),所有的操作都按輸入順序執(zhí)行。你需要回答在某個時刻,隊列中有多少個元素具有可見性。
第一行包含一個整數(shù) N,表示節(jié)點個數(shù)。接下來包含多行輸入,每一行包含一個操作,操作類型共有以下三種:add、sync 和 query,各自的輸入格式如下:
1. add element:表示這是一個添加操作,將元素 element 添加到隊列中;
2. sync follower_id:表示這是一個同步操作,follower_id 號副節(jié)點會從主節(jié)點中同步下一個自己缺失的元素;
3. query:查詢操作,詢問當前分布式隊列中有多少個元素具有可見性。
3 add 1 add 2 query add 1 sync 1 sync 1 sync 2 query sync 1 query sync 2 sync 2 sync 1 query
0 1 1 3
【樣例說明】
執(zhí)行到第一個 query 時,隊列內(nèi)容如下:
0:[1,2]1:[1,2]
2:[1]
只有下標為 0 的元素被所有節(jié)點同步,因此答案為 1。執(zhí)行到第三個 query 時,隊列內(nèi)容如下:0:[1,2,1]1:[1,2,1]2:[1]
只有下標為 0 的元素被所有節(jié)點同步,因此答案為 1。執(zhí)行到第四個 query 時,隊列內(nèi)容如下:0:[1,2,1]1:[1,2,1]2:[1,2,1]
三個元素都被所有節(jié)點同步,因此答案為 3。
【評測用例規(guī)模與約定】
對于 30% 的評測用例:1 ≤ 輸入的操作數(shù) ≤ 100。
對于 100% 的評測用例:1 ≤ 輸入的操作數(shù) ≤ 2000,1 ≤ N ≤ 10,1 ≤f ollower_id < N,0 ≤ element ≤ 105。
2024年第十五屆藍橋杯第一次比賽真題,。。。。。。。。。。。。
參加下周比賽的同學(xué)可以做一下,體會一下類型和難度