时光如梭，Codeforces 的题号还是三位数的时代已经过去；量子语言原来已经来临。
传送门
题目大意
给定一个长度为
n
n
的序列 a，有
m
m
个询问，每次询问给定一个区间 [l,r]，如果这个区间里存在恰好只出现一次的数，输出这个数（如果有多个就任意输出一个），否则输出
0
0
。
n,m≤5×105，
ai≤105
a
i
≤
10
5
。
思路
还好题解是英文的看不懂啊哈哈哈。
首先题解中有三个类型：主席树，线段树，基于莫队的算法（Mo-based algorithm，出题人不是中国的，真神仙），然后我瞄了第一句话：如果所有询问右端点一样……然后我就自己想了……
不妨求出每个位置下一个与它相同的数所在的位置，
O(n)
O
(
n
)
扫描即可，我们用一个从前往后的箭头表示这个东西。发现，如果区间内存在恰好只出现一次的数，那么这个数必须满足两个条件：指向它的箭头不存在或者起点在左端点外；它指向其它位置的箭头在右端点外（如果没有，不妨令这个箭头指向
n+1
n
+
1
）。
假设一个区间内所有位置都不存在指向它的箭头，怎么判断这个区间是否有解呢？直接取这个区间内指向别的地方的位置的最大值，拿它和右端点比较即可，这个可以用线段树维护。现在有些位置有箭头指向它，换句话说，有些位置在求最大值时不能算进对答案的贡献中。
考虑把询问按左端点离线，从左到右处理。对于有箭头指向它的位置，我们让它的箭头指向的位置减去一个极大值，然后在区间中取最大值即可。当处理完一个左端点后，如果左端点指向了某个位置，我们就把那个位置指向的位置加上之前减去的那个极大值，这样就能正确统计答案了。用线段树维护，时间复杂度
O(nlogn)
O
(
n
log
n
)
。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
putchar('\n');
}
const int INF = (~(int(1) << (sizeof(int) * 8 - 1))) >> 1;
const int maxn = int(5e5) + 5;
int n, m;
int a[maxn];
struct Query
{
int l, r;
void read()
{
l = readIn();
r = readIn();
}
} querys[maxn];
std::vector<int> offline[maxn];
int appear[maxn];
int next[maxn];
bool pointer[maxn];
class SegTree
{
static inline int code(int l, int r)
{
return (l + r) | (l != r);
}
struct Node
{
int maxVal;
int maxIdx;
Node() : maxVal(-INF - 1) {}
bool operator<(const Node& b) const
{
return maxVal < b.maxVal;
}
} nodes[maxn * 2];
int g_Pos, g_Val, g_L, g_R;
void update(int l, int r)
{
Node& t = nodes[code(l, r)];
int mid = (l + r) >> 1;
Node& lc = nodes[code(l, mid)];
Node& rc = nodes[code(mid + 1, r)];
if (lc.maxVal >= rc.maxVal)
t = lc;
else
t = rc;
}
void add_(int l, int r)
{
if (l == r)
{
nodes[code(l, r)].maxVal += g_Val;
return;
}
int mid = (l + r) >> 1;
if (g_Pos <= mid) add_(l, mid);
else add_(mid + 1, r);
update(l, r);
}
Node query_(int l, int r)
{
if (g_L <= l && r <= g_R)
{
return nodes[code(l, r)];
}
int mid = (l + r) >> 1;
Node ret;
if (g_L <= mid)
ret = std::max(ret, query_(l, mid));
if (g_R > mid)
ret = std::max(ret, query_(mid + 1, r));
return ret;
}
public:
void build(int l, int r)
{
if (l == r)
{
Node& t = nodes[code(l, r)];
t.maxVal = -INF + next[l];
t.maxIdx = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid);
build(mid + 1, r);
update(l, r);
}
void add(int pos, int val)
{
g_Pos = pos;
g_Val = val;
add_(1, n);
}
int query(int l, int r)
{
g_L = l;
g_R = r;
Node t = query_(1, n);
if (t.maxVal > r)
return t.maxIdx;
else
return 0;
}
} st;
int ans[maxn];
void run()
{
n = readIn();
for (int i = 1; i <= n; i++)
a[i] = readIn();
m = readIn();
for (int i = 1; i <= m; i++)
querys[i].read();
for (int i = 1; i <= m; i++)
offline[querys[i].l].push_back(i);
for (int i = n; i; i--)
{
next[i] = appear[a[i]];
if (!next[i]) next[i] = n + 1;
appear[a[i]] = i;
}
for (int i = 1; i <= n; i++)
if (next[i])
pointer[next[i]] = true;
st.build(1, n);
for (int i = 1; i <= n; i++)
if (!pointer[i])
st.add(i, INF);
for (int l = 1; l <= n; l++)
{
for (int i = 0; i < offline[l].size(); i++)
{
int idx = offline[l][i];
int r = querys[idx].r;
ans[idx] = st.query(l, r);
}
if (next[l] <= n)
st.add(next[l], INF);
}
for (int i = 1; i <= m; i++)
printOut(ans[i]);
}
int main()
{
run();
return 0;
}
总结
要是一眼题解都不看就会做就好了。唉，谁叫我太弱了呢 QAQ。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
