U604938 你不准卡 O(n sqrt n log L) 其中 L log L = sqrt n
如题目所言，这道题的出现就是为此，所以不要说什么 wyy。
首先是空间上卡掉了 \(n\sqrt n\) 空间的做法，然后因为值域限制卡掉了回滚莫队（也许只是我菜才不会写？）。总之再有什么我也没法了，就这样。
如果你要卡常
请确保您是 \(（O(n\sqrt n \log L)，其中L \log L = \sqrt n)\) 或更优的复杂度！！！
inline，static，快读。- 莫队奇偶性排序。
- 读入大数字用
scanf比快读快。 - 少写函数，哪怕
inline，都扔主函数里（我是错误示范，up，qry都是可以扔的）。 - 数组的定义顺序和数组大小也会影响时间。
- 不行就抄吧，也许是码风问题。
正文
首先这是个区间问题显然可以用莫队来做，然后就是要维护区间特定值域内最小众数，按理来讲有很多办法可以维护，但是就是要用线段树！！！
考虑用权值线段树，维护每一个值出现的次数，然后维护最大次数以及其值，结合动态开点显然可以做到 \(O(\log V)\) 的修改和查询。
但是过不了呢！
考虑离散化，这个也显然，可以做到 \(O(\log n)\) 的修改和查询。
还是过不了呢！！
考虑到查询很少，修改很多，可以稍微平衡一下两者，对值域分块，每一个块使用一个线段树维护，可以做到 \(O(\log \sqrt n)\) 修改，\(O(\sqrt n)\) 查询，已经很优秀了的！
就是过不了哦！！！
我所追求的，是真正的平衡；（好中二，算了）
显然修改次数是 \(n\sqrt n\) 的，查询次数是 \(n\) 的，上一步我们已经平衡了一部分，但是还不够，设值域分块中线段树的长度为 \(L\)，容易得到两种操作的总复杂度分别为 \(O(n\sqrt n \log L)\) 和 \(O(n\frac nL)\)，强行将两者调平，得到 \(L\log L=\sqrt n\) 时复杂度最优秀。
不过，这依然无法！……好吧过了。（原来是过不了的，后来仁慈了）
其实不要仅停留在理论，两个式子是有着隐藏的系数的，没错，就是常数。大概是这样的 \(O(n\sqrt n \log L \times (线段树大常数))\) 和 \(O(n\frac nL \times(分块跑不满小常数))\)，所以显然 \(L\) 要比上面理论算出来的要更小一些才行。
最后再来重申一遍我们的复杂度！！！
\(\Large O(n\sqrt n \log L)，其中(L \log L = \sqrt n)！！！\)
代码
// code by 樓影沫瞬_Hz17
#include <bits/stdc++.h>
#define en_ putchar_unlocked('\n')
#define e_ putchar_unlocked(' ')
using namespace std;
inline int in() { int n = 0; char p = getchar_unlocked();while (p < '-') p = getchar_unlocked();bool f = p == '-' ? p = getchar_unlocked() : 0;do n = n * 10 + (p ^ 48), p = getchar_unlocked();while (p >= '0');return f ? -n : n;
}
inline int in(int &a) { return a = in(); }
inline void out(int n) {if(n < 0) putchar_unlocked('-'), n = -n;if(n > 9) out(n / 10);putchar_unlocked(n % 10 + '0');
}
constexpr int N = 2e5 + 10, B1 = 400, B2 = 60;
using pii = pair<int, int>;int ls[N * 4], rs[N * 4], mx[N * 4], id[N * 4];struct Query {int l, r, L, R, id;
} q[N];int a[N], hs[N], pos1[N], pos2[N];int rt[3010], L[3010], R[3010], cnt, n, cntv;inline void build(int &u, const int l, const int r) {u = ++ cnt;if(l == r) { id[u] = l;return;}int m = (l + r) >> 1;build(ls[u], l, m);build(rs[u], m + 1, r);mx[u] = mx[ls[u]], id[u] = id[ls[u]];
}inline void up(int u) {if(mx[ls[u]] >= mx[rs[u]]) {mx[u] = mx[ls[u]], id[u] = id[ls[u]];return;}mx[u] = mx[rs[u]], id[u] = id[rs[u]];
}inline void update(const int u, const int l, const int r, const int p) {if(l == r) {++ mx[u];return;}int m = (l + r) >> 1;if(p <= m) update(ls[u], l, m, p);if(p > m) update(rs[u], m + 1, r, p);up(u);
}inline void reduce(const int u, const int l, const int r, const int p) {if(l == r) {-- mx[u];return;}int m = (l + r) >> 1;if(p <= m) reduce(ls[u], l, m, p);if(p > m) reduce(rs[u], m + 1, r, p);up(u);
}inline pii query(const int u, const int l, const int r, const int L, const int R) {if(L > r || l > R) return {0, 0};if(L <= l and r <= R) return {mx[u], id[u]};int m = (l + r) >> 1;pii t1 = query(ls[u], l, m, L, R), t2 = query(rs[u], m +1, r, L, R);return t1.first >= t2.first ? t1 : t2;
}int ans[N];inline int qry(int l, int r) {int ql = pos2[l], qr = pos2[r], MX = 0, ID = 0;if(ql != qr) {pii t = query(rt[ql], L[ql], R[ql], l, R[ql]);if(t.first > MX) MX = t.first, ID = t.second;for(int i = ql + 1; i < qr; i ++) if(mx[rt[i]] > MX) MX = mx[rt[i]], ID = id[rt[i]];t = query(rt[qr], L[qr], R[qr], L[qr], r);if(t.first > MX) MX = t.first, ID = t.second;}if(ql == qr) {pii t = query(rt[ql], L[ql], R[ql], l, r);if(t.first) ID = t.second;}return ID;
}signed main() {#ifndef ONLINE_JUDGE freopen("5.in", "r", stdin);freopen("5.out", "w", stdout);#endifin(n);for(int i = 1; i <= n; i ++) hs[i] = in(a[i]);for(int i = 1; i <= n; i ++) in(q[i].l), in(q[i].r), in(q[i].L), in(q[i].R), q[i].id = i, pos1[i] = (i - 1) / B1 +1;for(int i = 1; R[i - 1] != n; i ++) {L[i] = (i - 1) * B2 + 1, R[i] = min(i * B2, n);for(int j = L[i]; j <= R[i]; j ++) pos2[j] = i;build(rt[i], L[i], R[i]);}sort(q + 1, q + 1 + n, [](const Query &a, const Query &b) { return pos1[a.l] == pos1[b.l] ? pos1[a.l] & 1 ? a.r < b.r : a.r > b.r : pos1[a.l] < pos1[b.l];});sort(hs + 1, hs + 1 + n);int len = unique(hs + 1, hs + 1+ n) - hs - 1;for(int i = 1; i <= n; i ++) {a[i] = lower_bound(hs + 1, hs + len + 1, a[i]) - hs;q[i].L = lower_bound(hs + 1, hs + len + 1, q[i].L) - hs;q[i].R = lower_bound(hs + 1, hs + len + 1, q[i].R) - hs;}for(int i = 1, l = 1, r = 0; i <= n; i ++) {while(l < q[i].l) reduce(rt[pos2[a[l]]], L[pos2[a[l]]], R[pos2[a[l]]], a[l]), ++ l;while(l > q[i].l) -- l, update(rt[pos2[a[l]]], L[pos2[a[l]]], R[pos2[a[l]]], a[l]);while(r < q[i].r) ++ r, update(rt[pos2[a[r]]], L[pos2[a[r]]], R[pos2[a[r]]], a[r]);while(r > q[i].r) reduce(rt[pos2[a[r]]], L[pos2[a[r]]], R[pos2[a[r]]], a[r]), -- r;ans[q[i].id] = qry(q[i].L, q[i].R);}for(int i = 1; i <= n; i ++) {if(!ans[i]) putchar_unlocked('-');if(ans[i]) out(hs[ans[i]]);en_;}
}
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~
 其中 L log L = sqrt n)
