阿里云可以做电影网站吗,导视设计原则,拓者设计吧免费注册,网站交易平台建设一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
522D - Closest Equals 二、解题报告
1、思路分析
考虑查询区间已经给出#xff0c;我们可以离线查询
对于这类区间离线查询的问题我们通常可以通过左端点排序#xff0c;然后遍历询问同时维护左区间信息…一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
522D - Closest Equals 二、解题报告
1、思路分析
考虑查询区间已经给出我们可以离线查询
对于这类区间离线查询的问题我们通常可以通过左端点排序然后遍历询问同时维护左区间信息来完成
我们考虑可以预处理出d[], d[i]代表a[i]和其左边最近的相等的值的距离如果没有就置为n
然后线段树维护区间最值
预处理nxt[i]即a[i]下一个出现位置
考虑将询问按照左端点升序排序
遍历查询q如果当前遍历到的l q[i].l我们就右扩展左区间同时modify nxt[l]为正无穷
然后查询区间[l, r]的最值即可
2、复杂度 时间复杂度 O(NlogN MlogN)空间复杂度O(N) 3、代码详解
#include bits/stdc.h
using i64 long long;
using i128 __int128;
using PII std::pairint, int;
const int inf 1e9 7, P 1e9 7;templateclass Info
struct SegmentTree {int n;std::vectorInfo info;SegmentTree(int _n): n(_n), info(2 (32 - __builtin_clz(_n))) {}SegmentTree(std::vectorInfo _init): SegmentTree(_init.size()) {auto build [](auto self, int p, int l, int r) {if (l r) {info[p] _init[l];return;}int mid l r 1;self(self, p 1, l, mid), self(self, p 1 | 1, mid 1, r);pull(p);};build(build, 1, 0, n - 1);}void pull(int p) {info[p] info[p 1] info[p 1 | 1];}void modify(int p, int l, int r, int x, const Info v) {if (l r) {info[p] v;return;}int mid l r 1;if (x mid) modify(p 1, l, mid, x, v);else modify(p 1 | 1, mid 1, r, x, v);pull(p);}void modify(int x, const Info v) {modify(1, 0, n - 1, x, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l y || r x) return Info();if (x l r y) return info[p];int mid l r 1;return rangeQuery(p 1, l, mid, x, y) rangeQuery(p 1 | 1, mid 1, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n - 1, l, r);}};
struct Info {int x inf;Info operator (const Info b) const {return { std::min(x, b.x) };}
};void solve() {int n, m;std::cin n m;std::vectorint a(n), nxt(n, n);std::mapint, int last;for (int i 0; i n; i ) {std::cin a[i];if (last.count(a[i]))nxt[last[a[i]]] i;last[a[i]] i;}std::vectorInfo d(n);for (int i 0; i n; i )if (nxt[i] n) d[nxt[i]] { nxt[i] - i };SegmentTreeInfo sgt(d);std::vectorstd::arrayint, 3 q(m);std::vectorint ans(m);for (int i 0, l, r; i m; i ) std::cin l r, q[i] { l, r, i };std::sort(q.begin(), q.end(), [](auto x, auto y) {return x[0] y[0];});for (int i 0, st 0; i m; i ) {auto [l, r, id] q[i];-- l, -- r;while (st l) {if (nxt[st] n)sgt.modify(nxt[st], Info()); st;}ans[id] sgt.rangeQuery(l, r).x;}for (int x : ans) std::cout (x inf ? x : -1) \n;
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ 1;// std::cin _;while (_ --)solve();return 0;
}
