c806: 一堆卡片
標籤 :
通過比率 : 67% (2 人 / 3 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-10-23 06:42

內容

$\color{black}{\text{UD}}$ 得到了一些寫著數字的卡片,只要將 $\color{black}{N}$ 張卡片(數字為 $\color{black}{A_1, A_2, \cdots, A_N}$ )堆放在一起,它們就會產生一個奇妙數值 $\color{black}{S}$。

經過實驗,$\color{black}{S = \displaystyle\sum_{i < j}{A_i \space xor \space A_j} = \sum_{i=1}^{n}{\sum_{j=i+1}^{n}{A_i \space xor \space A_j}}}$,也就是任選兩張卡片的 $\color{black}{xor}$ 值之和。

為了觀察數字變化,現在 $\color{black}{\text{UD}}$ 打算更動卡片堆,請你隨時計算新的奇妙數值 $\color{black}{S}$ 。

輸入說明

第一行為操作次數 $\color{black}{M (1 \le M \le 1000000)}$ 。

第 $\color{black}{2 \sim M + 1}$ 行,
若輸入為 $\color{black}{\text{+ c}}$ ,代表放置數值為 $\color{black}{\text{c}}$ 的卡片;
若輸入為 $\color{black}{\text{- c}}$ ,代表抽出數值為 $\color{black}{\text{c}}$ 的卡片。

一開始沒有任何卡片。
保證 $\color{black}{0 \le \text{c} \le 1000000}$ ,且不會抽出不存在的卡片。

輸出說明

輸出 $\color{black}{S}$ (無任何卡片時 $\color{black}{S = 0}$)。

範例輸入
6
+ 1
+ 1
+ 2
- 1
- 1
- 2
範例輸出
0
0
6
3
0
0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
提示 :

第三個操作後,$\color{black}{S = (1 \space xor \space 1) + (1 \space xor \space 2) + (1 \space xor \space 2) = 0 + 3 + 3 = 6}$。

測資點 $\color{black}{00}$,$\color{black}{M \le 100}$。
測資點 $\color{black}{01}$,$\color{black}{M \le 30000, 0 \le c \le 20}$。
測資點 $\color{black}{02}$,沒有抽出卡片的動作。
測資點 $\color{black}{03 \sim 04}$,無特殊限制。

標籤:
出處:
[編輯:
icube (常數爆炸)
]


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