Cod sursa(job #865630)
#include<algorithm>
#include<fstream>
#define zeros(x) ( (x ^ (x - 1)) & x )
// solutie cu AIB
#define dim 100007
#define mod 666013
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
int AIB[dim],next[dim],ant[dim],a,b,t[dim],cnt;
int i,j,n,m,k;
struct cub {
int a,b,idx,sol;
}
S[dim];
int cmp1(cub a,cub b) {
return a.a<b.a;
}
int cmp2(cub a,cub b){
return a.idx<b.idx;
}
int add(int x,int val){
for(int i=x;i<=n;i+=zeros(i)){
AIB[i]+=val;
if(AIB[i]<mod)
AIB[i]+=mod;
if(AIB[i]>=mod)
AIB[i]-=mod;
}
}
int comp (int x) {
int sum=0;
for(int i=x;i;i-=zeros(i)){
sum+=AIB[i];
}
return sum%mod;
}
int main () {
f>>n>>k>>m;
for(i=1;i<=n;++i){
f>>a;
t[i]=a;
next[ant[a]]=i;
if(ant[a]==0){
add(i,a);
}
ant[a]=i;
}
for(i=1;i<=m;++i ){
f>>a>>b;
S[i].a=a;
S[i].b=b;
S[i].idx=i;
}
sort(S+1,S+1+m,cmp1);
cnt=1;
for(i=1;i<=n;++i) {
while(S[cnt].a==i && cnt<=m){
S[cnt].sol=comp(S[cnt].b);
++cnt;
}
add(i,-t[i]);
if(next[i]){
add(next[i],t[i]);
}
}
sort(S+1,S+1+m,cmp2);
for(i=1;i<=m;++i){
g<<S[i].sol<<"\n";
}
return 0;
}