【bzoj3339】Rmq Problem

Description

Input

Output

Sample Input

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Sample Output

3
0
3
2
4

HINT

分析

离线算法。

对于[l,r]区间的询问，我们可以线性求出来，然后考虑[l,r]与[l+1,r]区间有什么不同，在a[l]下一次出现的位置之前，所有大于a[l]的mex，都变成是a[l]，因为 [l+1,a[l]下一次出现的位置-1]，这个区间内没有a[l]了，大于它的数当然可以是它。

所以将询问的先按左端点排序，然后递增左端点，不断更新，用线段树维护。

code

 #include<cstdio>

 #include<algorithm>

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 using namespace std;

 const int MAXN = ;

 const int INF = 1e9;

 struct Que{

     int l,r,id;

     bool operator < (const Que &x) const

     {

         return l < x.l;

     }

 }q[MAXN];

 int a[MAXN],sg[MAXN],mn[MAXN<<];

 int next[MAXN],last[MAXN],ans[MAXN];

 bool vis[MAXN];

 int n,m,k = ,now;

 int read()

 {

     int x=;char ch=getchar();

     while(ch<''||ch>'') {ch=getchar(); }

     while(ch>=''&&ch<='') {x=x*+ch-''; ch=getchar(); }

     return x;

 }

 void pushdown(int rt)

 {

     if (mn[rt]!=INF)

     {

         mn[rt<<] = min(mn[rt],mn[rt<<]);

         mn[rt<<|] = min(mn[rt],mn[rt<<|]);

     }

 }

 void build(int l,int r,int rt)

 {

     mn[rt] = INF;

     if (l==r)

     {

         mn[rt] = sg[l];

         return ;

     }

     int m = (l+r)>>;

     build(lson);

     build(rson);

 }

 void update(int l,int r,int rt,int L,int R,int v)

 {

     if (L<=l&&r<=R)

     {

         mn[rt] = min(mn[rt],v);

         return ;

     }

     pushdown(rt);

     int m = (l+r)>>;

     if (L<=m) update(lson,L,R,v);

     if (R>m)  update(rson,L,R,v);

 }

 int query(int l,int r,int rt,int p)

 {

     if (l==r) return mn[rt];

     pushdown(rt);

     int m = (l+r)>>;

     if (p<=m) return query(lson,p);

     else return query(rson,p);

 }

 int main()

 {

     n = read();m = read();

     for (int i=; i<=n; ++i)

         a[i] = read();

     for (int i=;i<=m; ++i)

         q[i].l = read(), q[i].r = read(), q[i].id = i;

     sort(q+,q+m+);

     for (int i=; i<=n; ++i)

     {

         vis[a[i]] = true;

         while (vis[k]) k++;

         sg[i] = k;

     }

     build(,n,);

     for (int i=n; i; --i)

         next[i] = last[a[i]], last[a[i]] = i;

     now = ;

     for (int i=; i<=m; ++i)

     {

         while (now<q[i].l)

         {

             if (!next[now]) next[now] = n+;

             update(,n,,now,next[now]-,a[now]);

             now++;

         }

         ans[q[i].id] = query(,n,,q[i].r);

     }

     for (int i=; i<=m; ++i)

         printf("%d\n",ans[i]);

     return ;

 }

（……）

巴特西

【bzoj3339】Rmq Problem

【bzoj3339】Rmq Problem

Description

Input

Output

Sample Input

Sample Output

HINT

分析

code

最新文章

热门文章