https://acm.hdu.edu.cn/showproblem.php?pid=3333https://acm.hdu.edu.cn/showproblem.php?pid=3333https://vjudge.net.cn/problem/HDU-3333https://vjudge.net.cn/problem/HDU-3333
题目很简单,给出长度为N的数组,Q次询问,每次给出区间[x, y), 问该区间内不同数字的和
思路:
预处理, 记录每个a[i]对应的最近相等值(max { k | k < i && a[k] == a[i])
for(int i {}; i < N; ++i) near[i] = last[a[i]], last[a[i]] = i;
只需在更新过程中,同时维护当前时刻,value of a[i]最后出现的下标即可
注意到这里的last[a[i]]有越界风险(max {a[i]} == INT_MAX)
需要离散化
枚举每个询问区间[x, y),对于a[i], 如果有near[i] < x, 意味着原数组最近一次出现value of a[i]不在该区间[x, y)内,也就意味着a[i]是区间中第一个出现的元素,可以被记录
由于每个区间可能有重叠,这时需要采用贪心思路和区间合并的思路,对区间左端点排序,依照次序依次处理询问区间,得到答案
具体看代码
- #include
- #include
- #include
-
- constexpr auto __MAX__ { static_cast<int>(1e5) };
- //数组长度最大值
-
- constexpr auto __QUERIES__ { static_cast<int>(1e3) };
- //询问最大次数
-
- std::array<int, __MAX__ + 1> sequence {};
-
- std::array<int, __QUERIES__ + 1> x {};
- //询问区间左端点(闭)
- std::array<int, __QUERIES__ + 1> y {};
- //询问区间右端点(开)
-
- std::array<int, __QUERIES__ + 1> results {};
- //询问答案
-
- int N {};
- //数组长度
- int queries {};
- //询问次数
-
- std::array<int, __MAX__ + 1> uniques {};
- //用于离散化的辅助数组
- std::array<int, __MAX__ + 1> last{};
- //记录value: sequence[i] 最后一个出现(迭代过程)的下标
- std::array<int, __MAX__ + 1> left{};
- //记录与value: sequence[i] 相等的最近一次下标
-
- std::array<int, __MAX__ << 2 | 1> segments {};
- //线段树
- std::array<int, __QUERIES__ + 1> qtable {};
- //询问表排序
- std::array<int, __MAX__ + 1> stable {};
- //数组表排序
-
- constexpr int left(int index) noexcept { return x << 1; }
- constexpr int right(int index) noexcept { return x << 1 | 1; }
-
- //向上更新线段树,维护数组和
- constexpr update(int index) noexcept {
- segments[index] = std::plus<int>(segments[left(index)], segments[right(index)]);
- }
-
-
- int query(int first, int last) noexcept {
- return query(first, last, 0, N, 0);
- }
- //递归询问区间数组和
- int query(int first, int last, int current_first, int current_last, int index) noexcept {
- if(first <= current_first && last >= current_last) return segments[index];
- int middle { (current_first + current_last)/2 };
- return (
- first < middle ? query(first, last, current_first, middle, left(index)) : 0
- + last >= middle ? query(first, last, middle, current_last, right(index)) : 0 );
- }
-
- void change(int position, int value) noexcept {
- change(position, value, 0, N, 0);
- }
- //单点修改(加上固定常数),并且返回时维护线段树
- void change(int position, int value, int first, int last, int index) noexcept {
- if(first + 1 == last) return (void) (segments[index] += v);
- int middle { (first + last)/2 };
- if(position < middle) change(position, value, first, middle, left(index));
- else change(position, value, middle, last, right(index));
- update(index);
- }
-
- int main(void) {
- //读数组
- std::scanf("%d", &N);
- for(int i {}; i < N; (void) (uniques[i] = sequence[i ++]))
- std::scanf("%d", &sequence[i]);
- //读询问
- std::scanf("%d", &queries);
- for(int i {}; i < queries; ++i)
- std::scanf("%d%d", &x[i], &y[i]);
-
- //离散化
- std::sort(uniques.begin(), uniques.begin() + N);
- auto counter { static_cast<int>(
- std::distance(uniques.begin(),
- std::unique(uniques.begin(), uniques.begin() + N))) };
- for(int i {}; i < N; ++i)
- sequence[i] = static_cast<int>(
- std::distance(uniques.begin(),
- std::lower_bound(uniques.begin(), uniques.begin() + counter, sequence[i])));
-
- //初始化last数组
- std::fill_n(last.begin(), counter, -1);
- //更新left数组
- for(int i {}; i < N; ++i) {
- left[i] = last[sequence[i]];
- last[sequence[i]] = i;
- }
-
- /*
- ** 对询问和数组进行表排序,保证:
- ** 1: 询问区间左端点有序
- ** 2: 迭代过程中,最早出现的元素最先被遍历
- */
- for(int i {}; i < queries; ++i) qtable[i] = i;
- for(int i {}; i < N; ++i) stable[i] = i;
- std::sort(qtable.begin(), qtable.begin() + queries, [&](int i, int j) { return x[table[i]] < x[table[j]]; });
- std::sort(stable.begin(), stable.begin() + N, [&](int i, int j) { return left[stable[i]] < left[stable[j]]; });
-
- //离线处理询问
- int sentinel {};
- //遍历每个询问
- for(int i {}; i < queries; ++i) {
- //根据left数组,把在区间中的仅一次出现的元素,插入线段树
- while(sentinel < N && left[stable[sentinel]] < x[qtable[i]]) {
- change(stable[sentinel], uniques[sequence[stable[sentinel]]]);
- ++ sentinel;
- }
- //更新答案
- results[qtable[i]] = query(x[qtable[i], y[qtable[j]]);
- }
-
- //输出
- for(int i{}; i < queries; ++i) std::printf("%d%c", results[i], " \n"[! (i == queries)]);
- return 0;
- }
-