牛客暑假多校第一场 J Different Integers

题意：给你一个数组， q次询问， 每次询问都会有1个[l, r] 求 区间[1,l] 和 [r, n] 中 数字的种类是多少。

解法1， 莫队暴力：

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 2e5 + ;

 int n, m, blo;

 int a[N];

 struct Node{

     int l, r, id, ans;

 }q[N];

 bool cmp(Node x1, Node x2){

     if(x1.l/blo !=  x2.l / blo) return x1.l < x2.l;

     if((x1.l / blo) & )    return x1.r < x2.r;

     else    return x1.r > x2.r;

 }

 int cnt[N];

 int tot;

 int ans[N];

 void add(int p){

     //cout << p << endl;

     cnt[a[p]]++;

     if(cnt[a[p]] == ) tot++;

 }

 void Remove(int p){

     cnt[a[p]]--;

     if(cnt[a[p]] == ) tot--;

 }

 int main(){

     while(~scanf("%d%d", &n, &m)){

         memset(cnt, , sizeof(cnt));

         tot = ;

         blo =  + ;

         for(int i = ; i <= n; i++)

             scanf("%d", &a[i]);

         for(int i = ; i <= m; i++){

             scanf("%d%d", &q[i].l, &q[i].r);

             q[i].id = i;

         }

         sort(q+, q++m, cmp);

         int L = , R = n+;

         for(int i = ; i <= m; i++){

             int nl = q[i].l;

             int nr = q[i].r;

             while(L < nl) add(++L);

             while(L > nl) Remove(L--);

             while(R > nr) add(--R);

             while(R < nr) Remove(R++);

             ans[q[i].id] = tot;

         }

         for(int i = ; i <= m; i++){

             printf("%d\n", ans[i]);

         }

     }

     return ;

 }

解法2， 离线询问， 按r从小到打排序， 每次r往右边移动的时候， 如果r移除的时候移除了 x 最后一次出现的位置， 那么就在x第一次出现的位置标记一下。 每次询问的时候答案就为[1,l] 标记数字出现的次数 + 右边的值。我们用树状数组来优化[1,l]的和。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 2e5 + ;

 int cnt[N], last[N], first[N];

 int a[N], ans[N];

 int n, m, tot;

 struct Node{

     int l, r, id;

     bool operator <(Node &x) const{

         return r < x.r;

     }

 }q[N];

 void Add(int x){

     while(x <= n){

         cnt[x]++;

         x += x&(-x);

     }

 }

 int Query(int x){

     int ret = ;

     while(x){

         ret += cnt[x];

         x -= x&(-x);

     }

     return ret;

 }

 int main(){

     while(~scanf("%d%d", &n, &m)){

         memset(cnt, , sizeof(cnt));

         memset(last, , sizeof(last));

         memset(first, , sizeof(first));

         tot = ;

         for(int i = ; i <= n; i++){

             scanf("%d", &a[i]);

             if(first[a[i]] == ){

                 first[a[i]] = i;

                 tot++;

             }

             last[a[i]] = i;

         }

         for(int i = ; i <= m; i++){

             scanf("%d%d", &q[i].l, &q[i].r);

             q[i].id = i;

         }

         sort(q+, q++m);

         int R = ;

         for(int i = ; i <= n; i++){

             while(R < q[i].r){

                 if(last[a[R]] == R){

                     Add(first[a[R]]);

                     tot--;

                 }

                 R++;

             }

             ans[q[i].id] = tot + Query(q[i].l);

         }

         for(int i = ; i <= m; i++)

             printf("%d\n", ans[i]);

     }

     return ;

 }

还有蔡队的写法， 直接复制一份原来的数组在后面， 将2个区间的问题转化成一个区间求数字的问题，然后就可以套主席树的板子了。