题目链接:https://ac.nowcoder.com/acm/contest/1084/B
此题为区间不同数之和的板子题,数据量为$5e5$级别,莫队会被卡,这里介绍一种扫描线思想的做法
首先可以把所有询问都存起来,从小到大$for$$[1, n]$的右端点$r$,动态维护出$[l, r]$的答案,同时在右端点增大的过程中维护出$pos[x]$表示$x$上一次出现的位置,考虑右端点从$r - 1$到$r$会对答案产生什么影响,可以发现若$pos[a[r]] = p$,则左端点在$[p + 1, r]$的都会新增$a[r]$的贡献,因为此时在这些区间中$a[r]$这个数是第一次出现,可以发现需要进行的操作是区间加,单点查询,用树状数组维护差分数组即可实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 500010;
int n, m;
int a[N], pos[N];
LL tr[N], ans[N];
vector<array<int, 2>> que[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL query(int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 0; i < m; i ++ )
{
int l, r;
cin >> l >> r;
que[r].push_back({l, i});
}
for (int r = 1; r <= n; r ++ )
{
int p = pos[a[r]];
add(p + 1, a[r]), add(r + 1, -a[r]);
pos[a[r]] = r;
for (auto [l, id] : que[r])
ans[id] = query(l);
}
for (int i = 0; i < m; i ++ )
cout << ans[i] << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T -- ) solve();
return 0;
}