#include<bits/stdc++.h>
#include <iomanip>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);
#define ll int //long long
#define for_t ll T;cin>>T;while(T--)
#define endl "\n"
#define F(a,b) for(ll i=a;i<b;i++)
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define pb push_back
#define lc(curr) (curr * 2)
#define rc(curr) ((curr * 2) + 1)
const int maxn = 500005;
ll a[maxn];
ll tree[maxn * 4];
ll arr[maxn];
ll rightv[maxn];
vector<pair<ll,pair<ll,ll>>> queries;
map<ll,ll> cnt;
map<ll,ll> occ;
//index of next occurrence of this element;
//generate array for all elements
//one by one remove elements from 0 to n
//once element is removed
//update tht index -> 0
//index of next occurrence of that element -> 0
//index of 2nd next occurrence of that element -> 1
//index of 3rd next occurrence of that element -> -1
//all other occurrences should be 0?
void build(ll curr,ll l,ll r)
{
if(l == r)
{
tree[curr] = arr[l];
return;
}
build(lc(curr),l,(l + r)/2);
build(rc(curr),((l + r)/2) + 1,r);
tree[curr] = tree[lc(curr)] + tree[rc(curr)];
}
void update(ll curr,ll l,ll r,ll i,ll num)
{
if(l > i || r < i)
{
return;
}
if(l == i && r == i)
{
tree[curr] = num;
return;
}
ll mid = (l + r)/2;
if(i <= mid)
{
update(lc(curr),l,mid,i,num);
}
else
{
update(rc(curr),mid + 1,r,i,num);
}
tree[curr] = tree[lc(curr)] + tree[rc(curr)];
}
ll query(ll curr,ll l,ll r,ll i,ll j)
{
if(l > j || r < i)
{
return 0;
}
if(l >= i && r <= j)
{
return tree[curr];
}
ll mid = (l + r)/2;
return query(lc(curr),l,mid,i,j) + query(rc(curr),mid + 1,r,i,j);
}
void sol()
{
ll n,q;
cin >> n >> q;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
queries.resize(q);
for(int i = 0;i < q;i++)
{
cin >> queries[i].first >> queries[i].second.first;
queries[i].second.second = i;
}
vector<ll> ans(q);
memset(rightv,0,sizeof(rightv));
memset(tree,0,sizeof(tree));
memset(arr,0,sizeof(arr));
sort(all(queries));
for(int i = n;i >= 1;i--)
{
rightv[i] = occ[a[i]];
occ[a[i]] = i;
}
for(int i = 1;i <= n;i++)
{
cnt[a[i]]++;
if(cnt[a[i]] > 1)
{
continue;
}
arr[i] = 0;
arr[rightv[i]] = 1;
arr[rightv[rightv[i]]] = -1;
}
build(1,1,n);
ll prev = 1;
for(int i = 0;i < queries.size();i++)
{
ll l = queries[i].first;
ll r = queries[i].second.first;
ll temp;
while(prev < l)
{
temp = prev;
if(temp != 0)
{
arr[temp] = 0;
update(1,1,n,temp,0);
}
temp = rightv[prev];
if(temp != 0)
{
arr[temp] = 0;
update(1,1,n,temp,0);
}
temp = rightv[rightv[prev]];
if(temp != 0)
{
arr[temp] = 1;
update(1,1,n,temp,1);
}
temp = rightv[rightv[rightv[prev]]];
if(temp != 0)
{
arr[temp] = -1;
update(1,1,n,temp,-1);
}
prev++;
}
arr[l] = 0;
update(1,1,n,l,0);
temp = rightv[l];
if(temp != 0)
{
arr[temp] = 1;
update(1,1,n,temp,1);
}
temp = rightv[rightv[l]];
if(temp != 0)
{
arr[temp] = -1;
update(1,1,n,temp,-1);
}
ans[queries[i].second.second] = query(1,1,n,l,r);
prev = l;
}
for(auto it:ans)
{
cout << it << endl;
}
}
int main()
{
//freopen("mootube.in", "r", stdin);
//freopen("mootube.out", "w", stdout);
FIO
sol();
}
Compilation message
poklon.cpp: In function 'void sol()':
poklon.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i = 0;i < queries.size();i++)
| ~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
12 ms |
12244 KB |
Output is correct |
| 5 |
Correct |
146 ms |
15704 KB |
Output is correct |
| 6 |
Correct |
158 ms |
15564 KB |
Output is correct |
| 7 |
Correct |
343 ms |
19604 KB |
Output is correct |
| 8 |
Correct |
565 ms |
23568 KB |
Output is correct |
| 9 |
Correct |
723 ms |
27440 KB |
Output is correct |
| 10 |
Correct |
894 ms |
31352 KB |
Output is correct |
