HDU 5919 Sequence II（主席树）题解-白红宇

HDU 5919 Sequence II（主席树）题解

阅读量：5337 次

发布时间：2019-06-15

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

题意：有A1 ~ An组成的数组，给你l r，L = min((l + ans[i - 1]) % n + 1, (r + ans[i - 1]) % n + 1)，R = max((l + ans[i - 1]) % n + 1, (r + ans[i - 1]) % n + 1)，你先需要的到L，R区间有k个不同的数字，然后问你L，R区间第（k + 1）/ 2个不同的数字下标是多少？

思路：显然是个在线询问。

我们之前已经会用主席树求区间内有多少不同数字了：从左到右把每个数字的位置存进每个操作的线段树，如果之前这个数已经出现，就在当前这棵线段树中删掉之前出现的位置，以保证每个数字出现的唯一性。显然每个区间保存的是某个数字最右边出现的位置。

但是这里显然我们不能去直接求第（k + 1）/ 2个不同的数字下标，因为我这里要求的是最早出现第（k + 1）/ 2个数的位置。那我直接从n往1建主席树，那我就变成了每个区间保存的是某个数字最左边出现的位置，显然我第i棵树并没有保存i前面的位置，那我就可以直接求i到后面任意位置的区间的第p个不相同数出现的位置。

代码：

#include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include 
            
             #include
             
              using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 2e5 + 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, q;struct node{ int lson, rson; int sum;}T[maxn * 40];int fa[maxn], ans[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 query1(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 += query1(l, m, L, R, T[now].lson); if(R > m) sum += query1(m + 1, r, L, R, T[now].rson); return sum;}int query2(int l, int r, int now, int k){ if(l == r) return l; int m = (l + r) >> 1; int sum = T[T[now].lson].sum; if(sum >= k) return query2(l, m, T[now].lson, k); else return query2(m + 1, r, T[now].rson, k - sum);}int main(){ int ca = 1, t; scanf("%d" ,&t); while(t--){ init(); scanf("%d%d", &n, &q); root[n + 1] = 0; for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = n; i >= 1; i--){ if(fa[a[i]] == -1){ update(1, n, root[i], root[i + 1], i, 1); fa[a[i]] = i; } else{ update(1, n, root[i], root[i + 1], i, 1); update(1, n, root[i], root[i], fa[a[i]], -1); fa[a[i]] = i; } } ans[0] = 0; for(int i = 1; i <= q; i++){ int l, r, L, R, k; scanf("%d%d", &l, &r); L = min((l + ans[i - 1]) % n + 1, (r + ans[i - 1]) % n + 1); R = max((l + ans[i - 1]) % n + 1, (r + ans[i - 1]) % n + 1); k = query1(1, n, L, R, root[L]); ans[i] = query2(1, n, root[L], (k + 1) / 2); } printf("Case #%d:", ca++); for(int i = 1 ; i <= q; i++) printf(" %d", ans[i]); printf("\n"); } return 0;}

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

你可能感兴趣的文章