hdu3436Queue-jumpers（线段树）

这题最不好求的一部分是rank部分因为top每次都是把一个数放在队头不会穿插在数组里也就是说后面没有top过的一部分数依旧保持有序

这样可以分为两部分来处理比如 1 2 3 4 5 6 7 TOP 3 TOP 5 TOP 7后会是这么一种状态 7 5 3 1 2 4 6 这样可以建立两颗线段树一个处理前面一个处理后面

对于N 值很大肯定是需要离散化的前面的那颗就可以用普通的求第k大标记求和来求出第几以及x在哪个位置后面的线段树的值可以这么来表示 s[w] = num[i]-num[i-1]

这样对于询问rank x 就用线段树找第一个大于等于x的数。

虽然错了很多次，看见那个红红的AC还是很高兴的。。。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 struct node

 {

     char s[];

     int d;

 }p[N];

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

 int po[N],fo[N],a[N];

 bool vis[N];

 map<int,int>f;

 void up(int w)

 {

     s[w] = s[w<<]+s[w<<|];

 }

 void up1(int w)

 {

     ss[w] = ss[w<<]+ss[w<<|];

     oo[w] = oo[w<<]+oo[w<<|];

 }

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

 {

     if(l==r)

     {

         s[w] = oo[w] = ;

         if(fo[l]>fo[l-])

         ss[w] = fo[l]-fo[l-];

         return ;

     }

     int m= (l+r)>>;

     build(l,m,w<<);

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

     up(w);

     up1(w);

 }

 void update(int pos,int k,int d,int l,int r,int w)

 {

     if(l==r)

     {

         s[w] = d;

         if(d)

         {

             po[k] = l;

             o[w] = fo[k];

            // cout<<k<<" "<<fo[k]<<endl;

         }

         return ;

     }

     int m = (l+r)>>;

     if(pos>m) update(pos,k,d,m+,r,w<<|);

     else update(pos,k,d,l,m,w<<);

     up(w);

 }

 void update1(int k,int l,int r,int w)

 {

     if(l==r)

     {

         ss[w]--;

         oo[w] = ;

         return ;

     }

     int m = (l+r)>>;

     if(k>m) update1(k,m+,r,w<<|);

     else update1(k,l,m,w<<);

     up1(w);

 }

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

 {

     if(l==r)

     {

         return o[w];

     }

     int m = (l+r)>>;

     if(p>s[w<<]) return query(p-s[w<<],m+,r,w<<|);

     else return query(p,l,m,w<<);

 }

 int query1(int p,int l,int r,int w)

 {//cout<<l<<" "<<r<<" "<<ss[w]<<" "<<p<<endl;

     if(l==r)

     {

         //cout<<l<<endl;

         if(vis[l])

         return fo[l]--(ss[w]-p);

         else

         return fo[l]-(ss[w]-p);

     }

     int m = (l+r)>>;

     if(p<=ss[w<<])

     return query1(p,l,m,w<<);

     else

     return query1(p-ss[w<<],m+,r,w<<|);

 }

 int getsum(int a,int b,int l,int r,int w)

 {

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

     return s[w];

     int m = (l+r)>>;

     int re = ;

     if(a<=m)

     re+=getsum(a,b,l,m,w<<);

     if(b>m)

     re+=getsum(a,b,m+,r,w<<|);

     return re;

 }

 int getsum1(int a,int b,int l,int r,int w)

 {

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

     return oo[w];

     int m = (l+r)>>;

     int re = ;

     if(a<=m)

     re+=getsum1(a,b,l,m,w<<);

     if(b>m)

     re+=getsum1(a,b,m+,r,w<<|);

     return re;

 }

 int main()

 {

     int i,n,q,kk=,t;

     cin>>t;

     while(t--)

     {

         memset(vis,,sizeof(vis));

         memset(fo,,sizeof(fo));

         memset(o,,sizeof(o));

         f.clear();

         scanf("%d%d",&n,&q);

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

         {

             scanf("%s%d",p[i].s,&p[i].d);

             a[i] = p[i].d;

         }

         sort(a,a+q);

         int g = ;

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

         {

             if(!f[a[i]])

             {

                 g++;

                 f[a[i]] = g;

                 fo[g] = a[i];

                 //cout<<g<<" "<<a[i]<<endl;

             }

         }

         g++;

         f[n+] = g;

         fo[g] = n+;

         g = q+;

         build(,g,);

         int e = g+;

         printf("Case %d:\n",++kk);

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

         {

             int k = f[p[i].d];

             if(strcmp(p[i].s,"Top")==)

             {

                 e--;

                 if(vis[k])

                     update(po[k],k,,,g,);

                 else

                     update1(k,,g,);

                 update(e,k,,,g,);

                 vis[k]= ;

             }

             else if(strcmp(p[i].s,"Rank")==)

             {

                 //int sum = getsum(1,g,1,g,1);

                 //cout<<s[1]<<endl;

                //cout<<getsum1(1,2,1,g,1)<<endl;

                 if(p[i].d>s[])

                 {

                     int cnt = query1(p[i].d-s[],,g,);

                     printf("%d\n",cnt);

                 }

                 else

                 {

                     printf("%d\n",query(p[i].d,,g,));

                 }

             }

             else

             {

                 if(vis[k])

                 {

                     int cnt = getsum(,po[k],,g,);

                     //cout<<po[k]<<endl;

                     printf("%d\n",cnt);

                 }

                 else

                 {

                     if(k==g)

                     cout<<p[i].d<<endl;

                     else

                     {

                         int cnt = getsum1(k+,g,,g,);

                         printf("%d\n",cnt+p[i].d);

                     }

                 }

             }

         }

     }

     return ;

 }

巴特西

hdu3436Queue-jumpers（线段树）

最新文章

热门文章