IT技术互动交流平台

hdu5444Elven Postman(主席树思想的应用)

作者:殇雪  来源:IT165收集  发布日期:2015-09-14 22:21:34

主席树这个概念应该不陌生吧!恩?不会, 戳这里。

主席树(函数式线段树)用的是函数思想,一个节点开数组用来保存自己的左右节点,这样节省许多不必要的空间,还可以保存许多历史状态。而这里我们用的是主席树的函数思想来实现。

上题:http://acm.hdu.edu.cn/showproblem.php?pid=5444

题目大意:

给你一个序列,第一个数为二叉树根节点,之后每个数往上加节点,且保证左节点小于根节点,且保证右节点大于根节点。且每个节点最多有2个子节点。然后再查询位置,每往左找输出一个E,右找输出W。例如序列2, 1, 4, 3可以生成如下图:

例如查找1,需要往左一次输出E,查找2,不需要搜直接输出,查找3需要向右一次再向左一次,输出WE。

哇!这题好水,不就是二叉树吗?啪啪啪,几分钟码完了, 交一发,嗯,居然RE了,不行,的开大叔组,开成10W,嗯?又RE了。最后一想如果这个数列是1-n,即a[i] = i,那样需穴ky"http://www.it165.net/qq/" target="_blank" class="keylink">qq3w87Ktb0ytcQxMDAwtM63vbj2vdq146Gjub5+fiioc6luqHQpYqOs0/TDxsTYo6zIu7rzu9jP68bw0tTHsNGnuf21xNb3z6/K96Osv8nS1L+qyv3X6bzHwry4w73ateO1xNfz09K2+dfTo6zEx9H5xvGyu8rH1rvSqrfDzsq1vW649r3ateO+zdDQoaPIu7rzvs3V4tH5QUPBy6Gjo6ixyMj8tcTKsbryzOG9u7XEyrG68rOswcvByzUxc6Oso6wxNDowMDo1MbXEyrG68szhvbu1xKGjsb7AtMTcQUO1xKOsVEFUo6k8L3A+CjxwPri9yc+0+sLro7o8L3A+CgoKPHByZSBjbGFzcz0="brush:cpp;gutter:true;">#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 4000 + 5; int a[N], b[N],ls[N], rs[N], mx[N]; int n, k, tot, sz, ql, qr, x, q, T; void update(int o, int l, int r, int p){ int m = (l + r) >> 1; if(p <= mx[o]){ if(ls[o] == 0){ ls[o] = tot; mx[tot] = p; return ; } else update(ls[o], l, m, p); } else { if(rs[o] == 0){ rs[o] = tot; mx[tot] = p; return; } update(rs[o], m + 1, r, p); } } void query(int o, int l, int r, int k){ if(mx[o] == k)return ; int m = (l + r) >> 1; if(k <= mx[o]){ printf("E"); query(ls[o], l, m, k); } else{ printf("W"); query(rs[o], m + 1, r, k); } } void work(){ scanf("%d", &x); query(1, 1, n, x); puts(""); } int main(){ scanf("%d", &T); while(T--){ scanf("%d", &n); tot = 1; //Build(rt[0], 1, n); memset(mx, 0, sizeof(mx)); memset(ls, 0, sizeof(ls)); memset(rs, 0, sizeof(rs)); //for(int i = 1; i <= n; i ++)ls[i] = i << 1, rs[i] = i << 1|1; //for(int i = 0; i <= 20; i ++)printf("i = %d, rt = %d, ls = %d, rs= %d, mx = %d\n", i, rt[i], ls[i], rs[i], mx[i]); for(int i = 1; i <= n; i ++){ scanf("%d", a + i); if(i == 1)mx[1] = a[1]; else update(1, 1, n, a[i]); tot ++; } scanf("%d", &q); while(q --)work(); } return 0; }

  

延伸阅读:

Tag标签: 主席   思想  
  • 专题推荐

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规