bzoj3809 -- 莫队+分块
2018-06-17 23:17:20来源:未知 阅读 ()
题目大意:
给出一个序列和m个询问,每个询问求[l,r]中权值∈[a,b]的权值的种类数。
由于询问是离线的,考虑莫队。显然可以用修改和查询为O(log2n)的树状数组维护权值种类数,但这种做法的总时间复杂度是O(n*sqrt(n)*log2m),可能会TLE。
注意到总共有O(m)个查询、O(n*sqrt(n))个修改,所以可以使用O(sqrt(n))查询、O(1)修改的分块。总时间复杂度为O(m*sqrt(n)+n*sqrt(n))
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 inline char nc(){ 8 static char buf[100000],*p1=buf,*p2=buf; 9 if(p1==p2){ 10 p2=(p1=buf)+fread(buf,1,100000,stdin); 11 if(p1==p2)return EOF; 12 } 13 return *p1++; 14 } 15 inline void Read(int& x){ 16 char c=nc(); 17 for(;c<'0'||c>'9';c=nc()); 18 for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc()); 19 } 20 #define N 100010 21 #define M 1000010 22 #define lowbit(x) x&-x 23 struct Node{ 24 int l,r,a,b,F; 25 }A[M]; 26 int i,j,l,r,k,n,m,c[N],a[N],S,Ans[M],Ma,Sum[350],Cnt[N],b[N]; 27 inline bool Cmp(Node x,Node y){ 28 return b[x.l]<b[y.l]||(b[x.l]==b[y.l]&&x.r<y.r); 29 } 30 inline void U(int x){ 31 Cnt[x]++;if(Cnt[x]==1)Sum[b[x]]++; 32 } 33 inline void D(int x){ 34 Cnt[x]--;if(Cnt[x]==0)Sum[b[x]]--; 35 } 36 inline int Query(int x,int y){ 37 int Ans=0; 38 if(b[y]-b[x]<=1){ 39 for(;x<=y;x++)Ans+=(Cnt[x]?1:0); 40 return Ans; 41 } 42 for(int i=b[x]+1;i<b[y];i++)Ans+=Sum[i]; 43 for(int i=x;b[i]==b[x];i++)Ans+=(Cnt[i]?1:0); 44 for(int i=y;b[i]==b[y];i--)Ans+=(Cnt[i]?1:0); 45 return Ans; 46 } 47 int s[20]; 48 int Len; 49 inline void Print(int x){ 50 if(x==0){putchar(48);putchar('\n');return;} 51 for(Len=0;x;x/=10)s[++Len]=x%10; 52 for(;Len;)putchar(s[Len--]+48); 53 putchar('\n'); 54 } 55 int main() 56 { 57 Read(n);Read(m); 58 S=sqrt((double)n); 59 for(i=1;i<=n;i++)b[i]=(i-1)/S+1; 60 for(i=1;i<=n;i++){ 61 Read(a[i]); 62 if(a[i]>Ma)Ma=a[i]; 63 } 64 for(i=1;i<=m;i++){ 65 Read(A[i].l);Read(A[i].r);Read(A[i].a);Read(A[i].b); 66 A[i].F=i; 67 } 68 sort(A+1,A+m+1,Cmp); 69 for(i=1,l=1,r=0;i<=m;i++){ 70 while(A[i].r>r)U(a[++r]); 71 while(A[i].l>l)D(a[l++]); 72 while(A[i].r<r)D(a[r--]); 73 while(A[i].l<l)U(a[--l]); 74 Ans[A[i].F]=Query(A[i].a,A[i].b); 75 } 76 for(i=1;i<=m;i++)Print(Ans[i]); 77 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:Add Two Numbers
- 莫队算法例题,模板及小结 2019-08-16
- 牛客国庆集训day6 B Board (模拟标记思维或找规律或分块? 2018-10-08
- BZOJ4241: 历史研究(回滚莫队) 2018-09-18
- 树上莫队算法 2018-06-27
- SPOJ COT2 - Count on a tree II(树上莫队) 2018-06-27
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash