fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int N = 123456;
  5. ll P = 999999929;//1585931419LL;
  6. ll MOD = 1000000007LL;
  7. ll p[N], par[N], Hash[N], cp[N];
  8. void pre(){
  9. 	p[0] = cp[0]=1LL;
  10. 	for(int i = 1; i<N; i++){
  11. 		p[i] = (p[i-1] * P) % MOD;
  12. 		cp[i] = (cp[i-1] + p[i])%MOD;
  13. 	}
  14. }
  15.  
  16. void hashParent(int sz){
  17. 	for(int i = 1; i<=sz; i++)
  18. 		Hash[i] = (par[i-1] * p[i-1]) % MOD;
  19.  
  20. 	for (int i = 1; i<=sz; i++)
  21. 		Hash[i] = (Hash[i] + Hash[i-1]) % MOD;
  22. }
  23. ll hashPattern(int l, int r){
  24. 	ll hp = 0LL;
  25. 	for(int i = l; i<=r; i++)
  26. 		hp = (hp + par[i-1] * p[i-l]) % MOD;
  27. 	return hp;
  28. }
  29. void solve()
  30. {
  31. 	int n;
  32. 	cin >> n;
  33. 	for (int i = 0; i<n; i++)
  34. 		cin >> par[i];
  35. 	hashParent(n);
  36.  
  37. 	int q;
  38. 	cin >> q;
  39. 	while (q--){
  40. 		int l, r, cnt = 0;
  41. 		cin >> l >> r;
  42. 		int sz = r-l+1;
  43. 		ll hp = hashPattern(l, r);
  44.  
  45. 		for (int i = 0; i + sz < l; i++){
  46. 			ll part = (Hash[i+sz] - Hash[i] + MOD) % MOD;
  47. 			ll z = (par[l-1] + par[i]) % MOD;
  48. 			z = (z * cp[sz-1]) % MOD;
  49. 			ll cmp = (z - hp + MOD) % MOD;
  50. 			if (part == (cmp * p[i])%MOD)
  51. 			++cnt;
  52. 		}
  53. 		for(int i = r; i + sz <= n; i++){
  54. 			ll part = (Hash[i+sz] - Hash[i] + MOD) % MOD;
  55. 			ll z = (par[l-1] + par[i]);
  56. 			z = (z * cp[sz-1]) % MOD;
  57. 			ll cmp = (z - hp + MOD) % MOD;
  58. 			if (part == (cmp * p[i]) % MOD)
  59. 				++cnt;
  60. 		}
  61. 		cout << cnt << endl;
  62. 	}
  63. }
  64.  
  65. int main()
  66. {
  67. 	pre();
  68. 	solve();
  69. 	return 0;
  70. }	
  71.  
  72.  
Success #stdin #stdout 0.01s 6960KB
comments (?)
stdin
copy 
8
1 2 2 1 100 99 99 100
3
1 4
1 2
3 4
stdout
copy 
1
2
2
https://ideone.com/9bZYxj
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!