Inna and Sequence
题意：先给你一个n,一个m， 然后接下来输入m个数，表示每次拳击会掉出数的位置，然后输入n个数，每次输入1或0在数列的末尾加上1或0，如果输入-1，相应m序列的数的位置就会掉出来并且后面的数会向前补位（每次删除操作可以看作是同时进行的，只有删除结束之后才会进行补位），最后输出这个数列的剩下结果，如果数列为空就输出“Poor stack!”。
题解：一开始想到的思路还是和上次CF889F想到的一样，在删除的位置标记一下，然后每次2分去查找在前面删除操作之后现在需要删除的位置对应哪里，然后再进行相应的位置，注意的就是，要么从后往前删除，且用二分去查找开始的第一个点，因为m序列如果太大的话，每次删除都会有很多时间浪费在不能删除的位置上； 要么就是先把每次对应的全部位置找出来，再进行删除，因为每次删除都会对后面的删除产生影响。
1 #include2 using namespace std; 3 const int N = 1e6+10; 4 int n, m, R; 5 int tree[N], a[N]; 6 int ans[N]; 7 int lowbit(int x) 8 { 9 return x&(-x);10 }11 void Add(int x)12 {13 while(x <= n)14 {15 tree[x]++;16 x += lowbit(x);17 }18 }19 int Query(int x)20 {21 int ret = 0;22 while(x > 0)23 {24 ret += tree[x];25 x -= lowbit(x);26 }27 return ret;28 }29 int Find_pos(int pos)//找到以前删除之后的补位之后的对应位置30 {31 int l = pos, r = R;32 while(l <= r)33 {34 int mid = l+r >> 1;35 int num = Query(mid);36 if(mid == num + pos && ans[mid] != -1)37 {38 return mid;39 }40 else if(mid < num+ pos) l = mid+1;41 else r = mid - 1;42 }43 }44 void Delete()45 {46 int l = 1, r = m;47 int len = R - Query(R);48 while(l <= r)//2分寻找每次开始删除的位置，倒着删除49 {50 int mid = l + r >> 1;51 if(len >= a[mid]) l = mid+1;52 else r = mid-1;53 }54 for(int i = l-1; i > 0; i--)55 {56 int pos = Find_pos(a[i]);57 ans[pos] = -1;58 Add(pos);59 }60 }61 int main()62 {63 scanf("%d%d",&n,&m);64 for(int i = 1; i <= m; i++)65 scanf("%d",&a[i]);66 R = 0;67 int t;68 for(int i = 1; i <= n; i++)69 {70 scanf("%d",&t);71 if(t == -1)72 Delete();73 else ans[++R] = t;74 }75 if(R - Query(R) == 0) printf("Poor stack!\n");76 else77 {78 for(int i = 1; i <= R; i++)79 {80 if(ans[i] == -1) continue;81 printf("%d",ans[i]);82 }83 }84 return 0;85 }
然后上面那个思路竟然被队长说TLE, 然后最后修改了n发，最终走到了和下面这个版本耗时差不多的慢几十ms的线段树版本操作。
开一棵线段树保存有效长度，然后每次通过有效长度去删除就好了。同时可以将m序列转化成有效长度，将删除数组的每一位减去前面的个数，就可以从头开始进行删除操作，
因为你每删除一次数据，有效长度就会减一，所以如果轮到第m个数，那么对于刚开始删除的序列的有效长度就已经减去m-1了。
1 #include2 #define lson l,m,rt<<1 3 #define rson m+1,r,rt<<1|1 4 using namespace std; 5 const int N = 1e6+10; 6 int n, m; 7 int tree[N<<2], ans[N], Delt[N]; 8 void Add(int L,int C,int l, int r, int rt) 9 {10 tree[rt]++;11 if(l == r)12 {13 ans[l] = C;14 return ;15 }16 int m = l+r >> 1;17 if(L <= m) Add(L,C,lson);18 else Add(L,C,rson);19 }20 void Delete(int Num, int l, int r, int rt)21 {22 tree[rt]--;23 if(l == r)24 {25 ans[l] = -1;26 return ;27 }28 int m = l+r >> 1;29 if(tree[rt<<1] >= Num) Delete(Num, lson);30 else Delete(Num-tree[rt<<1],rson);31 }32 int main()33 {34 //ios::sync_with_stdio(false);35 //cin.tie(0);36 //cout.tie(0);37 scanf("%d%d",&n,&m);38 for(int i = 0; i < m; i++)39 {40 scanf("%d",&Delt[i]);41 Delt[i] -= i;//将位置转化成长度42 }43 int tot = 0;44 int tmp;45 for(int i = 1; i <= n; i++)46 {47 scanf("%d",&tmp);48 if(tmp != -1)49 Add(++tot,tmp,1,n,1);50 else51 {52 for(int i = 0; i < m; i++)53 {54 if(tree[1] < Delt[i]) break;55 else Delete(Delt[i],1,n,1);56 }57 }58 }59 if(tree[1] == 0) printf("Poor stack!\n");60 else61 {62 for(int i = 1; i <= tot; i++)63 if(ans[i] != -1)64 printf("%d",ans[i]);65 }66 return 0;67 }