CodeForces - 220B 离散化+莫队算法
莫队算法链接:传送门
题意:
有n个数,m个区间。问区间内有多少个x,x满足x的个数等于x的值的个数(如果x是3,区间内要存在3个3)。
题解:
因为a[i]太大,所以要离散化一下,但是不能用map容器,因为map容器多一个log
莫队就是离线问题+区间的移动。复杂度是O((N+M)*√N)
莫队代码还要分块要不然还会TLE,分块大小为sqrt(n)
未分块-TLE代码:
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <set> #include <map> #include <string> #include <queue> #include <stack> #include <string> using namespace std; typedef long long ll; using namespace std; const int maxn=1e5+7; int unit,n,m; struct Node { int l,r,id,result; }node[maxn]; bool mmp1(Node x,Node y) { if(x.l==y.l) return x.r<y.r; return x.l<y.l; } bool mmp2(Node x,Node y) { return x.id<y.id; } int a[maxn],b[maxn],num[maxn],pr[maxn],ans; int add(int i) { num[a[i]]++; if(num[a[i]]==b[a[i]]) ans++; else if(num[a[i]]==b[a[i]]+1) ans--; } void del(int i) { num[a[i]]--; if(num[a[i]]==b[a[i]]) ans++; else if(num[a[i]]==b[a[i]]-1) ans--; } int main() { scanf("%d%d",&n,&m); unit=(int)sqrt(n); for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); int cnt=unique(b+1,b+1+n)-(b+1); for(int i=1;i<=n;++i) { a[i]=lower_bound(b+1,b+1+cnt,a[i])-b; } for(int i=1;i<=m;++i) scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i; sort(node+1,node+1+m,mmp1); int lpos=node[1].l,rpos=lpos-1; for(int i=1;i<=m;++i) { while(lpos>node[i].l) add(--lpos); while(rpos<node[i].r) add(++rpos); while(lpos<node[i].l) del(lpos++); while(rpos>node[i].r) del(rpos--); node[i].result=ans; } sort(node+1,node+1+m,mmp2); for(int i=1;i<=m;++i) printf("%d\n",node[i].result); return 0; }
分块-正确代码:
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <set> #include <map> #include <string> #include <queue> #include <stack> #include <string> using namespace std; typedef long long ll; using namespace std; const int maxn=1e5+7; int unit,n,m; struct Node { int l,r,id,result; bool operator < (const Node x)const { return l/unit==x.l/unit?r<x.r:l<x.l; } }node[maxn]; //bool mmp1(Node x,Node y) //{ // if(x.l==y.l) // return x.r<y.r; // return x.l<y.l; //} bool mmp2(Node x,Node y) { return x.id<y.id; } int a[maxn],b[maxn],num[maxn],pr[maxn],ans; int add(int i) { num[a[i]]++; if(num[a[i]]==b[a[i]]) ans++; else if(num[a[i]]==b[a[i]]+1) ans--; } void del(int i) { num[a[i]]--; if(num[a[i]]==b[a[i]]) ans++; else if(num[a[i]]==b[a[i]]-1) ans--; } int main() { scanf("%d%d",&n,&m); unit=(int)sqrt(n); for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); int cnt=unique(b+1,b+1+n)-(b+1); for(int i=1;i<=n;++i) { a[i]=lower_bound(b+1,b+1+cnt,a[i])-b; } for(int i=1;i<=m;++i) scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i; sort(node+1,node+1+m); int lpos=node[1].l,rpos=lpos-1; for(int i=1;i<=m;++i) { while(lpos>node[i].l) add(--lpos); while(rpos<node[i].r) add(++rpos); while(lpos<node[i].l) del(lpos++); while(rpos>node[i].r) del(rpos--); node[i].result=ans; } sort(node+1,node+1+m,mmp2); for(int i=1;i<=m;++i) printf("%d\n",node[i].result); return 0; }
相关推荐
boneix 2020-10-21
seanzed 2020-10-15
ifconfig 2020-10-14
学留痕 2020-09-20
往后余生 2020-09-17
kka 2020-09-14
redis 2020-09-07
lzccheng 2020-09-06
soyo 2020-08-31
stonerkuang 2020-08-18
LxyPython 2020-08-17
raksmart0 2020-08-17
Lzs 2020-08-14
MrHaoNan 2020-07-31
80530895 2020-07-05
lengyu0 2020-06-28
YarnSup 2020-06-28
huanglianhuabj00 2020-06-27