CodeForces - 220B 离散化+莫队算法

2021-02-01 22:17

阅读：449

标签：b16 closed view style nbsp 莫队算法 scanf 复杂度 for

莫队算法链接：传送门

题意：

有n个数，m个区间。问区间内有多少个x，x满足x的个数等于x的值的个数（如果x是3，区间内要存在3个3）。

题解：

因为a[i]太大，所以要离散化一下，但是不能用map容器，因为map容器多一个log

莫队就是离线问题+区间的移动。复杂度是O（(N+M)*√N）

莫队代码还要分块要不然还会TLE，分块大小为sqrt(n)

未分块-TLE代码：

 1 #include  2 #include  3 #include  4 #include  5 #include  6 #include 
 7 #include set>
 8 #include  9 #include string>
10 #include 11 #include 12 #include string>
13 using namespace std;
14 typedef long long ll;
15 using namespace std;
16 const int maxn=1e5+7;
17 int unit,n,m;
18 struct Node
19 {
20     int l,r,id,result;
21 }node[maxn];
22 bool mmp1(Node x,Node y)
23 {
24     if(x.l==y.l)
25         return x.ry.r;
26     return x.ly.l;
27 }
28 bool mmp2(Node x,Node y)
29 {
30     return x.idy.id;
31 }
32 int a[maxn],b[maxn],num[maxn],pr[maxn],ans;
33 int add(int i)
34 {
35     num[a[i]]++;
36     if(num[a[i]]==b[a[i]]) ans++;
37     else if(num[a[i]]==b[a[i]]+1) ans--;
38 }
39 void del(int i)
40 {
41     num[a[i]]--;
42     if(num[a[i]]==b[a[i]]) ans++;
43     else if(num[a[i]]==b[a[i]]-1) ans--;
44 }
45 int main()
46 {
47     scanf("%d%d",&n,&m);
48     unit=(int)sqrt(n);
49     for(int i=1;ii)
50         scanf("%d",&a[i]),b[i]=a[i];
51     sort(b+1,b+n+1);
52     int cnt=unique(b+1,b+1+n)-(b+1);
53     for(int i=1;ii)
54     {
55         a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
56     }
57     for(int i=1;ii)
58         scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i;
59     sort(node+1,node+1+m,mmp1);
60     int lpos=node[1].l,rpos=lpos-1;
61     for(int i=1;ii)
62     {
63         while(lpos>node[i].l) add(--lpos);
64         while(rposrpos);
65         while(lpos);
66         while(rpos>node[i].r) del(rpos--);
67         node[i].result=ans;
68     }
69     sort(node+1,node+1+m,mmp2);
70     for(int i=1;ii)
71         printf("%d\n",node[i].result);
72     return 0;
73 }

View Code

分块-正确代码：

 1 #include  2 #include  3 #include  4 #include  5 #include  6 #include 
 7 #include set>
 8 #include  9 #include string>
10 #include 11 #include 12 #include string>
13 using namespace std;
14 typedef long long ll;
15 using namespace std;
16 const int maxn=1e5+7;
17 int unit,n,m;
18 struct Node
19 {
20     int l,r,id,result;
21     bool operator const Node x)const
22     {
23         return l/unit==x.l/unit?rx.l;
24     }
25 }node[maxn];
26 //bool mmp1(Node x,Node y)
27 //{
28 //    if(x.l==y.l)
29 //        return x.r30 //    return x.l31 //}
32 bool mmp2(Node x,Node y)
33 {
34     return x.idy.id;
35 }
36 int a[maxn],b[maxn],num[maxn],pr[maxn],ans;
37 int add(int i)
38 {
39     num[a[i]]++;
40     if(num[a[i]]==b[a[i]]) ans++;
41     else if(num[a[i]]==b[a[i]]+1) ans--;
42 }
43 void del(int i)
44 {
45     num[a[i]]--;
46     if(num[a[i]]==b[a[i]]) ans++;
47     else if(num[a[i]]==b[a[i]]-1) ans--;
48 }
49 int main()
50 {
51     scanf("%d%d",&n,&m);
52     unit=(int)sqrt(n);
53     for(int i=1;ii)
54         scanf("%d",&a[i]),b[i]=a[i];
55     sort(b+1,b+n+1);
56     int cnt=unique(b+1,b+1+n)-(b+1);
57     for(int i=1;ii)
58     {
59         a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
60     }
61     for(int i=1;ii)
62         scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i;
63     sort(node+1,node+1+m);
64     int lpos=node[1].l,rpos=lpos-1;
65     for(int i=1;ii)
66     {
67         while(lpos>node[i].l) add(--lpos);
68         while(rposrpos);
69         while(lpos);
70         while(rpos>node[i].r) del(rpos--);
71         node[i].result=ans;
72     }
73     sort(node+1,node+1+m,mmp2);
74     for(int i=1;ii)
75         printf("%d\n",node[i].result);
76     return 0;
77 }

View Code

CodeForces - 220B 离散化+莫队算法

标签：b16 closed view style nbsp 莫队算法 scanf 复杂度 for

原文地址：https://www.cnblogs.com/kongbursi-2292702937/p/12812455.html

上一篇：Java BIO、NIO、AIO

下一篇：php phpexcel/PHPExcel导出乱码的问题

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：CodeForces - 220B 离散化+莫队算法
文章链接：http://soscw.com/index.php/essay/49691.html

亲，登录后才可以留言！

CodeForces - 220B 离散化+莫队算法

评论

热门文章

推荐文章

最新文章

置顶文章