數字範圍很大,我們可以先進行離散化 (其實不用離散化也可以做,請詳見並感謝Wei-Han Chen的留言和他寫的題解呦^_^),注意如果有一個數字$v$,那麼$v+1$也要算進去,$0$也要算進去(想想mex的性質就知道為甚麼)
首先可以想到一種計算方式:把區間的所有value找出來,開一個大小為值域大小的bool陣列,把所有出現的數字設成true,最後,將陣列從小到大掃過去,找出第一個false就是答案
可是,上述計算方式太花時間了,如果我們不開bool陣列,改開int陣列,是否能儲存多餘的資訊呢?
我也不知道怎麼想到的,就儲存「上一個這個數字出現的位置」吧
這樣,如果我們從$A_{1}$到$A_{N}$慢慢把數字加進去,假設現在加到$A_{i}$,那麼對於一個詢問$q$,如果它的右界$q.r=i$(因此可以把詢問依照右界$q.r$排序),就可以直接將陣列從小到大掃過去,找出第一個值$<q.l$的就是答案(代表這個數字上一個出現的位置$<q.l$,也就是不存在於$[q.l,q.r]$這個區間)
掃描陣列有可能花太多時間,我們可以對這個陣列建立一棵維護最小值(最小出現位置)的線段樹,詢問時盡量往左子樹走,同時保持目前區間的最小值$<q.l$,找到底的時候那個位置就是答案
總之
1. 將詢問依照右界排序
2. 建立一棵維護最小出現位置的線段樹,只需支持單點修改並維護區間最小值
3. 對於每個詢問$q$,把所有$A_{i}(i\leq q.r)$拿去更新線段樹,接著盡量往左子樹走,同時保持目前區間的最小值$<q.l$,找到底就是答案
時間複雜度:$O(N\log N)$
code:
#include<cstdio> //#include<cassert> #include<vector> #include<algorithm> using namespace std; const int INF=2147483647; void assert(bool valid){if(valid)return;for(;;)putchar('E');} struct QueryType { int l,r,id; QueryType(){} QueryType(const int _l,const int _r,const int _id):l(_l),r(_r),id(_id){} bool operator<(const QueryType &q)const{return r<q.r;} }; int MN[800001]; void Build(const int id,const int l,const int r) { MN[id]=0; if(l==r)return; const int mid=(l+r)/2; Build(id*2,l,mid),Build(id*2+1,mid+1,r); } void Maintain(const int id){MN[id]=min(MN[id*2],MN[id*2+1]);} void Add(const int id,const int l,const int r,const int loc,const int v) { if(l==r){MN[id]=v;return;} const int mid=(l+r)/2; if(loc<=mid)Add(id*2,l,mid,loc,v); else Add(id*2+1,mid+1,r,loc,v); Maintain(id); } int Query(const int id,const int l,const int r,const int bound) { assert(MN[id]<bound);//保持目前區間最小值<bound if(l==r)return r; const int mid=(l+r)/2; if(MN[id*2]<bound)return Query(id*2,l,mid,bound);//盡量往左子樹走 else return Query(id*2+1,mid+1,r,bound); } int N,M,S[100001],ANS[100000]; vector<int>V; vector<QueryType>Q; int main() { // freopen("in.txt","r",stdin); int testcount;scanf("%d",&testcount); while(testcount--) { int querycount; scanf("%d%d",&N,&querycount); V.clear();V.push_back(0); for(int i=1;i<=N;i++)scanf("%d",&S[i]),V.push_back(S[i]),V.push_back(S[i]+1); sort(V.begin(),V.end()),V.resize(unique(V.begin(),V.end())-V.begin()); for(int i=1;i<=N;i++)S[i]=lower_bound(V.begin(),V.end(),S[i])-V.begin(); M=V.size(); Build(1,0,M-1); Q.clear(); for(int l,r,i=0;i<querycount;i++) { scanf("%d%d",&l,&r); Q.push_back(QueryType(l,r,i)); } sort(Q.begin(),Q.end()); int now=0; for(const QueryType &q:Q) { while(now<q.r)now++,Add(1,0,M-1,S[now],now); assert(now==q.r); ANS[q.id]=Query(1,0,M-1,q.l); } for(int i=0;i<querycount;i++)printf("%d\n",ANS[i]); } assert(scanf("%d",&testcount)!=1); return 0; }
這不一定要離散化吧?
回覆刪除因為區間序列長度最長是10^5,所以只要數值>10^5,那就等於沒有用
那只要建出一個長度固定式10^5的線段樹,維護數值最後出現的位置(跟你的解法一樣),也是OK
真的耶,我都沒有發現XD
刪除感謝你呦,我們又可以把作法變得更簡單了!