SPOJ - DQUERY D-query——主席树

SPOJ - DQUERY D-query——主席树

区间不相同的数模板题

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;int T, ks, n, m, a[maxn], pre[maxn*10], cnt, root[maxn];struct Node { int l, r, sum; }node[maxn*40];int p, v;void init() { cnt = 0; memset(pre, 0, sizeof(pre));}void update(int l, int r, int &rootx, int rooty) { rootx = ++cnt; node[rootx] = node[rooty]; node[rootx].sum += v; if (l == r) return; int mid = (l + r)>>1; if (p <= mid) update(l, mid, node[rootx].l, node[rooty].l); else update(mid+1, r, node[rootx].r, node[rooty].r);}int query(int l, int r, int rootx) { if (l == r) return node[rootx].sum; int mid = (l + r)>>1; if (p <= mid) return node[node[rootx].r].sum + query(l, mid, node[rootx].l); else return query(mid+1, r, node[rootx].r);}int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (!pre[a[i]]) { p = i, v = 1; update(1, n, root[i], root[i-1]); } else { int temp; p = pre[a[i]], v = -1; update(1, n, temp, root[i-1]); p = i, v = 1; update(1, n, root[i], temp); } pre[a[i]] = i; } scanf("%d", &m); while (m--) { int l, r; scanf("%d%d", &l, &r); p = l; printf("%d\n", query(1, n, root[r])); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。