fork(13) 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. inline int64_t gilbertOrder(int x, int y, int pow, int rotate) {
  62. if (pow == 0) {
  63. return 0;
  64. }
  65. int hpow = 1 << (pow-1);
  66. int seg = (x < hpow) ? (
  67. (y < hpow) ? 0 : 3
  68. ) : (
  69. (y < hpow) ? 1 : 2
  70. );
  71. seg = (seg + rotate) & 3;
  72. const int rotateDelta[4] = {3, 0, 0, 1};
  73. int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  74. int nrot = (rotate + rotateDelta[seg]) & 3;
  75. int64_t subSquareSize = int64_t(1) << (2*pow - 2);
  76. int64_t ans = seg * subSquareSize;
  77. int64_t add = gilbertOrder(nx, ny, pow-1, nrot);
  78. ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  79. return ans;
  80. }
  81.  
  82. struct Query {
  83. int l, r, idx;
  84. int64_t ord;
  85.  
  86. inline void calcOrder() {
  87. ord = gilbertOrder(l, r, 21, 0);
  88. }
  89. };
  90.  
  91. inline bool operator<(const Query &a, const Query &b) {
  92. return a.ord < b.ord;
  93. }
  94.  
  95. signed main() {
  96. #ifndef USE_FILE_IO
  97. ios_base::sync_with_stdio(false);
  98. #endif
  99.  
  100. mt19937 rnd(42);
  101.  
  102. int n, m, k; cin >> n >> m; k = rnd() % 1048576;
  103. vector<int> p(n+1);
  104. for (int i = 0; i < n; i++) {
  105. int val = rnd() % 1048576;
  106. p[i+1] = p[i] ^ val;
  107. }
  108.  
  109. vector<Query> qry(m);
  110. for (int i = 0; i < m; i++) {
  111. int l = rnd() % n + 1, r = rnd() % n + 1;
  112. if (l > r) {
  113. swap(l, r);
  114. }
  115. qry[i].l = l; qry[i].r = r;
  116. qry[i].idx = i;
  117. qry[i].calcOrder();
  118. }
  119.  
  120. int64_t ans = 0;
  121. vector<int64_t> res(m);
  122. vector<int64_t> cnt((int)2e6, 0);
  123. sort(qry.begin(), qry.end());
  124. int l = 0, r = 1;
  125. ans = (p[1] == k);
  126. cnt[p[0]]++; cnt[p[1]]++;
  127.  
  128. for (Query q: qry) {
  129. q.l--;
  130. while (l > q.l) {
  131. l--;
  132. ans += cnt[p[l] ^ k];
  133. cnt[p[l]]++;
  134. }
  135. while (r < q.r) {
  136. r++;
  137. ans += cnt[p[r] ^ k];
  138. cnt[p[r]]++;
  139. }
  140. while (l < q.l) {
  141. cnt[p[l]]--;
  142. ans -= cnt[p[l] ^ k];
  143. l++;
  144. }
  145. while (r > q.r) {
  146. cnt[p[r]]--;
  147. ans -= cnt[p[r] ^ k];
  148. r--;
  149. }
  150. res[q.idx] = ans;
  151. }
  152.  
  153. uint64_t rhsh = 0;
  154. for (int i = 0; i < m; i++) {
  155. rhsh *= (uint64_t)1e9 + 7;
  156. rhsh += (uint64_t)res[i];
  157. }
  158. cout << rhsh << "\n";
  159.  
  160. return 0;
  161. }
  162.  
Success #stdin #stdout 2.5s 15240KB
stdin
400000 400000
stdout
18318053225040230409