【LOJ2254】【SNOI2017】一个简单的询问

Author Avatar
q234rty 8月 02, 2017

莫队算法即可。

本题粗看似乎无从下手，考虑将一个询问拆成多个前缀询问。

设 f(x,y)=ans(1,x,1,y) , g(x,y)=get(1,x,y) ,我们有

\begin{aligned} ans(l1,r1,l2,r2) & =\sum_{x=0}^{\infty}(g(r1,x)-g(l1-1,x))\times (g(r2,x)-g(l2-1,x))\\ & =\sum_{x=0}^{\infty}g(r1,x)\times g(r2,x)-g(r1,x)\times g(l2-1,x)\\ & -g(l1-1,x)\times g(r2,x)+g(l1-1,x)\times g(l2-1,x)\\ & =f(r1,r2)-f(r1,l2-1)-f(l1-1,r2)+f(l1-1,l2-1) \end{aligned}

于是用莫队计算 f 即可。

用两个数组分别维护两个前缀中每个数的出现次数，增删数时可以 O(1) 更新答案。

时间复杂度 O(n \sqrt n) 。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=10000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9. 	#ifdef LOCAL
  10. 		freopen("2254.txt","r",stdin);
  11. 	#endif
  12. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  13. 	bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17. 	bool isneg;
  18. 	int val=0;
  19. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20. 	bufpos+=(isneg=buf[bufpos]=='-');
  21. 	for(;isdigit(buf[bufpos]);bufpos++)
  22. 		val=val*10+buf[bufpos]-'0';
  23. 	return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27. 	int val=0;
  28. 	for(;!isdigit(buf[bufpos]);bufpos++);
  29. 	for(;isdigit(buf[bufpos]);bufpos++)
  30. 		val=val*10+buf[bufpos]-'0';
  31. 	return val;
  32. }
  33. #endif
  34. char readchar(){
  35. 	for(;isspace(buf[bufpos]);bufpos++);
  36. 	return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39. 	int cur=0;
  40. 	for(;isspace(buf[bufpos]);bufpos++);
  41. 	for(;!isspace(buf[bufpos]);bufpos++)
  42. 		s[cur++]=buf[bufpos];
  43. 	s[cur]='\0';
  44. 	return cur;
  45. }
  46. ll ans[50001],now;
  47. int a[50001],cnt[2][50001],pl[50001];
  48. struct query{
  49. 	int p,sgn,l1,l2;
  50. 	bool operator <(const query& rhs)const{
  51. 		return pl[l1]!=pl[rhs.l1]?pl[l1]<pl[rhs.l1]:l2<rhs.l2;
  52. 	}
  53. }q[200001];
  54. void update(int p,int v,int sgn){
  55. 	now+=sgn*cnt[p^1][v];
  56. 	cnt[p][v]+=sgn;
  57. }
  58. int main(){
  59. 	init();
  60. 	int n=readint(),cur=0;
  61. 	for(int i=1;i<=n;i++)
  62. 		a[i]=readint();
  63. 	int m=readint();
  64. 	for(int i=1;i<=m;i++){
  65. 		int l1=readint()-1,r1=readint(),l2=readint()-1,r2=readint();
  66. 		if (l1)
  67. 			q[++cur]=(query){i,-1,l1,r2};
  68. 		if (l2)
  69. 			q[++cur]=(query){i,-1,l2,r1};
  70. 		if (l1 && l2)
  71. 			q[++cur]=(query){i,1,l1,l2};
  72. 		q[++cur]=(query){i,1,r1,r2};
  73. 	}
  74. 	int sz=sqrt(n)+0.5;
  75. 	for(int i=1;i<=n;i++)
  76. 		pl[i]=(i-1)/sz+1;
  77. 	sort(q+1,q+cur+1);
  78. 	int l1=0,l2=0;
  79. 	for(int i=1;i<=cur;i++){
  80. 		while(l1<q[i].l1)
  81. 			update(0,a[++l1],1);
  82. 		while(l1>q[i].l1)
  83. 			update(0,a[l1--],-1);
  84. 		while(l2<q[i].l2)
  85. 			update(1,a[++l2],1);
  86. 		while(l2>q[i].l2)
  87. 			update(1,a[l2--],-1);
  88. 		ans[q[i].p]+=now*q[i].sgn;
  89. 	}
  90. 	for(int i=1;i<=m;i++)
  91. 		printf("%lld\n",ans[i]);
  92. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2017/08/02/loj2254/

隐藏