Pagini recente » Cod sursa (job #624360) | Cod sursa (job #463797) | Cod sursa (job #1594823) | Cod sursa (job #1391090) | Cod sursa (job #2271863)
#include <bits/stdc++.h>
using namespace std;
struct tst{
int r, i;
};
const int M = 666013;
int n, m, test, aib[100005], v[100005], b[100005], last[100005], ans[100005], r[100005];
vector<tst> q[100005];
void update(int idx, int val)
{
while(idx <= n){
aib[idx] = (aib[idx] + val)%M;
idx += (idx & (-idx));
}
}
int read(int idx)
{
int sum = 0;
while(idx){
sum = (sum + aib[idx])%M;
idx -= (idx & (-idx));
}
return sum;
}
int main()
{
ifstream fin ("distincte.in");
ofstream fout ("distincte.out");
fin >> n >> m >> test;
for (int i = 1; i <= n; ++i){
fin >> v[i];
b[i] = last[v[i]];
r[b[i]] = i;
if(b[i] == 0)
update(i, v[i]);
last[v[i]] = i;
}
for (int t = 1; t <= test; ++t){
int l, r;
fin >> l >> r;
q[l].push_back({r, t});
}
for (int t = 1; t <= n; ++t){
if(t != 1 && r[t-1] != 0)
update(r[t-1], v[r[t-1]]);
for (auto Q : q[t])
ans[Q.i] = (read(Q.r)-read(t-1)+M)%M;
}
for (int i = 1; i <= test; ++i)
fout << ans[i] << "\n";
return 0;
}