牛客竞赛题目讲解_Different Integers

// 

//  https://ac.nowcoder.com/acm/contest/20322/J

#include <algorithm>

#include <iostream>

#include <cstring>

 using namespace std;

const int N = 1E5 + 100;

int n, m, block;

int arr[N]={ 0,1, 2, 3,4, 1,2,3 };

/*  莫队算法 (Mo's Algorithm)

*/

int res[N];

 int cnt[N];

struct Mo {

    int L, r, idx, lb;  

     bool operator < (const Mo &rhs) const {

        if (lb == rhs.lb) {

            return r < rhs.r;

        }

        return lb < rhs.lb;

    }

};

Mo qry[N];

int Q[N][2]={

1, 3,

3, 6,

2 ,3,

2 ,4,

1 ,3,

1 ,7,

3,5

};

 int sum=0;

void Insert(int x)

{

    cnt[x]++;//个数记录

    if(cnt[x]==1) sum++;//如果满足条件，就更新答案

}

void Remove(int x)

{

    cnt[x]--;

    if(cnt[x]==0) sum--;

}

int main() {

      n=7;m=7;

memset(cnt,0,sizeof cnt);

    /*

cin >> n>> m;

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

        cin >> arr[i];

    }

     

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

        cin >> qry[i].L >> qry[i].r;

        qry[i].idx = i;

    }*/

block = sqrt(n);  

cout<<block<<endl;

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

         qry[i].L =Q[i-1][0]; qry[i].r=Q[i-1][1];

        qry[i].idx = i;

qry[i].lb= qry[i].L/block;

}

   

   sort(qry + 1, qry + 1 + m);

for (int i = 1; i <= m; i++) cout<<qry[i].idx<<"   ";

cout<<endl;

    int left=0,r=n+1;

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

while(left<qry[i].L) Insert(arr[++left]);

cout <<" sum="<<sum<<" i="<<i<<" left="<<left<<" r="<<r<<endl;         

while(left>qry[i].L) Remove(arr[left--]);

           cout <<" sum="<<sum<<" i="<<i<<" left="<<left<<" r="<<r<<endl;

            while(r<qry[i].r) Remove(arr[r++]);

           cout <<" sum="<<sum<<" i="<<i<<" left="<<left<<" r="<<r<<endl;

            while(r>qry[i].r) Insert(arr[--r]);

cout <<" sum="<<sum<<" i="<<i<<" left="<<left<<" r="<<r<<endl<<endl;

            res[qry[i].idx]=sum;//记录答案

    }

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

        cout << res[i] << endl;

    }

    return 0;

}