fork(1) download
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <chrono>
  5. #include <climits>
  6. #include <cstdint>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <cstring>
  10. #include <ctime>
  11. #include <deque>
  12. #include <fstream>
  13. #include <functional>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <map>
  17. #include <numeric>
  18. #include <queue>
  19. #include <random>
  20. #include <set>
  21. #include <stack>
  22. #include <sstream>
  23. #include <tuple>
  24. #include <vector>
  25.  
  26. using namespace std;
  27. using namespace chrono;
  28.  
  29. #ifdef DEBUG
  30. //#define LOCAL_INPUT_FILE
  31. #else
  32. //#define USE_FILE_IO
  33. #endif
  34.  
  35. #ifdef USE_FILE_IO
  36. #define INPUT_FILE "input.txt"
  37. #define OUTPUT_FILE "output.txt"
  38. #define cin ____cin
  39. #define cout ____cout
  40. ifstream cin(INPUT_FILE);
  41. ofstream cout(OUTPUT_FILE);
  42. #else
  43. #ifdef LOCAL_INPUT_FILE
  44. #define cin ____cin
  45. ifstream cin("input.txt");
  46. #endif
  47. #endif
  48.  
  49. const int infinity = (int)1e9 + 42;
  50. const int64_t llInfinity = (int64_t)1e18 + 256;
  51. const int module = (int)1e9 + 7;
  52. const long double eps = 1e-8;
  53.  
  54. mt19937_64 randGen(system_clock().now().time_since_epoch().count());
  55.  
  56. inline void raiseError(string errorCode) {
  57. cerr << "Error : " << errorCode << endl;
  58. exit(42);
  59. }
  60.  
  61. int block = 200;
  62.  
  63. struct Query {
  64. int l, r, idx;
  65.  
  66. inline pair<int, int> toPair() const {
  67. return make_pair(l / block, ((l / block) & 1) ? -r : +r);
  68. }
  69. };
  70.  
  71. inline bool operator<(const Query &a, const Query &b) {
  72. return a.toPair() < b.toPair();
  73. }
  74.  
  75. signed main() {
  76. #ifndef USE_FILE_IO
  77. ios_base::sync_with_stdio(false);
  78. #endif
  79.  
  80. mt19937 rnd(42);
  81.  
  82. int n, m, k; cin >> n >> m; k = rnd() % 1048576;
  83. vector<int> p(n+1);
  84. for (int i = 0; i < n; i++) {
  85. int val = rnd() % 1048576;
  86. p[i+1] = p[i] ^ val;
  87. }
  88. block = sqrt(n) + 1;
  89.  
  90. vector<Query> qry(m);
  91. for (int i = 0; i < m; i++) {
  92. int l = rnd() % n + 1, r = rnd() % n + 1;
  93. if (l > r) {
  94. swap(l, r);
  95. }
  96. qry[i].l = l; qry[i].r = r;
  97. qry[i].idx = i;
  98. }
  99.  
  100. int64_t ans = 0;
  101. vector<int64_t> res(m);
  102. vector<int64_t> cnt((int)2e6, 0);
  103. sort(qry.begin(), qry.end());
  104. int l = 0, r = 1;
  105. ans = (p[1] == k);
  106. cnt[p[0]]++; cnt[p[1]]++;
  107.  
  108. for (Query q: qry) {
  109. while (l > q.l) {
  110. l--;
  111. ans += cnt[p[l] ^ k];
  112. cnt[p[l]]++;
  113. }
  114. while (r < q.r) {
  115. r++;
  116. ans += cnt[p[r] ^ k];
  117. cnt[p[r]]++;
  118. }
  119. while (l < q.l) {
  120. cnt[p[l]]--;
  121. ans -= cnt[p[l] ^ k];
  122. l++;
  123. }
  124. while (r > q.r) {
  125. cnt[p[r]]--;
  126. ans -= cnt[p[r] ^ k];
  127. r--;
  128. }
  129. res[q.idx] = ans;
  130. }
  131.  
  132. uint64_t rhsh = 0;
  133. for (int i = 0; i < m; i++) {
  134. rhsh *= (uint64_t)1e9 + 7;
  135. rhsh += (uint64_t)res[i];
  136. }
  137. cout << rhsh << "\n";
  138.  
  139. return 0;
  140. }
  141.  
Success #stdin #stdout 2.46s 27760KB
stdin
400000 400000
stdout
4675657410287817021