fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. #define f first
  6. #define s second
  7. #define pb push_back
  8. #define ep emplace
  9. #define eb emplace_back
  10. #define lb lower_bound
  11. #define ub upper_bound
  12. #define all(x) x.begin(), x.end()
  13. #define rall(x) x.rbegin(), x.rend()
  14. #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
  15. #define mem(f,x) memset(f , x , sizeof(f))
  16. #define sz(x) (ll)(x).size()
  17. #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
  18. #define mxx *max_element
  19. #define mnn *min_element
  20. #define cntbit(x) __builtin_popcountll(x)
  21. #define len(x) (int)(x.length())
  22.  
  23. const int N = 1e6 + 10;
  24. const int M = 3e5 + 10;
  25.  
  26. int A[M], B[M], mx[M], mn[M], pos[M], ans[N];
  27. vector <pair <int, int>> ask[M], add[M];
  28.  
  29. struct seg{
  30. vector <int> seg;
  31. void ass(int n) {
  32. seg.assign(n * 4 + 100, 0);
  33. }
  34.  
  35. void upd(int id, int l, int r, int p, int v) {
  36. seg[id] = max(seg[id], v);
  37. if (l == r)
  38. return;
  39.  
  40. int m = (l + r) / 2;
  41. if (m >= p) {
  42. upd(id * 2, l, m, p, v);
  43. } else {
  44. upd(id * 2 + 1, m + 1, r, p, v);
  45. }
  46. }
  47.  
  48. int get(int id, int l, int r, int u, int v) {
  49. if (l > v || r < u)
  50. return 0;
  51.  
  52. if (l >= u && r <= v)
  53. return seg[id];
  54.  
  55. int m = (l + r) / 2;
  56. return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
  57. }
  58. };
  59.  
  60. int find_mex(int n, int x, int y) {
  61. int l = 0, r = n - 1, ans = -1;
  62. while (l <= r) {
  63. int m = (l + r) / 2;
  64. if (mn[m] >= x && mx[m] <= y) {
  65. ans = m;
  66. l = m + 1;
  67. } else {
  68. r = m - 1;
  69. }
  70. }
  71.  
  72. return ans + 1;
  73. }
  74.  
  75. void cal(int n) {
  76. seg seg;
  77. seg.ass(n);
  78. for (int i = 1; i <= n; i++) {
  79. mx[B[i]] = mn[B[i]] = i;
  80. pos[A[i]] = i;
  81. }
  82.  
  83. for (int i = 1; i < n; i++) {
  84. mx[i] = max(mx[i - 1], mx[i]);
  85. mn[i] = min(mn[i - 1], mn[i]);
  86. }
  87.  
  88. int l = n, r = 1;
  89. for (int i = 0; i < n; i++) {
  90. l = min(l, pos[i]);
  91. r = max(r, pos[i]);
  92. add[r].pb({l, i + 1 - find_mex(n, l, r)});
  93. }
  94.  
  95. for (int i = 1; i <= n; i++) {
  96. for (auto x : add[i]) {
  97. seg.upd(1, 1, n, x.f, x.s);
  98. }
  99.  
  100. for (auto x : ask[i]) {
  101. ans[x.s] = max(seg.get(1, 1, n, x.f, i), ans[x.s]);
  102. }
  103.  
  104. add[i].clear();
  105. }
  106. }
  107.  
  108. void solve() {
  109. int n;
  110. cin >> n;
  111.  
  112. for (int i = 1; i <= n; i++)
  113. cin >> A[i];
  114.  
  115. for (int i = 1; i <= n; i++)
  116. cin >> B[i];
  117.  
  118. int q;
  119. cin >> q;
  120.  
  121. for (int i = 1; i <= q; i++) {
  122. int l, r;
  123. cin >> l >> r;
  124. ask[r].pb({l, i});
  125. }
  126.  
  127. cal(n);
  128. for (int i = 1; i <= n; i++) {
  129. swap(A[i], B[i]);
  130. }
  131.  
  132. cal(n);
  133. for (int i = 1; i <= n; i++)
  134. ask[i].clear();
  135.  
  136. for (int i = 1; i <= q; i++) {
  137. cout << ans[i] << "\n";
  138. ans[i] = 0;
  139. }
  140. }
  141.  
  142. int main() {
  143. ios_base::sync_with_stdio(0);
  144. cin.tie(0);
  145. cout.tie(0);
  146.  
  147. int t;
  148. cin >> t;
  149.  
  150. while (t--) {
  151. solve();
  152. }
  153.  
  154. return 0;
  155. }
  156.  
  157. // ab a
Time limit exceeded #stdin #stdout 5s 18772KB
stdin
Standard input is empty
stdout
Standard output is empty