LOJ: 1293 - Document Analyzer (Persistance SegmentTree)

LOJ: 1293 - Document Analyzer
///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
#define UNIK(v) sort(all(v)),v.resize( unique(all(v)) -v.begin() );
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     50005
#define inf    1000000010
#define MD     1000000000LL
#define eps    1e-9
///===============================///

struct data {
    int l,r,sm;
    data() {};
};
data nd[(36*MX)+2];// 2 times insertion so 36,else 18
int nw,root[MX+2];
int Ins(int pn,int l,int r,int p,int v) {
    int id=++nw;
    nd[ id ]=nd[ pn ];
    if( l==r ) {
        nd[ id ].sm=v;
        return id;
    }
    int md=(l+r)>>1;
    if( p<=md ) nd[id].l=Ins(nd[id].l,l,md,p,v);
    else nd[id].r=Ins( nd[id].r,md+1,r,p,v );
    nd[ id ].sm=( nd[ nd[id].l ].sm+nd[ nd[id].r ].sm );
    return id;
}

int Qry(int nn,int l,int r,int q1,int q2) {
    if( r<q1 || l>q2 ) return 0;
    if( q1<=l && r<=q2 ) return nd[nn].sm;
    int md=(l+r)>>1;
    int x=Qry( nd[nn].l,l,md,q1,min(md,q2) );
    int y=Qry( nd[nn].r,md+1,r,max(q1,md+1),q2 );
    return (x+y);
}

map<string,int>MP;
int ar[MX+2],Lst[MX+2];
int main() {
    int tc,cs=1,i,j,k,n;
    S(tc);
    while(tc--) {
        string s,str;
        str="";
        while( getline(cin,s) ) {
            if(s=="END")break;
            str+=" ";
            str+=s;
        }
        int ln=SZ(str);
        for(i=0; i<ln; i++) {
            if(!isalpha( str[i] ) )str[i]=' ';
        }
        MP.clear();
        stringstream ss(str);
        n=0;///total elements
        k=0;///distinct elements
        while(ss>>s) {
            if( !MP[s] ) MP[s]=++k;
            ar[++n]=MP[s];
            Lst[n]=0;
        }
        ///now finding distinct values in range with BS;
        nw=0;
        root[0]=++nw;
        for(i=1; i<=n; i++) {
            int x=ar[i];
            if( Lst[x] ) {
                ///Erase last and insert new;
                root[i]=Ins(root[i-1],1,n,Lst[x],0);
                root[i]=Ins(root[i],1,n,i,+1);
            } else {
                root[i]=Ins(root[i-1],1,n,i,+1);
            }
            Lst[x]=i;
        }
        int mn=n+1,pp,qq;
        for(int q=1; q<=n; q++) {
            if( Qry(root[q],1,n,1,q)<k ) continue;
            int lo=1,hi=q,ret=1;
            while(lo<=hi) {
                int md=(lo+hi)>>1;
                int xx=Qry(root[q],1,n,md,q);
                if( xx>=k ) {
                    ret=max(ret,md);
                    lo=md+1;
                } else hi=md-1;
            }
            if( mn>(q-ret+1) ) {
                mn=(q-ret+1);///len;
                pp=ret;
                qq=q;
            }
        }
        printf("Case %d: %d %d\n",cs++,pp,qq);
    }
    return 0;
}