26.CF1000F One Occurrence

26.CF1000F One Occurrence

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列，要求支持查询区间内只出现一次的数字

可以离线，那么离线所有询问后按右端点排序，然后加入贡献回答即可。

洛谷传送门：CF1000F One Occurrence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：F. One Occurrence (codeforces.com)

题目思路

给定序列，要求支持查询区间内只出现一次的数字。

这属于一类特别典型的问题：开桶维护最后一次出现位置，在更新时去重复贡献。

对于本题，我们首先对所有询问进行离线，然后按照右端点排序加入贡献计算答案：

• 记录每个数字上次最后一次出现的位置
• 只要对于上一次出现的位置维护一个区间最小值和最小值的数值，然后查询区间最小值是否位于区间内即可
• 在每次加入右端点时判断是否之前出现过，如果出现过就清除上次加入的贡献(当当前点为右端点时，上次出现的位置一定只能作为左端点出现，因此需要消除其作为右端点时记录的前序信息)

当然，这题如果强制在线的话，可以用可持久化权值线段树保留历史版本进行查询。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 4e6 + 10;

namespace SegTree{
    #define ls rt > 1;
        if(mid >= pos) update(lson, pos, val, pre);
        else update(rson, pos, val, pre);
        push_up(rt);
    }


    Info query(int rt, int l, int r, int L, int R){
        if(l >= L && r > 1; Info ans = Info{0, INT_MAX};
        if(mid >= L) ans = ans + query(lson, L, R);
        if(mid  a[i];
    SegTree::build(1, 1, n);
    int m = 0; cin >> m;
    for(int i = 1; i > l >> r;
        q[r].emplace_back(query{l, i});
    }

    for(int i = 1; i