【HDU4967】Handling the Past

题意

模拟栈操作。有三种操作push,pop,peak分别代表从栈顶压入元素，删除栈顶元素，查询栈顶元素。但是，每个操作会给出一个时间戳，要求操作必须要按照时间戳来进行。但是对于每个peak必须马上给出查询结果。其中n<=50000,xi,ti<=1e9

分析

讲真，这种题必须结合样例才能明白让干嘛。如果暴力的话，对于每个peak的时间复杂度都是O(n)。所以我们想到了线段树。

1.因为t的值很大，所以我们要首先将t离散化（我因为离散化写丑了一开始还T了好几发）

2.将每个push的t和x对应的记录下来

3.对于每个操作push，我们在t的位置插入1，对于每个pop操作，我们在t的位置插入-1。对于每个peak操作，我们找到t左边的第一个t1，符合sum(t1 to t)>0,这时候和t1对应的x值就是答案。

思路是很好想的，然后就是操作3该怎么通过线段树来维护？

我们通过线段树来维护一个区间和，和一个最大后缀和，然后对于没个peak查询，所有从1到t的线段树的结点，从右往左找，如果加上当前结点的最大后缀和大于0的话，这个答案就一定在这个节点内，否则加上这个结点的区间和继续往左找。这里可以结合代码进行理解。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <map>

 using namespace std;

 const int maxn=+;

 struct Ope{

     string name;

     int t,a;

 }ope[maxn];

 int n,kase;

 int V[maxn],M[maxn];

 int sumv[*maxn],max_suff[*maxn];

 int v,x;

 void maintain(int o){

     sumv[o]=sumv[*o]+sumv[*o+];

     max_suff[o]=max(max_suff[*o+],sumv[*o+]+max_suff[*o]);

 }

 void update(int o,int L,int R){

     if(L==R){

         sumv[o]+=x;

         max_suff[o]+=x;

         return ;

     }

     int M=L+(R-L)/;

     if(v<=M)update(*o,L,M);

     if(v>M)update(*o+,M+,R);

     maintain(o);

     return;

 }

 int tot,ans;

 int ql,qr;

 void solve(int o,int L,int R){

     if(L==R){

         ans=L;

         return;

     }

     int M=L+(R-L)/;

     if(tot+max_suff[*o+]>)

       return solve(*o+,M+,R);

     tot+=sumv[*o+];

     return solve(*o,L,M);

 }

 void query(int o,int L,int R){

     if(ans!=-)

         return;

     if(ql<=L&&qr>=R){

         if(tot+max_suff[o]>){

             solve(o,L,R);

         }

         else tot+=sumv[o];

         return;

     }

     int M=L+(R-L)/;

     if(M<qr)

         query(*o+,M+,R);

     if(M>=ql)

         query(*o,L,M);

     return;

 }

 int main(){

     kase=;

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

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

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

             cin>>ope[i].name;

             if(ope[i].name=="push"){

                 scanf("%d%d",&ope[i].a,&ope[i].t);

             }

             if(ope[i].name=="pop"||ope[i].name=="peak"){

                 scanf("%d",&ope[i].t);

             }

             V[i]=ope[i].t;

         }

         sort(V+,V++n);

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

             if(ope[i].name=="push"){

                 int tt=lower_bound(V+,V++n,ope[i].t)-V;

                 M[tt]=ope[i].a;

             }

         }

        /* for(int i=1;i<=n;i++){

             int tt=lower_bound(V+1,V+1+n,ope[i].t)-V;

             cout<<tt<<endl;

         }*/

         memset(sumv,,sizeof(sumv));

         memset(max_suff,,sizeof(max_suff));

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

             if(ope[i].name=="push"){

                 v=lower_bound(V+,V++n,ope[i].t)-V;

                 x=;

                 update(,,n);

             }

             else if(ope[i].name=="pop"){

                 v=lower_bound(V+,V++n,ope[i].t)-V;

                 x=-;

                 update(,,n);

             }

             else{

                 ql=,qr=lower_bound(V+,V++n,ope[i].t)-V;

                 tot=,ans=-;

                 query(,,n);

                 printf("%d\n",ans==-?-:M[ans]);

             }

         }

     }

 return ;

 }

巴特西

【HDU4967】Handling the Past

最新文章

热门文章