CodeForces - 220B 离散化+莫队算法
2024-08-30 11:00:53
莫队算法链接：传送门
题意：
有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 <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdlib>
6 #include <algorithm>
7 #include <set>
8 #include <map>
9 #include <string>
10 #include <queue>
11 #include <stack>
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.r<y.r;
26 return x.l<y.l;
27 }
28 bool mmp2(Node x,Node y)
29 {
30 return x.id<y.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;i<=n;++i)
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;i<=n;++i)
54 {
55 a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
56 }
57 for(int i=1;i<=m;++i)
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;i<=m;++i)
62 {
63 while(lpos>node[i].l) add(--lpos);
64 while(rpos<node[i].r) add(++rpos);
65 while(lpos<node[i].l) del(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;i<=m;++i)
71 printf("%d\n",node[i].result);
72 return 0;
73 }
分块-正确代码：
1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <cmath>
5 #include <cstdlib>
6 #include <algorithm>
7 #include <set>
8 #include <map>
9 #include <string>
10 #include <queue>
11 #include <stack>
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?r<x.r:l<x.l;
24 }
25 }node[maxn];
26 //bool mmp1(Node x,Node y)
27 //{
28 // if(x.l==y.l)
29 // return x.r<y.r;
30 // return x.l<y.l;
31 //}
32 bool mmp2(Node x,Node y)
33 {
34 return x.id<y.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;i<=n;++i)
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;i<=n;++i)
58 {
59 a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
60 }
61 for(int i=1;i<=m;++i)
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;i<=m;++i)
66 {
67 while(lpos>node[i].l) add(--lpos);
68 while(rpos<node[i].r) add(++rpos);
69 while(lpos<node[i].l) del(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;i<=m;++i)
75 printf("%d\n",node[i].result);
76 return 0;
77 }
最新文章
- web前段 弹出小例子
- [Effective C++ --023]宁以non-member、non-friend替换member函数
- [转载]__type_traits
- centos安装epel源
- Week3（9月26日）：做完后，总结下
- i春秋与我
- mongodb突然出现不是内外部命令或可执行
- NiftyNet项目介绍
- 【51nod1847】 奇怪的数学题
- vs2013 跳过IE10
- android 多进程
- 显示Unicode 字节的对应字符的小技巧
- Learning from delayed reward (Q-Learning的提出) （Watkins博士毕业论文）（建立了现在的reinforcement Learning模型）
- spark java API 实现二次排序
- c++计算器后续（5）
- 真正的PHP多线程（绝非fork或者用http再开进程）
- Struts2---输入验证
- Java中多对多映射关系
- Activemq API使用(整合spring)
- 常用的gif加载动态图片