CodeforcesRound#220(Div.2)D树状数组&&二分_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#220(Div.2)D树状数组&&二分_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2604字，纯文字阅读大概需要4分钟。
内容图文
/*题目*/
题意：给了n,m,然后一个包含m个数的数组nnum，数组默认从小到大排序，然后是 n个操作，输入一个数x，若x为0，把0加到这个字符串的末尾，若x为1，把1加到这个字符串的末尾，若x为-1，那么把字符串里的 下标 与 nnum数组里的元素相等的 给删除，字符串一开始是空的，问你最后字符串里有什么，若为空 就输出 POOR STACK
这题目看这操作一般都很容易联想到线段树，树状数组，一开始我建了个树状数组，但是超时了，毕竟操作很多，而且 在删除操作里，若nnum数组很大，等同于10^12的复杂度，只能优化，一般来说是用二分了，直接以这个串的某个位置是否为空来建立树状数组，每一次加在最后就不用说了，直接加就可以，关键在于删除，首先删除，要第一步二分查找出 要删除的最后一位，比如字符串长度为7，而nnum数组里 有个8，其实8这个位置不需要删除的，但是这个还是超时，于是想到在树状数组里删除的时候也需要二分，可是写了一直错，后来借鉴了杰哥的发现，原来WA在这里，比如 当前字符串为01010，需要删除 1，3，4位置的字符，要轮着来，当你删除1号位置的时候，字符串变成了1010，你在树状数组里也是要删除1节点的状态，所以原来的3号位置在当前变成了2号位置，当你删了3号以后变成了110 ，原来的4号位置变成了2号位置，所以每删除一次，下标会发生变化，但是没事，发现前面操作了几次而你原来的下标就比当前 减少了几，所以 nnum[i] - i 其实就是 当前需要删除的 元素 在 树状数组里的位置
int n,m;int c[1000000 + 55];int nnum[1000000 + 55];int aa[1000000 + 55];int sum[1000000 + 55];int len;void init() { memset(c,0,sizeof(c)); memset(aa,-1,sizeof(aa));}bool input() { while(cin>>n>>m) { for(int i=0;i<m;i++)cin>>nnum[i]; return false; } return true;}int lowbit(int x) { return x&(-x);}void add(int i,int val) { while(i <= n) { c[i] += val; i += lowbit(i); }}int get_sum(int i) { int sum = 0; while(i > 0) { sum += c[i]; i -= lowbit(i); } return sum;}void binary_find(int pos,int id) { int l = 1; int r = n; while(l <= r) { int mid = (l + r)>>1; int ret = get_sum(mid); if(aa[mid] == -1) { if(ret >= nnum[pos] - id) r = mid - 1; else l = mid + 1; } else if(ret == nnum[pos] - id) { add(mid,-1); aa[mid] = -1; len--; break; } else if(ret > nnum[pos] - id) r = mid - 1; else if(ret < nnum[pos] - id) l = mid + 1; }}void cal() { int q = n; len = 0; int cnt = 1; while(q--) { int type; cin>>type; if(type == -1) { if(len == 0)continue; if(nnum[0] > len)continue; int now = lower_bound(nnum,nnum + m,len) - nnum; for(int i=0;i<=now;i++) binary_find(i,i); } else { aa[cnt] = type; add(cnt,1); cnt++; len++; } } if(len <= 0){puts("Poor stack!");return ;} for(int i=1;i<=n;i++) if(aa[i] != -1) printf("%d",aa[i]); puts("");}void output() {}int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0;}
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#220(Div.2)D树状数组&&二分_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#220(Div.2)D树状数组&&二分_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。