Description

在組合游戲中計算狀態的 SG 值時，我們常常會遇到 mex 函數。mex(S) 的值為集合 S 中沒有出現過的最小自然數。例如，mex({1,2}) = 0、mex({0,1,2,3}) = 4。
給定長度為 n 的序列 a。現有 m 次詢問，每次給定 l 和 r，詢問區間 [l,r] 的數構成的集合的 mex 值。

Input

輸入數據的第一行包含三個整數 n、m 和 t，其中 t 為 0 或者 1，表示數據類型。
接下來一行，包含 n 個非負整數，為序列 a。
接下來 m 行，每行描述一個詢問。第 i 行包含兩個正整數 l 和 r，代表第 i 次詢問的區間的左右端點。如果 t = 1，則詢問進行了加密，從第二個詢問開始，讀入的 l 和 r 異或前一次詢問的答案才是真正的詢問左右端點。

Output

對于每個詢問，輸出一行，代表詢問區間的 mex 值。

Sample Input

5 4 0
2 1 0 2 1
3 3
2 3
2 4
1 2

Sample Output

1
2
3
0

Data Constraint

Solution

• 考慮用主席樹的在線做法。

• 主席樹中以值域為下標，存的值為 min{max{posv}}min{max{posv}} ，

• 即當前這個值最后出現的位置在哪里，所有位置的最小值。

• 那么我們查詢區間 [l,r][l,r] 的時候，就查找第 rt[r]rt[r] 棵主席樹，

• 如果左區間的值 ≥l≥l ，說明左區間所有值在詢問區間中都出現過， 就不可能成為答案，

• 于是就遞歸右區間，否則遞歸左區間。

• 有個小優化：當讀入的 ai>nai>n 那它肯定不會成為答案，就干脆不加入了。

• 動態開點，時空復雜度都是 O(N?log?N)O(NlogN) 。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=2e5+5; struct data {int p,l,r; }f[N*19]; int tot,ans,num,pos; int rt[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int min(int x,int y) {return x<y?x:y; } void insert(int pre,int &v,int l,int r) {f[v=++tot]=f[pre];if(l==r){f[v].p=pos;return;}int mid=l+r>>1;if(num<=mid) insert(f[pre].l,f[v].l,l,mid); else insert(f[pre].r,f[v].r,mid+1,r);f[v].p=min(f[f[v].l].p,f[f[v].r].p); } int query(int v,int l,int r) {if(l==r) return l;int mid=l+r>>1;if(f[f[v].l].p>=pos) return query(f[v].r,mid+1,r);return query(f[v].l,l,mid); } int main() {freopen("mex.in","r",stdin);freopen("mex.out","w",stdout);int n=read(),m=read(),t=read();for(int i=1;i<=n;i++){num=read();if(num<=n) insert(rt[i-1],rt[pos=i],0,n); else rt[i]=rt[i-1];}while(m--){int l=read(),r=read();if(t) l^=ans,r^=ans;pos=l;ans=query(rt[r],0,n);write(ans),putchar('\n');}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ 5710. 【北大夏令营2018模拟5.13】Mex的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。