SPOJ DQUERY D-query（主席树区间不同数个数）-白红宇

SPOJ DQUERY D-query（主席树区间不同数个数）

阅读量：5134 次

发布时间：2019-06-13

本文共 1815 字，大约阅读时间需要 6 分钟。

题意：问你区间有几个不同的数

思路：主席树nb。我们知道主席树每一个root都存着一棵权值线段树，现在我们在每个root中存位置，也就是01表示这个位置存不存在。然后我们用一个fa[a[i]]表示a[i]这个数在前面出现的位置。如果没有在前面出现过，那么我们直接把这个位置变成1,；如果出现过了，我们就把当前root节点下的线段树的fa[a[i]]位置减掉。也就是说我每个数字存在的位置现在只出现当前区间的最右边的那个位置，那我直接每次询问L R区间个数，那么我直接遍历root[R]线段树的L R区间，看一下有几个位置就好了。

代码：

#include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include 
            
             #include
             
              using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 1e6 + 10;const int M = maxn * 30;const ull seed = 131;const int INF = 0x3f3f3f3f;const int MOD = 1000000007;int a[maxn], root[maxn], tot;int n, m;struct node{ int lson, rson; int sum;}T[maxn * 40];int fa[maxn];void init(){ tot = 0; memset(fa, -1, sizeof(fa)); memset(T, 0, sizeof(T));}void update(int l, int r, int &now, int pre, int pos, int v){ T[++tot] = T[pre], now = tot; T[now].sum += v; if(l == r) return; int m = (l + r) >> 1; if(pos <= m) update(l, m, T[now].lson, T[pre].lson, pos, v); else update(m + 1, r, T[now].rson, T[pre].rson, pos, v);}int query(int l, int r, int L, int R, int now){ if(L <= l && R >= r){ return T[now].sum; } int m = (l + r) >> 1, sum = 0; if(L <= m) sum += query(l, m, L, R, T[now].lson); if(R > m) sum += query(m + 1, r, L, R, T[now].rson); return sum;}int main(){ int ca = 1; init(); scanf("%d", &n); int cnt = 1e6; for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); if(fa[a[i]] == -1){ update(1, cnt, root[i], root[i - 1], i, 1); fa[a[i]] = i; } else{ update(1, cnt, root[i], root[i - 1], i, 1); update(1, cnt, root[i], root[i], fa[a[i]], -1); fa[a[i]] = i; } } scanf("%d", &m); while(m--){ int L, R; scanf("%d%d", &L, &R); printf("%d\n", query(1, cnt, L, R, root[R])); } return 0;}

转载于:https://www.cnblogs.com/KirinSB/p/10784288.html

你可能感兴趣的文章