首页 > 代码库 > SPOJ3267--D-query （主席树入门练习）
SPOJ3267--D-query （主席树入门练习）
题意：查找区间内不同数字的个数。
两种做法，一种是 树状数组离线，另一种就是主席树。
树状数组离线操作的链接 http://www.cnblogs.com/oneshot/p/4110415.html
两种方法思路差不多，都是扫一遍，如果这个数曾经出现过那么就 在上次位置-1，如果没有出现过就在 当前位置+1，同时更新该数字的最新的位置。
这样的话，在主席树里面 以x为根的线段树存的就是1-x之间不同的数字的个数。我们只需要查找以r为根的线段树同时大于l的区间内的个数就行了。
给主席跪了，orz。主席树其实就是每个位置对应一颗线段树，但是这样 n 个点 n 棵线段树显然会MLE，怎么解决呢？我们可以看到 从第 i 棵线段树到第i+1 棵线段树，很多子树都是相同的，这样如果再重新建一棵完整的线段树显然浪费了很大的空间。我们只需要把第i棵线段树的 某个子树同时第i+1棵线段树 某个 节点下面即可，这样就大大减小了空间复杂度。
1 #include <map> 2 #include <cstdio> 3 #include <vector> 4 #include <cstdlib> 5 #include <cstring> 6 #include <algorithm> 7 using namespace std; 8 const int maxn = 3e4+10; 9 int a[maxn],c[maxn*18],lson[maxn*18],rson[maxn*18],tot,n,m; 10 int build(int l,int r) 11 { 12 int root = tot++; 13 c[root] = 0; 14 if (l != r) 15 { 16 int mid = (l + r) >> 1; 17 lson[root] = build(l,mid); 18 rson[root] = build(mid + 1,r); 19 } 20 return root; 21 } 22 int update(int root,int pos,int val) 23 { 24 int newroot = tot++; 25 int tmp = newroot; 26 c[newroot] = c[root] + val; 27 int l = 1,r = n; 28 while (l < r) 29 { 30 int mid = (l + r) >> 1; 31 if (pos <= mid) 32 { 33 rson[newroot] = rson[root]; 34 lson[newroot] = tot++; 35 newroot = lson[newroot]; 36 root = lson[root]; 37 r = mid; 38 } 39 else 40 { 41 lson[newroot] = lson[root]; 42 rson[newroot] = tot++; 43 newroot = rson[newroot]; 44 root = rson[root]; 45 l = mid + 1; 46 } 47 c[newroot] = c[root] + val; 48 } 49 return tmp; 50 } 51 int query(int root,int pos) 52 { 53 int res = 0; 54 int l = 1,r = n; 55 while (pos > l) 56 { 57 int mid = (l + r) >> 1; 58 if (pos <= mid) 59 { 60 res += c[rson[root]]; 61 root = lson[root]; 62 r = mid; 63 } 64 else 65 { 66 root = rson[root]; 67 l = mid + 1; 68 } 69 } 70 return res + c[root]; 71 } 72 int per_root[maxn]; 73 int main(void) 74 { 75 #ifndef ONLINE_JUDGE 76 freopen("in.txt","r",stdin); 77 #endif 78 while (~scanf ("%d",&n)) 79 { 80 tot = 0; 81 for (int i = 1; i <= n ;i++) 82 scanf ("%d",a+i); 83 per_root[0] = build(1,n); 84 map<int,int>mp; 85 for (int i = 1; i <= n; i++) 86 { 87 if (mp.find(a[i]) == mp.end()) 88 { 89 per_root[i] = update(per_root[i-1],i,1); 90 } 91 else 92 { 93 int tmp = update(per_root[i-1],mp[a[i]],-1); 94 per_root[i] = update(tmp,i,1); 95 } 96 mp[a[i]] = i; 97 } 98 scanf ("%d",&m); 99 for (int i = 0; i < m; i++)100 {101 int l,r;102 scanf ("%d%d",&l,&r);103 printf("%d\n",query(per_root[r],l));104 }105 }106 return 0;107 }
SPOJ3267--D-query （主席树入门练习）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。