D-QUERY SPOJ – Fenwick Tree

Home   »   D-QUERY SPOJ – Fenwick Tree

#include
using namespace std;
#define int long long
int fenwick[1000005];
int arr[30005];
int N;
void update(int index,int x)
{
   for(int i=index;i<=N;i+=(i&-i))
   {
      fenwick[i]+=x;
   }
}
int sum(int index)
{
   int ans = 0;
   for(int i=index;i>0;i-=(i&-i))
   {
      ans+=fenwick[i];
   }
   return ans;
}
signed main()
{   
   #ifndef ONLINE_JUDGE
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
   #endif   
   ios_base::sync_with_stdio(0);cin.tie(0);cin.tie(0);

   cin >> N;

   int arr[N+1];
   for(int i=1;i<=N;i++)cin >> arr[i];

   vector>> q;
   
   int m;cin >> m;

   int queryid = 0;
   while(m--)
   {
      int l,r;cin >> l >> r;
      q.push_back({r,{l,queryid}});
      queryid++;
   }
   sort(q.begin(),q.end());

   int marked[1000005];
   memset(marked,0,sizeof marked);


   int qcounter = 0;
   int ans[q.size()];

   for(int i=1;i<=N;i++)
   {
      int element = arr[i];

      if(marked[element]!=0)
         update(marked[element],-1);

      marked[element] = i;
      update(i,1);

      while(qcounter < q.size() && q[qcounter].first == i)
      {

         ans[q[qcounter].second.second] = (sum(i) - sum(q[qcounter].second.first-1));
         qcounter++;
      }
   }

   for(int i=0;i

Leave a Reply

Your email address will not be published. Required fields are marked *