[Luogu] p1972 HH Necklace

Title address ：

https://www.luogu.com.cn/problem/P1972

Title Description ：
HH There is a necklace made of all kinds of beautiful shells .HH I believe different shells will bring good luck , So after every walk , He would take out a piece of shell at will , Think about what they mean .HH Constantly collecting new shells , therefore , His necklace is getting longer and longer . one day , He suddenly asked a question ： In a piece of shell , How many different shells are there ？ This question is hard to answer …… Because the necklace is too long . therefore , He had to turn to you for help , To solve this problem .

Input format ：
One positive integer per line $n$, Indicates the length of the necklace .
The second line $n$ A positive integer $a_i$, Indicates the... In the necklace $i$ A kind of shell .
The third line is an integer $m$, Express HH Number of queries .
Next $m$ That's ok , Two integers per line $l,r$, The interval of inquiry .

Output format ：
Output $m$ That's ok , One integer per row , Ask the corresponding answer in turn .

Data range ：
about $20\%$ The data of ,$1\le n,m\le 5000$;
about $40\%$ The data of ,$1\le n,m\le 10^5$;
about $60\%$ The data of ,$1\le n,m\le 5\times 10^5$;
about $100\%$ The data of ,$1\le n,m,a_i\le 10^6$,$1\le l\le r\le n$.
This question may need a faster reading method , The maximum data point is about $20$MB.

Mo team solution reference https://blog.csdn.net/qq_46105170/article/details/125827776. Next, we introduce the tree array solution .

First, sort all queries from small to large according to the right endpoint . The key to solving the problem is if a certain number $x$ There have been many times , We only reserve the last time in this inquiry section . The method is , Open a pointer $i$, Dynamically maintain each number in $i$ Positions that have appeared before $f[a_i]$（ If it doesn't exist $f[a_i]=0$）, When asked $[l,r]$ When , If $i\le r$, It will be $i$ Sweep to $r$, At the same time, every time in the tree array , If $f[a_i]\ne 0$, Then the position $f[a_i]$ reduce $1$; Every time the position in the tree array $i$ Add $1$. In the array maintained by the tree array , Depending on the $r$ For the right border , Each number is marked only at its rightmost position $1$. In this way, you only need to find the interval of the array maintained by the tree array $[l,r]$ And . The code is as follows ：

#include <iostream>
#include <algorithm>
#define lowbit(x) (x & -x)
using namespace std;

const int N = 1e6 + 10;
int n, m, a[N], res[N], f[N];
struct Query {
    
  int id, l, r;
} q[N];
int tr[N];

inline void add(int k, int x) {
    
  for (; k <= n; k += lowbit(k)) tr[k] += x;
}

inline int sum(int k) {
    
  int res = 0;
  for (; k; k -= lowbit(k)) res += tr[k];
  return res;
}

int main() {
    
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }

  sort(q, q + m, [&](Query &q1, Query &q2) {
    
    return q1.r < q2.r;
  });

  for (int i = 1, k = 0; k < m; k++) {
    
    int r = q[k].r, l = q[k].l, id = q[k].id;
    for (; i <= n && i <= r; i++) {
    
      if (f[a[i]]) add(f[a[i]], -1);
      f[a[i]] = i;
      add(i, 1);
    }
    res[id] = sum(r) - sum(l - 1);
  }

  for (int i = 0; i < m; i++) printf("%d\n", res[i]);
}

Preprocessing time complexity $O(m\log m)$, Each inquiry averages $O(\log n+n/m)$, Space $O(n+{\max }_i{a}_i)$.