牛客网 暑期ACM多校训练营（第一场）J.Different Integers-区间两侧不同数字的个数-离线树状数组 or 可持久化线段树(主席树)

Mike

J.Different Integers
题意就是给你l,r，问你在区间两侧的[1,l]和[r,n]中，不同数的个数。
两种思路:
1.将数组长度扩大两倍,for(int i=n+1;i<=2*n;i++) a=a[i-n]；就可以将两个分开的区间合并成一个区间[r,l+n]，然后就可以通过主席树求解，套模板就可以了。
但是用主席树有风险，容易写超时，超内存，只能通过50%，初始化数组memset少写一个就过了，而且while(scanf("%d%d",&n,&m)==2)要写成这样，我赛后试了一下while(~scanf("%d%d",&n,&m))，过不了，只能过50%，所以主席树正好卡过去。
代码:

1 //J-主席树刚好卡过
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<vector>
 6 #include<algorithm>
 7 #include<cmath>
 8 #include<cstdlib>
 9 #include<queue>
10 using namespace std;
11 const int maxn=2*1e5+100;
12 
13 struct Node
14 {
15   int l,r,sum;
16 
17 }p[maxn*200];
18 int la[maxn],a[maxn],root[maxn];
19 int n,q,cnt;
20 
21 int build(int l,int r)
22 {
23   int nc=++cnt;
24   p[nc].sum=0;
25   p[nc].l=p[nc].r=0;
26   if(l==r){
27     return nc;
28   }
29 
30   int m=l+r>>1;
31   p[nc].l=build(l,m);
32   p[nc].r=build(m+1,r);
33   return nc;
34 }
35 int update(int pos,int c,int v,int l,int r)
36 {
37   int nc=++cnt;
38   p[nc]=p[c];
39   p[nc].sum+=v;
40   if(l==r){
41     return nc;
42   }
43 
44   int m=l+r>>1;
45   if(m>=pos)
46     p[nc].l=update(pos,p[c].l,v,l,m);
47   else
48     p[nc].r=update(pos,p[c].r,v,m+1,r);
49   return nc;
50 }
51 int query(int pos,int c,int l,int r)
52 {
53   if(l==r) return p[c].sum;
54   int m=l+r>>1;
55   if(m>=pos)
56     return p[p[c].r].sum + query(pos,p[c].l,l,m);
57   else
58     return query(pos,p[c].r,m+1,r);
59 }
60 int main()
61 {
62   while(scanf("%d%d",&n,&q)==2){
63     memset(la,-1,sizeof(la));
64     cnt=0;
65     for (int i=1;i<=n;i++){
66       scanf("%d",a+i);
67     }
68     for(int i=n+1;i<=2*n;i++)
69       a[i]=a[i-n];
70     n=n*2;
71     root[0]=build(1,n);
72     for (int i=1;i<=n;i++){
73       int v=a[i];
74       if(la[v]==-1)
75         root[i]=update(i,root[i-1],1,1,n);
76       else{
77         int t=update(la[v],root[i-1],-1,1,n);
78         root[i]=update(i,t,1,1,n);
79       }
80       la[v]=i;
81     }
82     while(q--){
83       int x,y;
84       scanf("%d%d",&x,&y);
85       printf("%d\n",query(y,root[n/2+x],1,n));
86     }
87   }
88 }

2.叉姐官方题解思路是树状数组，离线按照 r 从小到大处理询问，考虑没出现的数字个数，假设 r = last[x]，那么当 l < first[x] 时，x 没出现，用树状数组维护即可。
唉，真的是长的帅又厉害代码写的还优美，代码写的真的是好看，羡慕(✧◡✧)
代码:(叉姐代码)

1 #include <bits/stdc++.h>
 2 
 3 struct Query
 4 {
 5   int l, r, id;
 6 };
 7 
 8 bool operator < (const Query& u, const Query& v)
 9 {
10   return u.r < v.r;
11 }
12 
13 int main()
14 {
15   int n, q;
16   while (scanf("%d%d", &n, &q) == 2) {
17     std::vector<int> a(n), first(n, -1), last(n);
18     int total = 0;
19     for (int i = 0; i < n; ++ i) {
20       scanf("%d", &a[i]);
21       a[i] --, last[a[i]] = i;
22       if (first[a[i]] == -1) {
23         total ++, first[a[i]] = i;
24       }
25     }
26     std::vector<Query> queries;
27     for (int i = 0, l, r; i < q; ++ i) {
28       scanf("%d%d", &l, &r);
29       queries.push_back(Query {l - 1, r - 1, i});
30     }
31     std::sort(queries.begin(), queries.end());
32     std::vector<int> count(n), result(q);
33     for (int i = 0, k = 0; i < n; ++ i) {
34       while (k < q && queries[k].r == i) {
35         int& ref = result[queries[k].id] = total;
36         for (int j = queries[k].l; j < n; j += ~j & j + 1) {
37           ref -= count[j];
38         }
39         k ++;
40       }
41       if (last[a[i]] == i) {
42         for (int j = first[a[i]] - 1; ~j; j -= ~j & j + 1) {
43           count[j] ++;
44         }
45       }
46     }
47     for (int i = 0; i < q; ++ i) {
48       printf("%d\n", result[i]);
49     }
50   }
51 }

自己改了一下叉姐代码加了一点注释的代码:

1 //J-离线树状数组处理
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<map>
 9 #include<vector>
10 using namespace std;
11 const int maxn=1e5+10;
12 const int inf=0x3f3f3f3f;
13 const double eps=1e-5;
14 struct node
15 {
16   int l,r,id;
17   bool operator< (const node &a) const{   //结构体内嵌比较函数
18     return r<a.r;
19   }
20 };
21 int main()
22 {
23   int n,q;
24   while(~scanf("%d%d",&n,&q)){
25     vector<int>a(n),first(n, -1),last(n);
26     int total=0;
27     for (int i=0;i<n;i++){
28       scanf("%d",&a[i]);
29       a[i]--,last[a[i]]=i;//记录元素最后出现的位置
30       if(first[a[i]]==-1){//如果元素之前未出现，则记录第一次出现的位置
31         total++；
32         first[a[i]]=i;
33       }
34     }
35     vector<node> queries;
36     for (int i=0;i<q;i++) {
37       int l,r;
38       scanf("%d%d",&l,&r);
39       queries.push_back(node {l-1,r-1,i});//将区间和id存到容器内
40     }
41     sort(queries.begin(),queries.end());//区间右边界升序排序(结构体内内嵌了比较函数)
42     vector<int>count(n),result(q);
43     for (int i=0,k=0;i<n;i++){//树状数组维护
44       while(k<q&&queries[k].r==i){
45         int &ref=result[queries[k].id]=total;
46         for(int j=queries[k].l;j<n;j+=~j&j+1){//~j&j+1 +的优先级比&高
47           ref-=count[j];
48         }
49         k++;
50       }
51       if(last[a[i]]==i){
52         for(int j=first[a[i]]-1;~j;j-=~j&j+1){
53           count[j]++;//统计没有出现过的元素个数
54         }
55       }
56     }
57     for (int i=0;i<q;i++) {
58       printf("%d\n",result[i]);
59     }
60   }
61 }

讲道理，我是真的菜，难受。