Codeforces Round #803 (Div. 2)
05:45:22 |
Codeforces Round #804 (Div. 2)
7 өдрийн дараа |
D. Васили-ын Мулти олонлог
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Бодлогын зохиолч Васили-ын талаарх түүхүүд бичихээс залхсан учраас энэ удаад энгийн нэгэн бодлогын өгүүлбэр бичив.
Танд $q$ ширхэг асуулт болон Мулти олонлог $A$ өгөгдөх бөгөөд анхандаа уг Мулти олонлог нь зөвхөн $0$ гэсэн бүхэл тоог агуулж байв. Нийтдээ 3-н төрлийн асуултууд байна:
- "+ x" -- Мулти олонлог $A$ дээр бүхэл тоо $x$-г нэмж оруулна.
- "- x" -- Мулти олонлог $A$-аас бүхэл тоо $x$-ын нэг удаа хасна (хэрэв уг олонлогт 2 ширхэг $x$ бүхэл тоо байсан бол уг үйлдлийн дараа нэг $x$ нь олонлогтоо үлдэх юм). Мөн уг үйлдлийг хийхээс өмнө Мулти олонлог $A$ дотор дор хаяж нэг ширхэг $x$ бүхэл тоо оршин байна.
- "? x" -- танд $x$ бүхэл тоо өгөгдөх ба та
-ын утгыг тооцоолох хэрэгтэй, өөрөөр хэлбэл бүхэл тоо $x$ болон Мулти олонлог $A$ доторх ямар нэгэн бүхэл тоо $y$-ын битийн онцгой OR (өөрөөр хэлбэл XOR) үйлдлийн хамгийн их утгыг олох юм.
Мулти олонлог гэдэг нь тэнцүү элементүүдийг агуулж болдог олонлогийг хэлнэ.
Оролт
Оролтын эхний мөрөнд бүхэл тоо $q$ ($1 ≤ q ≤ 200 000$) өгөгдөх ба энэ нь Васили-ын гүйцэтгэх ёстой асуултуудын тоог илэрхийлнэ.
Дараагийн $q$ ширхэг мөрийн мөр болгонд '+', '-' эсвэл '?' гэсэн 3 тэмдэгтийн аль нэг тэмдэгт мөн бүхэл тоо $x_{i}$ ($1 ≤ x_{i} ≤ 10^{9}$) өгөгдөнө. Мөн дор хаяж нэг ширхэг 3-р төрлийн асуулт өгөгдөх юм.
Бүхэл тоо $0$ нь $A$ олонлог дотор үргэлж байхыг анхаарна уу.
Гаралт
'?' гэсэн хэлбэртэй өгөгдсөн (өөрөөр хэлбэл 3-р төрлийн асуулт) асуулт бүрийн хувьд бүхэл тоо $x_{i}$ болон Мулти олонлог $A$ доторх ямар нэгэн бүхэл тооны битийн онцгой OR (өөрөөр хэлбэл XOR) үйлдлийн хамгийн их утгыг хэвлэнэ үү.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11
Гаралт
11 10 14 13
Тэмдэглэл
Эхний 5-н асуултыг гүйцэтгэсний дараагаар Мулти олонлог $A$ нь $0$, $8$, $9$, $11$, $6$ болон $1$ гэсэн бүхэл тоонуудыг агуулна.
Түүнчлэн 6-дахь асуултын хариулт нь ,
,
,
болон
гэсэн бүхэл тоонуудаас их бүхэл тоо нь буюу
байх юм.