首页 > 代码库 > spoj 3267 D-query
spoj 3267 D-query
题目链接:http://vjudge.net/problem/SPOJ-DQUERY
------------------------------------------------------------------------------
主席树模板题之一 求不带修改的区间不同数个数
最近学习了下发现主席树就是可持久化线段树 由于每次单点修改只会改变一条链上的信息
所以我们可以把其余部分的信息重复利用 然后再新建一条链作为这次修改后的这条链的新状态
所以每次单点修改的时间复杂度和空间复杂度都是$O(logN)$
懂了原理后就像普通线段树一样按照自己的习惯来写就好 不需要准备什么模板
而对于这种求区间不同的数的个数的问题 我们只需维护对于每种前缀区间 每个数最后一次出现位置
然后所有最后一次出现位置对整个区间有$1$的贡献
这样就可以根据询问的区间右端点对应的版本 用区间减法来求区间不同数的个数
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 3e4 + 10, T = N * 50, L = 1e6 + 10; 4 int sum[T], ch[T][2], root[N << 1], ma[N], last[L]; 5 int croot, cnt, n, q; 6 void build(int x, int L, int R) 7 { 8 if(L == R) 9 {10 sum[x] = 0;11 return; 12 }13 int mid = (L + R) >> 1;14 ch[x][0] = ++cnt;15 build(cnt, L, mid);16 ch[x][1] = ++cnt;17 build(cnt, mid + 1, R);18 sum[x] = sum[ch[x][0]] + sum[ch[x][1]];19 }20 void update(int x, int L, int R, int y, int delta, int pre)21 {22 if(L == R)23 {24 sum[x] = sum[pre] + delta;25 return;26 }27 int mid = (L + R) >> 1;28 if(y <= mid)29 {30 ch[x][0] = ++cnt;31 update(cnt, L, mid, y, delta, ch[pre][0]);32 ch[x][1] = ch[pre][1];33 }34 else35 {36 ch[x][0] = ch[pre][0];37 ch[x][1] = ++cnt;38 update(cnt, mid + 1, R, y, delta, ch[pre][1]);39 }40 sum[x] = sum[ch[x][0]] + sum[ch[x][1]];41 }42 int query(int x, int L, int R, int r)43 {44 if(R <= r)45 return sum[x];46 int mid = (L + R) >> 1;47 if(r <= mid)48 return query(ch[x][0], L, mid, r);49 return50 sum[ch[x][0]] + query(ch[x][1], mid + 1, R, r);51 }52 int main()53 {54 scanf("%d", &n);55 root[++croot] = ++cnt;56 ma[0] = 1;57 build(cnt, 1, n);58 int x, y;59 for(int i = 1; i <= n; ++i)60 {61 scanf("%d", &x);62 root[++croot] = ++cnt;63 update(cnt, 1, n, i, 1, root[croot - 1]);64 if(last[x])65 {66 root[++croot] = ++cnt;67 update(cnt, 1, n, last[x], -1, root[croot - 1]);68 }69 last[x] = i;70 ma[i] = root[croot];71 }72 scanf("%d", &q);73 while(q--)74 {75 scanf("%d%d", &x, &y);76 if(x > 1)77 printf("%d\n", sum[ma[y]] - query(ma[y], 1, n, x - 1));78 else79 printf("%d\n", sum[ma[y]]);80 }81 return 0;82 }
spoj 3267 D-query
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。