2016年2月5日 星期五

[IOI Camp Judge 26]區間MEX

IOI Camp Judge是暫時性的,因此我在這裡做了題目備份

數字範圍很大,我們可以先進行離散化 (其實不用離散化也可以做,請詳見並感謝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;
}

2 則留言:

  1. 這不一定要離散化吧?

    因為區間序列長度最長是10^5,所以只要數值>10^5,那就等於沒有用

    那只要建出一個長度固定式10^5的線段樹,維護數值最後出現的位置(跟你的解法一樣),也是OK

    回覆刪除
    回覆
    1. 真的耶,我都沒有發現XD
      感謝你呦,我們又可以把作法變得更簡單了!

      刪除

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原