3339: Rmq Problem

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 1075  Solved: 549

[][][]

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

 

 

Source

[ ][ ][ ]

 

和 一模一样，代码不变，AC依旧。

 

1 #include 
     
       2  3 const int mxn = 200005; 4  5 int n, m, num[mxn], nxt[mxn], lst[mxn], mex[mxn], vis[mxn], ans[mxn]; 6  7 struct query { 8     int l, r, t; 9 }q[mxn];10 11 inline bool cmp(const query &a, const query &b)12 {13     return a.l < b.l;14 }15 16 signed main(void)17 {18     scanf("%d%d", &n, &m);19     20     for (int i = 1; i <= n; ++i)21     {22         scanf("%d", num + i);23         if (num[i] > n)24             num[i] = n;25     }26     27     for (int i = 0; i <= n; ++i)28         lst[i] = n + 1;29     30     for (int i = n; i >= 1; --i)31         nxt[i] = lst[num[i]], lst[num[i]] = i;32         33     for (int i = 1; i <= n; ++i)34     {35         mex[i] = mex[i - 1];36         vis[num[i]] = true;37         while (vis[mex[i]])38             ++mex[i];39     }40     41     for (int i = 1; i <= m; ++i)42         scanf("%d%d", &q[i].l, &q[i].r), q[i].t = i;43     44     std::sort(q + 1, q + m + 1, cmp);45     46     int left = 1;47     48     for (int i = 1; i <= m; ++i)49     {50         while (left < q[i].l)51         {52             int t = nxt[left];53             int p = num[left];54             for (int j = t - 1; j > left; --j)55             {56                 if (mex[j] <= p)break;57                 else mex[j] = p;58             }59             ++left;60         }61         62         ans[q[i].t] = mex[q[i].r];63     }64     65     for (int i = 1; i <= m; ++i)66         printf("%d\n", ans[i]);67 }
     

 

@Author: YouSiki