Light oj :- 1188 - Fast Queries( form i j, you have to find the number of distinct integers from index i to j)

Input

8 5

1 1 1 2 3 5 1 2

1 8

2 3

3 6

4 5

4 8

Output:

Case 1:

4

1

4

2

4

BY Segment tree:

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <complex>
#include <numeric>
#include <valarray>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
#define inf (1<<29)
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define nl printf("\n")
#define spc printf(" ")
#define sci(n) scanf("%ld",&n)
#define sc64(n) scanf("%I64d",&n)
#define scii(a,b) scanf("%ld %ld",&a,&b)
#define sc6464(a,b) scanf("%I64d %I64d",&a,&b)
#define scs(s) scanf("%s",s)
#define scss(a,b) scanf("%s %s",a,b)
#define scd(f) scanf("%lf",&f)
#define scdd(a,b) scanf("%lf %lf",&a,&b)
#define pfi(a) printf("%ld",a)
#define pf64(a) printf("%I64d",a)
#define pfii(a,b) printf("%ld %ld",a,b)
#define pf6464(a,b) printf("%I64d %I64d",a,b)
#define pfs(a) printf("%s",a)
#define pfss(a,b) printf("%s %s",a,b)
#define pfd(a) printf("%lf",a)
#define pfdd(a,b) printf("%lf %lf",a,b)
#define rep(i,n) for(int i(0),_n(n);i<_n;++i)
#define repr(i,n) for(int i=n;i>=0;i--)
#define repi(i,a,b) for(int i(a),_b(b);i<=_b;++i)
#define repl(i,n) for(int i(1),_n(n);i<=_n;++i)
#define repir(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mem(x,a) memset(x,a,sizeof(x))
#define repe(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
int dx[]={0,0,1,-1,1,-1,1,-1},dy[]={1,-1,0,0,1,-1,-1,1};
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#define ll long long
typedef vector<vector<int> > vvi;
#define MX 100060
long long tree[3*MX];
long long ar[MX],tr[3*MX],ss=0;
void  update(long l,long r,long i,long j,long node,long valu)
{
    if(i<=l&&j>=r)
    {
       tree[node]=valu;
        return;
    }
    if(i>r||j<l)
    return;

    long mid=(l+r)/2;

    long left=2*node;

    long right=left+1;

    update(l,mid,i,j,left,valu);

    update(mid+1,r,i,j,right,valu);

    tree[node]=tree[left]+tree[right];
}
void csum(long l,long r,long i,long j,long node)
{
    if(i<=l&&j>=r)
    {
        ss+=tree[node];
        return;
    }
    if(i>r||j<l)
    {
      return;
    }
    long mid=(l+r)/2;
    long left=2*node;
    long right=left+1;
    csum(l,mid,i,j,left);
    csum(mid+1,r,i,j,right);
}
int main()
{
    long n,q,a,b,pp;

    scanf("%ld",&pp);

    for(int ii=0;ii<pp;ii++)
    {
        scanf("%ld %ld",&n,&q);

    for(int i=1;i<=n;i++)
    scanf("%ld",&ar[i]);

    long s;

   vector<long>vc[100000],vt[100090];



    long aa[110000]={0},bb[100100]={0};

    for(int i=0;i<q;i++)
    {
        scanf("%ld%ld",&a,&b);

        vc[b].push_back(a);
        vt[b].push_back(i);

    }
    for(int i=1;i<=n;i++)
    {
       if(aa[ar[i]]!=0)
       {
           update(1,n,aa[ar[i]],aa[ar[i]],1,0);
       }

       update(1,n,i,i,1,1);
       //  for(int j=0;j<=15;j++)
       // cout<<tree[j]<<" ";
      // cout<<"\n";
       aa[ar[i]]=i;
       for(int j=0;j<vc[i].size();j++)
       {
           ss=0;
           csum(1,n,vc[i][j],i,1);
           //cout<<ss<<"\n";
           bb[vt[i][j]]=ss;
       }
    }
     printf("Case %ld:\n",ii+1);
    for(int i=0;i<q;i++)
    {
       printf("%ld\n",bb[i]);

    }
    }
return 0;
}


BY Binary indexed tree:


#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>

using namespace std;

#define sf scanf
#define pf printf

typedef map<int, int>mpii;

const int high = 100003;

struct Query
{
    int L , R , i;
}q[50007];

int ar[high] , ans[50007] , block=0 , answer=0 , mp[high];

bool cmp(Query x , Query y)
{
    if(x.L/block != y.L/block) return x.L/block < y.L/block;

    return x.R < y.R;
}

void add(int pos)
{
    mp[ar[pos]]++;

    if(mp[ar[pos]] == 1) answer++;
}

void rmoving(int pos)
{
    mp[ar[pos]]--;

    if(mp[ar[pos]] == 0) answer--;
}

void Results(int n , int m)
{
    block = (int)sqrt(n);

    sort(q , q+m , cmp);

    int i , currR = 0 , currL = 0 , L , R;

    for(i=0; i<m; i++)
    {
        L = q[i].L;
        R = q[i].R;

        while(currL < L)
        {
            rmoving(currL);
            currL++;
        }

        while(currL > L)
        {
            add(currL-1);
            currL--;
        }

        while(currR <= R)
        {
            add(currR);
            currR++;
        }

        while(currR > R+1)
        {
            rmoving(currR-1);
            currR--;
        }

        int indx = q[i].i;

        ans[indx] = answer;
    }
}

void solution(int m)
{
    for(int i=0; i<m; i++)
    {
        pf("%d\n" , ans[i]);
    }
}

int main()
{
    int t , tc=0 , n , i , qry , x , y;
    sf("%d", &t);
    while(t--)
    {
        memset(mp , 0 , sizeof mp);

        answer = 0;

        sf("%d %d", &n , &qry);

        for(i=0; i<n; i++)
        {
            sf("%d", &ar[i]);
        }

        for(i=0; i<qry; i++)
        {
            //sf("%d %d", &q[i].L , &q[i].R);

            scanf("%d", &x);
            scanf("%d", &y);
            x--;
            y--;
            q[i].L = x;
            q[i].R = y;
            q[i].i = i;

            q[i].i = i;
        }

        Results(n , qry);

        pf("Case %d:\n" , ++tc);

        solution(qry);
    }

    return 0;
}