Light OJ 1188/Spoj D-query - Segment Tree

/***
 created: 2022-07-08-00.09.35
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'


ll a[200005];
ll tree1[800005];

//void treeconstruct(ll node,ll b,ll e)
//{
//
//    if(b==e)
//    {
//        tree1[node]=a[b];
//        return;
//    }
//
//    ll left = node*2;
//    ll right = node*2 + 1ll;
//
//    ll mid=(b+e)/2;
//
//    treeconstruct(left,b,mid);
//    treeconstruct(right,mid+1,e);
//
//    tree1[node]=tree1[left]+tree1[right];
//
//}

void update(ll node,ll b,ll e,ll i,ll newv)
{
    if(i>e || i<b) return;

    if(b==e)
    {
        tree1[node]=newv;
        return;
    }

    ll left = node*2;
    ll right = node*2 + 1ll;

    ll mid=(b+e)/2;

    update(left,b,mid,i,newv);

    update(right,mid+1,e,i,newv);

    tree1[node]=tree1[left]+tree1[right];

}

ll queries(ll node,ll b,ll e,ll i,ll j)
{
    if(i>e || j<b) return 0;

    if(b>=i && e<=j) return tree1[node];

    ll left = node*2;
    ll right = node*2 + 1ll;

    ll mid=(b+e)/2;

    ll x=queries(left,b,mid,i,j);

    ll y=queries(right,mid+1,e,i,j);

    return x+y;

}

ll ans[200005];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll n,m,i,j,k,l,q;

        cin>>n>>q;

        for(i=1; i<=n; i++)
        {
            cin>>a[i];
        }



        vector<array<ll,3>>qr;

        for(i=0; i<q; i++)
        {
            cin>>j>>k;

            qr.push_back({k,j,i});
        }

        sort(qr.begin(),qr.end());

        map<ll,ll>x;

        j=0;

        for(i=1; i<=n; i++)
        {
            if(x[a[i]]>0)
            {
                update(1,1,n,x[a[i]],0ll);
            }

            update(1,1,n,i,1ll);

            x[a[i]]=i;

            for(; j<q; j++)
            {
                if(qr[j][0]==i)
                {
                    ans[qr[j][2]]=queries(1,1,n,qr[j][1],qr[j][0]);
                }
                else break;
            }
        }

        cout<<"Case "<<cs<<":"<<nl;

        for(i=0; i<q; i++)
        {
            cout<<ans[i]<<nl;
        }
    }


    get_lost_idiot;
}