Pagini recente » Cod sursa (job #1595848) | Cod sursa (job #3148995) | Cod sursa (job #1885691) | Cod sursa (job #2732990) | Cod sursa (job #2715925)
#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
long long prv[100005];
struct Query
{
long long l, r, orig;
bool operator < (const Query &other) const
{
if(r == other.r)
return l < other.l;
return r < other.r;
}
}queries[100005];
long long N, M, K;
struct AIB
{
long long v[100005];
void update(long long poz, long long val)
{
for(long long i = poz; i <= N; i += i & (-i))
v[i] += val;
}
long long query(long long poz)
{
long long s = 0;
for(long long i = poz; i >= 1; i -= i & (-i))
s += v[i];
return s;
}
}aib;
long long v[100005], ans[100005];
int main()
{
fin >> N >> K >> M;
for(long long i = 1; i <= N; i++)
{
fin >> v[i];
aib.update(i, v[i]);
}
for(long long i = 1; i <= M; i++)
{
fin >> queries[i].l >> queries[i].r;
queries[i].orig = i;
}
sort(queries + 1, queries + M + 1);
long long poz = 1;
for(long long i = 1; i <= M; i++)
{
while(poz <= queries[i].r)
{
if(prv[v[poz]] != 0)
aib.update(prv[v[poz]], -v[poz]);
prv[v[poz]] = poz;
poz++;
}
ans[queries[i].orig] = aib.query(queries[i].r) - aib.query(queries[i].l - 1);
}
for(long long i = 1; i <= M; i++)
fout << ans[i] % MOD << '\n';
return 0;
}