Codefroces 374 B Inna and Sequence (树状数组 || 线段树）

Inna and Sequence

题意：先给你一个n,一个m，然后接下来输入m个数，表示每次拳击会掉出数的位置，然后输入n个数，每次输入1或0在数列的末尾加上1或0，如果输入-1，相应m序列的数的位置就会掉出来并且后面的数会向前补位（每次删除操作可以看作是同时进行的，只有删除结束之后才会进行补位），最后输出这个数列的剩下结果，如果数列为空就输出“Poor stack!”。

题解：一开始想到的思路还是和上次CF889F想到的一样，在删除的位置标记一下，然后每次2分去查找在前面删除操作之后现在需要删除的位置对应哪里，然后再进行相应的位置，注意的就是，要么从后往前删除，且用二分去查找开始的第一个点，因为m序列如果太大的话，每次删除都会有很多时间浪费在不能删除的位置上；要么就是先把每次对应的全部位置找出来，再进行删除，因为每次删除都会对后面的删除产生影响。

 #include<cstdio>

 using namespace std;

 const int N = 1e6+;

 int n, m, R;

 int tree[N], a[N];

 int ans[N];

 int lowbit(int x)

 {

     return x&(-x);

 }

 void Add(int x)

 {

     while(x <= n)

     {

         tree[x]++;

         x += lowbit(x);

     }

 }

 int Query(int x)

 {

     int ret = ;

     while(x > )

     {

         ret += tree[x];

         x -= lowbit(x);

     }

     return ret;

 }

 int Find_pos(int pos)//找到以前删除之后的补位之后的对应位置

 {

     int l = pos, r = R;

     while(l <= r)

     {

         int mid = l+r >> ;

         int num = Query(mid);

         if(mid == num + pos && ans[mid] != -)

         {

             return mid;

         }

         else if(mid < num+ pos) l = mid+;

         else r = mid - ;

     }

 }

 void Delete()

 {

     int l = , r = m;

     int len = R - Query(R);

     while(l <= r)//2分寻找每次开始删除的位置，倒着删除

     {

         int mid = l + r >> ;

         if(len >= a[mid]) l = mid+;

         else r = mid-;

     }

     for(int i = l-; i > ; i--)

     {

         int pos = Find_pos(a[i]);

         ans[pos] = -;

         Add(pos);

     }

 }

 int main()

 {

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

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

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

     R = ;

     int t;

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

     {

         scanf("%d",&t);

         if(t == -)

             Delete();

         else ans[++R] = t;

     }

     if(R - Query(R) == ) printf("Poor stack!\n");

     else

     {

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

         {

             if(ans[i]  == -) continue;

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

         }

     }

     return ;

 }

然后上面那个思路竟然被队长说TLE, 然后最后修改了n发，最终走到了和下面这个版本耗时差不多的慢几十ms的线段树版本操作。

开一棵线段树保存有效长度，然后每次通过有效长度去删除就好了。同时可以将m序列转化成有效长度，将删除数组的每一位减去前面的个数，就可以从头开始进行删除操作，

因为你每删除一次数据，有效长度就会减一，所以如果轮到第m个数，那么对于刚开始删除的序列的有效长度就已经减去m-1了。

 #include<cstdio>

 #define lson l,m,rt<<1

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

 using namespace std;

 const int N = 1e6+;

 int n, m;

 int tree[N<<], ans[N], Delt[N];

 void Add(int L,int C,int l, int r, int rt)

 {

     tree[rt]++;

     if(l == r)

     {

         ans[l]  = C;

         return ;

     }

     int m = l+r >> ;

     if(L <= m) Add(L,C,lson);

     else Add(L,C,rson);

 }

 void Delete(int Num, int l, int r, int rt)

 {

     tree[rt]--;

     if(l == r)

     {

         ans[l] = -;

         return ;

     }

     int m = l+r >> ;

     if(tree[rt<<] >= Num) Delete(Num, lson);

     else Delete(Num-tree[rt<<],rson);

 }

 int main()

 {

     //ios::sync_with_stdio(false);

     //cin.tie(0);

     //cout.tie(0);

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

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

     {

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

         Delt[i] -= i;//将位置转化成长度

     }

     int tot = ;

     int tmp;

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

     {

         scanf("%d",&tmp);

         if(tmp != -)

             Add(++tot,tmp,,n,);

         else

         {

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

             {

                 if(tree[] < Delt[i]) break;

                 else Delete(Delt[i],,n,);

             }

         }

     }

     if(tree[] == ) printf("Poor stack!\n");

     else

     {

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

             if(ans[i] != -)

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

     }

     return ;

 }

巴特西

Codefroces 374 B Inna and Sequence (树状数组 || 线段树）

最新文章

热门文章