Advertisement
skimono

Untitled

Sep 17th, 2023
1,054
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.93 KB | None | 0 0
  1. #pragma GCC optimize("Ofast") // ������������ ���������, �� ��� ������
  2. #pragma GCC optimize("no-stack-protector") //�����
  3. #pragma GCC optimize("unroll-loops") // � ���� ���� ��� �� 100 �� ������ ����� � ��������� �� ��� � 100 ��� �� ������ ��������
  4. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") // ��� ����� ����� �� ��� 03 02 ��������� � ������ ������� �������� ��� ���� ������������
  5. #pragma GCC optimize("fast-math")
  6. #define _CRT_SECURE_NO_WARNINGS
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <string>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <stack>
  14. #include <iomanip>
  15. #include <fstream>
  16. #include <string>
  17. #include <set>
  18. #include <deque>
  19. #include <queue>
  20. #include <map>
  21. #include <bitset>
  22. #include <random>
  23. #include <list>
  24. #include <unordered_map>
  25. #include <unordered_set>
  26. #include <cassert>
  27.  
  28. using namespace std;
  29.  
  30. typedef long long ll;
  31. typedef short sh;
  32. typedef unsigned long long ull;
  33. typedef long double ld;
  34. typedef string str;
  35. //typedef __int128 ultraint;
  36. #define sqrt sqrtl
  37. #define F first
  38. #define S second
  39. #define endl '\n'
  40. #define all(vc666) vc666.begin(), vc666.end()
  41. #define allr(vc666) vc666.rbegin(), vc666.rend()
  42. #define int long long
  43. #define degug(x) cerr (#x) << " " << (x) << endl;
  44.  
  45. const ll INF = 2e18;
  46. const ll inf = 2e9 + 3;
  47. const ll ONE = 1, ZERO = 0;
  48. const ll mod = 998244353;
  49. const ll m1 = 1e9 + 575179;
  50. const ll m2 = 1e9 + 87;
  51. const ll LG = 19;
  52. const ll k = 1;
  53. const ll p = 79;
  54. ld EPS = 1e-9;
  55. ld PI = 3.1415926535897932384;
  56. ld phi = (sqrt(5) + 1.0) / 2.0;
  57. mt19937_64 rnd(4906);
  58.  
  59. struct Query {
  60.     int l, r, idx;
  61. };
  62.  
  63. const int N = 1e5 + 3;
  64. pair <int, int> pw[N];
  65. pair <int, int> h[N];
  66. map <int, int> keys[N];
  67. vector <int> base[N], base2[N];
  68. int ans[N];
  69. Query Q[N];
  70.  
  71. pair <int, int> get_h(int l, int r) {
  72.     return { (h[r + 1].first - (h[l].first * pw[r - l + 1].first) % m1 + m1) % m1, (h[r + 1].second - (h[l].second * pw[r - l + 1].second) % m2 + m2) % m2 };
  73. }
  74.  
  75. bool cmp(const Query& a, const Query& b) {
  76.     if (a.l / k != b.l / k) {
  77.         return a.l < b.l;
  78.     }
  79.     else {
  80.         return a.r < b.r;
  81.     }
  82. }
  83.  
  84. void solve() {
  85.     string t, s;
  86.     int n, len_t, len_s, len, i, j, m, l, r, q, res, lst = -1;
  87.     cin >> t;
  88.     len_t = t.size();
  89.     pw[0] = { 1, 1 };
  90.     h[0] = { 0, 0 };
  91.     for (i = 1; i <= len_t; i++) {
  92.         pw[i].first = (pw[i - 1].first * p) % m1;
  93.         pw[i].second = (pw[i - 1].second * p) % m2;
  94.         h[i].first = (h[i - 1].first * p + (t[i - 1] - 'a' + ONE)) % m1;
  95.         h[i].second = (h[i - 1].second * p + (t[i - 1] - 'a' + ONE)) % m2;
  96.     }
  97.     pair <int, int> hesh;
  98.     vector <int> rzl;
  99.     cin >> n;
  100.     for (i = 0; i < n; i++) {
  101.         cin >> s;
  102.         len_s = s.size();
  103.         rzl.push_back(len_s);
  104.         hesh = { 0, 0 };
  105.         for (j = 0; j < len_s; j++) {
  106.             hesh.first = (hesh.first * p + (s[j] - 'a' + ONE)) % m1;
  107.             hesh.second = (hesh.second * p + (s[j] - 'a' + ONE)) % m2;
  108.         }
  109.         keys[len_s][hesh.first * m1 + hesh.second] = i;
  110.     }
  111.     sort(all(rzl));
  112.     rzl.resize(unique(all(rzl)) - rzl.begin());
  113.     m = rzl.size();
  114.     for (i = 0; i < len_t; i++) {
  115.         for (j = 0; j < m; j++) {
  116.             len = rzl[j];
  117.             if (i + len - 1 < len_t) {
  118.                 hesh = get_h(i, i + len - 1);
  119.                 if (keys[len].contains(hesh.first * m1 + hesh.second)) {
  120.                     base[i].push_back(len);
  121.                     base2[i + len - 1].push_back(len);
  122.                 }
  123.             }
  124.         }
  125.     }
  126.     for (i = 0; i < len_t; i++) {
  127.         sort(all(base2[i]));
  128.     }
  129.     cin >> q;
  130.     for (i = 0; i < q; i++) {
  131.         cin >> Q[i].l >> Q[i].r;
  132.         Q[i].idx = i;
  133.         Q[i].l--;
  134.         Q[i].r--;
  135.     }
  136.     sort(Q, Q + q, cmp);
  137.     int left, right, last_r, last_l;
  138.     for (i = 0; i < q; i++) {
  139.         if (Q[i].l / k != lst) {
  140.             lst = Q[i].l / k;
  141.             l = Q[i].l;
  142.             r = Q[i].l - 1;
  143.             res = 0;
  144.         }
  145.         last_r = r;
  146.         last_l = l;
  147.         for (r; r < Q[i].r; r++) {
  148.             left = -1, right = base2[r + 1].size();
  149.             while (right - left > 1) {
  150.                 m = (left + right) / 2;
  151.                 if (r + 1 - base2[r + 1][m] + 1 >= last_l) {
  152.                     left = m;
  153.                 }
  154.                 else {
  155.                     right = m;
  156.                 }
  157.             }
  158.             res += right;
  159.         }
  160.         for (l; l > Q[i].l; l--) {
  161.             left = -1, right = base[l - 1].size();
  162.             while (right - left > 1) {
  163.                 m = (left + right) / 2;
  164.                 if (l - 1 + base[l - 1][m] - 1 <= r) {
  165.                     left = m;
  166.                 }
  167.                 else {
  168.                     right = m;
  169.                 }
  170.             }
  171.             res += right;
  172.         }
  173.         for (l; l < Q[i].l; l++) {
  174.             left = -1, right = base[l].size();
  175.             while (right - left > 1) {
  176.                 m = (left + right) / 2;
  177.                 if (l + base[l][m] - 1 <= r) {
  178.                     left = m;
  179.                 }
  180.                 else {
  181.                     right = m;
  182.                 }
  183.             }
  184.             res -= right;
  185.         }
  186.         ans[Q[i].idx] = res;
  187.     }
  188.     for (i = 0; i < q; i++) {
  189.         cout << ans[i] << " ";
  190.     }
  191. }
  192.  
  193. signed main() {
  194. #ifdef _DEBUG
  195.     freopen("input.txt", "r ", stdin);
  196.     freopen("output.txt", "w", stdout);
  197. #endif
  198.     ios_base::sync_with_stdio(0);
  199.     cin.tie(NULL);
  200.     cout.tie(NULL);
  201.     int t = 1;
  202.     //cin >> t;
  203.     while (t--) solve();
  204. }
  205. //Deisgned by skimono
  206. //Клуб "Кольца(Серьги)"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement