Different Integers（牛客多校第一场+莫队做法）

题目链接：https://www.nowcoder.com/acm/contest/139/J

题目：

题意：给你n个数，q次查询，对于每次查询得l，r，求1~l和r~n元素得种类。

莫队思路：1.将元素copy一份到最右边然后对于每次查询得l，r，我们就可以转换成求r，l+n这一个连续区间得元素种类，就将其转换成了一个莫队模板题了（比赛时还不会莫队就随便找了个板子）；

　　　　　2.将移动的两个指针l设为0，r设为n+1，然后进行莫队即可。

做法一代码实现如下：

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #include <cstdlib>

 #include <cstring>

 #include <vector>

 #include <list>

 #include <map>

 #include <stack>

 #include <queue>

 using namespace std;

 #define ll long long

 const int maxn1 = ;

 int cur[maxn1];

 int then[maxn1];

 int ans[maxn1];

 int limit,n,m;

 struct node

 {

     int l,r,id;

 }que[maxn1];

 bool cmp(node x,node y)

 {

     if(x.l/limit == y.l/limit)

         return x.r < y.r;

     return x.l/limit < y.l/limit;

 }

 void init()

 {

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

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

         cur[i+n] = cur[i];

     }

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

     {

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

         int t = que[i].r;

         que[i].r = que[i].l + n;

         que[i].l = t;

         que[i].id = i;

     }

     limit = (int)(sqrt( * n)+0.5);

     memset(then,,sizeof(then));

     memset(ans, , sizeof(ans));

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

 }

 void solve()

 {

     int L,R,ans1;

     L = R = ;

     ans1 = ;

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

     {

         while(que[i].l > L)

         {

             then[cur[L]]--;

             if(then[cur[L]] == )

                 ans1--;

             L++;

         }

         while(que[i].r < R)

         {

             then[cur[R]]--;

             if(then[cur[R]] == )

                 ans1--;

             R--;

         }

         while(que[i].l < L)

         {

             L--;

             then[cur[L]]++;

             if(then[cur[L]] == )

                 ans1++;

         }

         while(que[i].r > R)

         {

             R++;

             then[cur[R]]++;

             if(then[cur[R]] == )

                 ans1++;

         }

         ans[que[i].id] = ans1;

     }

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

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

 }

 int main()

 {

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

         init();

         solve();

     }

     return ;

 }

做法二代码实现如下：

 #include <set>

 #include <map>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 typedef unsigned long long ull;

 #define bug printf("*********\n");

 #define FIN freopen("in.txt", "r", stdin);

 #define debug(x) cout<<"["<<x<<"]" <<endl;

 #define IO ios::sync_with_stdio(false),cin.tie(0);

 const double eps = 1e-;

 const int mod = 1e9 + ;

 const int maxn = 1e5 + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const ll INF = 0x3f3f3f3f3f3f3f3f;

 inline int read() {//读入挂

     int ret = , c, f = ;

     for(c = getchar(); !(isdigit(c) || c == '-'); c = getchar());

     if(c == '-') f = -, c = getchar();

     for(; isdigit(c); c = getchar()) ret = ret *  + c - '';

     if(f < ) ret = -ret;

     return ret;

 }

 int n, q, sum, block;

 int a[maxn], cnt[maxn], pos[maxn];

 struct node {

     int l, r, ans, id;

 }ask[maxn];

 bool cmp(const node& x, const node& y) {

     return pos[x.l] == pos[y.l] ? x.r < y.r : x.l < y.l;

 }

 void add(int x) {

     cnt[x]++;

     if(cnt[x] == ) sum++;

 }

 void del(int x) {

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

     cnt[x]--;

 }

 int main() {

     //FIN;

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

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

             cnt[i] = ;

         }

         sum = ;

         block = sqrt( * n);

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

             a[i] = read();

             pos[i] = (i - ) / block;

         }

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

             ask[i].l = read();

             ask[i].r = read();

             ask[i].id = i;

         }

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

         for(int i = , l = , r = n + ; i <= q; i++) {

             while(r < ask[i].r) del(a[r++]);

             while(r > ask[i].r) add(a[--r]);

             while(l < ask[i].l) add(a[++l]);

             while(l > ask[i].l) del(a[l--]);

             ask[ask[i].id].ans = sum;

         }

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

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

     }

     return ;

 }

巴特西

Different Integers（牛客多校第一场+莫队做法）

最新文章

热门文章