Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef LOCAL
- #include <iostream>
- #include <fstream>
- #include <iomanip>
- #include <random>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <set>
- #include <map>
- #else
- #pragma GCC optimize("Ofast,unroll-loops")
- #include <bits/stdc++.h>
- #define cerr if (false) cerr
- #define endl '\n'
- #endif
- #define fi first
- #define se second
- #define sz(a) ((int)(a).size())
- #define all(a) (a).begin(), (a).end()
- #define lsb(x) (x & (-x))
- #define bit(mask, i) (((mask) >> (i)) & 1)
- #define popcount(x) __builtin_popcount(x)
- #define YES cout << "YES" << endl
- #define NO cout << "NO" << endl
- using namespace std;
- template <typename T>
- bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
- template <typename T>
- bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }
- using ll = long long;
- using pii = pair<int, int>;
- const int NMAX = 5e5+5;
- const int NIL = -1;
- struct Node {
- int min;
- int lchild, rchild;
- };
- int szv;
- Node v[23 * NMAX];
- void v_push_back(Node node) {
- v[szv++] = node;
- }
- struct SegTree {
- int n;
- vector<int> roots;
- SegTree(int _n): n(_n), roots({ build(1, _n) }) { }
- int build(int l, int r) {
- if (l >= r) {
- Node node = { NMAX, NIL, NIL };
- v_push_back(node);
- return szv - 1;
- }
- int mid = (l + r) >> 1;
- Node node = { NMAX, build(l, mid), build(mid + 1, r) };
- v_push_back(node);
- return szv - 1;
- }
- void update_val(int k, int pos, int val) {
- roots[k] = update_val(roots[k], 1, n, pos, val);
- }
- int update_val(int u, int l, int r, int pos, int val) {
- if (pos < l || r < pos) return u;
- if (l >= r) {
- v_push_back({ val, NIL, NIL });
- return szv - 1;
- }
- int mid = (l + r) >> 1;
- Node node = { 0,
- update_val(v[u].lchild, l, mid, pos, val),
- update_val(v[u].rchild, mid + 1, r, pos, val)
- };
- node.min = min(v[node.lchild].min, v[node.rchild].min);
- v_push_back(node);
- return szv - 1;
- }
- int query_min(int k, int l, int r) {
- int ret = query_min(roots[k], 1, n, l, r);
- return ret == NMAX ? -1 : ret;
- }
- int query_min(int u, int l, int r, int ll, int rr) {
- if (ll <= l && r <= rr) return v[u].min;
- int mid = (l + r) >> 1;
- int ret = NMAX;
- if (ll <= mid) ret = query_min(v[u].lchild, l, mid, ll, rr);
- if (mid < rr) ret = min(ret, query_min(v[u].rchild, mid + 1, r, ll, rr));
- return ret;
- }
- void update_copy(int k) {
- v_push_back(v[roots[k]]);
- roots.push_back(szv - 1);
- }
- };
- int n, m;
- int a[NMAX];
- vector<int> intervals[NMAX];
- void read() {
- cin >> n >> m;
- for (int i = 1; i <= n; i++)
- cin >> a[i];
- }
- void solve() {
- map<int, int> last_pos;
- for (int i = 1; i <= n; i++) {
- if (last_pos[a[i]] != 0)
- intervals[i].push_back(last_pos[a[i]]);
- last_pos[a[i]] = i;
- }
- last_pos.clear();
- SegTree tree = SegTree(n);
- for (int r = 1; r <= n; r++) {
- tree.update_copy(r - 1);
- for (auto &l : intervals[r])
- tree.update_val(r, l, r - l);
- }
- while (m--) {
- int l, r;
- cin >> l >> r;
- cout << tree.query_min(r, l, r) << endl;
- }
- }
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- read();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement