UVA6531Go up the ultras

这题意甚是难懂。。当且峰值为h 如果他能为ultras 需要满足条件 d>=15W d满足它到任意一个比它高的点须经过h-d这个点

通俗一点来说，如果这个点满足条件就找离他最近的一个<=h-15W的点看他们之间是否有比它更高的点如果没有的话它就满足条件需要左右两边找。

用线段树依次插入点值位置为节点值更新最大值及最小值。

需要离散化卡时间。。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<cmath>

 using namespace std;

 #define N 1000010

 #define M 100010

 int s[N<<],ss[N<<];

 int h[M],o[M],n,p[N],hi[M<<];

 bool f[M],ff[N];

 void update(int oo,int p,int d,int l,int r,int w)

 {

     if(l==r)

     {

         if(oo)

         s[w] = d;

         else

         ss[w] = d;

         return ;

     }

     int m = (l+r)>>;

     if(p<=m)

     update(oo,p,d,l,m,w<<);

     else

     update(oo,p,d,m+,r,w<<|);

     if(oo)

     s[w] = max(s[w<<],s[w<<|]);

     else

     ss[w] = min(ss[w<<],ss[w<<|]);

 }

 int query(int oo,int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         if(oo)

         return s[w];

         else

         return ss[w];

     }

     int m = (l+r)>>,re;

     if(oo)

     {

         re = ;

         if(a<=m)

         re = query(oo,a,b,l,m,w<<);

         if(b>m)

         re = max(re,query(oo,a,b,m+,r,w<<|));

     }

     else

     {

         re = n+;

         if(a<=m)

         re = query(oo,a,b,l,m,w<<);

         if(b>m)

         re = min(re,query(oo,a,b,m+,r,w<<|));

     }

     return re;

 }

 void build(int l,int r,int w,int oo)

 {

     if(l==r)

     {

         if(oo)

         s[w] = ;

         else

         ss[w] = n+;

         return ;

     }

     int m = (l+r)>>;

     build(l,m,w<<,oo);

     build(m+,r,w<<|,oo);

     if(oo)

     s[w] = max(s[w<<],s[w<<|]);

     else

     ss[w] = min(ss[w<<],ss[w<<|]);

 }

 int main()

 {

     int i;

     int hh = ,num=;

     while(scanf("%d",&n)!=EOF)

     {

         memset(f,,sizeof(f));

         memset(ff,,sizeof(ff));

         int mm = ,e = ;

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

         {

             scanf("%d",&h[i]);

             if(!ff[h[i]])

             {

                 hi[e++] = h[i];

                 ff[h[i]] = ;

             }

             if(h[i]>hh)

             {

                 if(!ff[h[i]-hh])

                 hi[e++] = h[i]-hh;

                 ff[h[i]-hh] = ;

             }

         }

         sort(hi,hi+e);

         int ko = ;

         for(i = ;i < e; i++)

         {

             p[hi[i]] = ++ko;

         }

         mm = ko+;

         build(,mm,,);

         update(,,,,mm,);

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

         {

             if(h[i]<=hh)

             {

                 update(,p[h[i]],i,,mm,);

                 continue;

             }

             if(h[i]>=h[i-]&&h[i]>=h[i+])

             {

                 f[i] = ;

                 int k1 = query(,,p[h[i]-hh],,mm,);

                 int k2 = query(,p[h[i]]+,mm,,mm,);

                 if(k2)

                 {

                     if(!k1||k2>k1)

                     f[i] = ;

                 }

             }

             update(,p[h[i]],i,,mm,);

         }

         build(,mm,,);

         update(,,n,,mm,);

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

         {

             if(f[i])

             {

                 int k1 = query(,,p[h[i]-hh],,mm,);

                 int k2 = query(,p[h[i]]+,mm,,mm,);

                 if(k2!=n+)

                 {

                     if(k1==n+||k2<k1)

                     f[i] = ;

                 }

             }

             update(,p[h[i]],i,,mm,);

         }

         int g = ;

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

         if(f[i])

         o[++g] = i;

         for(i =  ; i < g; i++)

         printf("%d ",o[i]);

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

     }

     return ;

 }

 /*

 26

 0 50000 150000 200000 150000

 200000 300000 100000 50000 150000 330000 350000

  250000 350000 200000 220000 300000 50000 100000

 250000 100000 150000 500000 300000 250000 0

 */

巴特西

UVA6531Go up the ultras

最新文章

热门文章