首页 > 代码库 > spoj 3267 D-query

spoj 3267 D-query

2024-08-15 22:36:08   211人阅读

题目链接: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


联系
我们