SPOJ: MKTHNUM – K-th Number

0

Problem Link: https://www.spoj.com/problems/MKTHNUM/

Solution Idea: (Merge Sort Tree)

  • At first take input and store the input in a pair array where first element of ith pair is the value ai and second element of ith pair is i.
  • Sort the pair array with with ascending order of ai
  • Build a merge sort tree using the second element of each pair of sorted pair array.
  • Now for each query i,j,k at first check how many number in range i to j inclusive are present in left subtree of current node in merge sort tree. Let the value is x. So if x<=k then it's sure that the answer is in the left subtree. So we will go to left subtree of current node with k. Otherwise we will go to right subtree of current node with k-x;
  • In this manner when we reach to a leaf node we can say that this node contains the index of our answer.


Advertisements

SPOJ: GSS2 – Can you answer these queries II

Problem Link : http://www.spoj.com/problems/GSS2/


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2


int ara[mx+5];
int last[2*mx+5];
ll ans[mx+5];

struct data
{
    int l,r,id;
};

vector<data>queries;

struct data1
{
    ll sum,lazy,best_lazy,ans;
    data1()
    {
        sum=lazy=best_lazy=ans=0;
    }
};

data1 tree[3*mx];

void push_down(data1 &cur, data1 &lft, data1 &rgt)
{
//    if(cur.lazy || cur.best_lazy)
//    {
        lft.best_lazy=max(lft.best_lazy,lft.lazy+cur.best_lazy);
        lft.lazy+=cur.lazy;
        lft.ans=max(lft.ans,lft.sum+cur.best_lazy);
        lft.sum=lft.sum+cur.lazy;
        rgt.best_lazy=max(rgt.best_lazy,rgt.lazy+cur.best_lazy);
        rgt.lazy+=cur.lazy;
        rgt.ans=max(rgt.ans,rgt.sum+cur.best_lazy);
        rgt.sum+=cur.lazy;
        cur.lazy=cur.best_lazy=0;
//    }
}

void push_up(data1 &cur, data1 &lft, data1 &rgt)
{
    cur.ans=max(lft.ans,rgt.ans);
    cur.sum=max(lft.sum,rgt.sum);
}


void update(int n, int b, int e, int i, int j, ll val)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        tree[n].best_lazy=max(tree[n].best_lazy,tree[n].lazy+val);
        tree[n].lazy+=val;
        tree[n].ans=max(tree[n].ans,tree[n].sum+val);
        tree[n].sum+=val;
        return;
    }
    segment_tree;
    push_down(tree[n],tree[l],tree[r]);
    update(l,b,mid,i,j,val);
    update(r,mid+1,e,i,j,val);
    push_up(tree[n],tree[l],tree[r]);
}

data1 query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return data1();
    if(b>=i && e<=j)
    {
        return tree[n];
    }
    segment_tree;
    push_down(tree[n],tree[l],tree[r]);
    data1 p=query(l,b,mid,i,j);
    data1 q=query(r,mid+1,e,i,j);
    data1 ret;
    push_up(ret,p,q);
    return ret;
}


int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    int n;
    sf(n);
    for(int i=1; i<=n; i++) sf(ara[i]);
    int m;
    sf(m);
    data a;
    for(int i=0; i<m; i++)
    {
        sff(a.l,a.r);
        a.id=i;
        queries.pb(a);
    }

    sort(all(queries),[](data a,data b)
    {
        return a.r<b.r;
    });

    int idx=0;
    for(int i=1; i<=n && idx<SZ(queries); i++)
    {
//        if(last[mx+ara[i]]!=0)
//        {
//            update(1,1,n,last[mx+ara[i]],0);
//        }
        int xx=last[mx+ara[i]]+1;
        update(1,1,n,xx,i,ara[i]);
        last[mx+ara[i]]=i;
        while(idx<SZ(queries) && queries[idx].r==i)
        {
            ans[queries[idx].id]=query(1,1,n,queries[idx].l,queries[idx].r).ans;
            idx++;
        }
    }

    for(int i=0; i<m; i++)
        printf("%lld\n",ans[i]);



    return 0;
}


SPOJ: CERC07S – Robotic Sort

Problem Link : http://www.spoj.com/problems/CERC07S/

Solution Idea:



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


/*-------------------------Treap Start------------------------*/
struct node
{
    int prior,size;
    pii val;//value stored in the array
    pii mini;//whatever info you want to maintain in segtree for each node
    int lazy;//whatever lazy update you want to do
    int id;
    struct node *l,*r;
};

typedef node* pnode;

int sz(pnode t)
{
    return t?t->size:0;
}

void upd_sz(pnode t)
{
    if(t)t->size=sz(t->l)+1+sz(t->r);
}

void lazy(pnode t)
{
    if(!t || !t->lazy)return;
//    t->val+=t->lazy;//operation of lazy
//    t->mini+=t->lazy*sz(t);
    swap(t->l,t->r);
    if(t->l)t->l->lazy^=t->lazy;//propagate lazy
    if(t->r)t->r->lazy^=t->lazy;
    t->lazy=0;
}

void reset(pnode t)
{
    if(t)t->mini = t->val;//no need to reset lazy coz when we call this lazy would itself be propagated
}

void combine(pnode& t,pnode l,pnode r) //combining two ranges of segtree
{
    if(!l || !r)return void(t = l?l:r);
    t->mini = min(l->mini, r->mini);
}

void operation(pnode t) //operation of segtree
{
    if(!t)return;
    reset(t);//reset the value of current node assuming it now represents a single element of the array
    lazy(t->l);
    lazy(t->r);//imp:propagate lazy before combining t->l,t->r;
    combine(t,t->l,t);
    combine(t,t,t->r);
}

void split(pnode t,pnode &l,pnode &r,int pos,int add=0)
{
    if(!t)return void(l=r=NULL);
    lazy(t);
    int curr_pos = add + sz(t->l);
    if(curr_pos<=pos)//element at pos goes to left subtree(l)
        split(t->r,t->r,r,pos,curr_pos+1),l=t;
    else
        split(t->l,l,t->l,pos,add),r=t;
    upd_sz(t);
    operation(t);
}

int find_min(pnode t, int add=0)
{
    lazy(t);
    int cur_pos=sz(t->l)+add;
    if(t->r && t->r->mini==t->mini) return find_min(t->r,cur_pos+1);
    if(t->l && t->l->mini==t->mini) return find_min(t->l,add);
    return cur_pos;
}

void merge(pnode &t,pnode l,pnode r)  //l->leftarray,r->rightarray,t->resulting array
{
    lazy(l);
    lazy(r);
    if(!l || !r) t = l?l:r;
    else if(l->prior>r->prior)merge(l->r,l->r,r),t=l;
    else    merge(r->l,l,r->l),t=r;
    upd_sz(t);
    operation(t);
}

pnode init(int val, int id)
{
    pnode ret = (pnode)malloc(sizeof(node));
    ret->prior=rand();
    ret->size=1;
    ret->val=pii(val,id);
    ret->mini=pii(val,id);
    ret->lazy=0;
    ret->l=ret->r=NULL;
    return ret;
}

//int range_query(pnode t,int l,int r) //[l,r]
//{
//    pnode L,mid,R;
//    split(t,L,mid,l-1);
//    split(mid,t,R,r-l);//note: r-l!!
//    int ans = t->mini;
//    merge(mid,L,t);
//    merge(t,mid,R);
//    return ans;
//}

//void range_update(pnode t,int l,int r,int val) //[l,r]
//{
//    pnode L,mid,R;
//    split(t,L,mid,l-1);
//    split(mid,t,R,r-l);//note: r-l!!
//    t->lazy+=val; //lazy_update
//    merge(mid,L,t);
//    merge(t,mid,R);
//}

//void split(pnode t,pnode &l,pnode &r,int key)
//{
//    if(!t) l=r=NULL;
//    else if(t->val<=key) split(t->r,t->r,r,key),l=t; //elem=key comes in l
//    else split(t->l,l,t->l,key),r=t;
//    upd_sz(t);
//}
//
//void insert(pnode &t,pnode it)
//{
//    if(!t) t=it;
//    else if(it->prior>t->prior) split(t,it->l,it->r,it->val),t=it;
//    else insert(t->val<=it->val?t->r:t->l,it);
//    upd_sz(t);
//}
//
//void erase(pnode &t,int key)
//{
//    if(!t)return;
//    else if(t->val==key)
//    {
//        pnode temp=t;
//        merge(t,t->l,t->r);
//        free(temp);
//    }
//    else erase(t->val<key?t->r:t->l,key);
//    upd_sz(t);
//}

void output(pnode t)
{
    if(!t) return;
    output(t->l);
    printf("%d ",t->val);
    output(t->r);
}

void clear_tree(pnode t)
{
    if(!t) return;
    clear_tree(t->l);
    clear_tree(t->r);
    free(t);
}

/*-------------------------Treap End--------------------------*/


int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n;
    while(sf(n) && n)
    {
        pnode root=NULL;
        for(int i=0; i<n; i++)
        {
            int a;
            sf(a);
            merge(root,root,init(a,i+1));
        }
        vector<int>ans;
        while(n)
        {
            int k=find_min(root);
            pnode l,r;
            split(root,l,r,k-1);
            split(r,root,r,0);
            if(l)
                l->lazy=1;
            merge(root,l,r);
            n--;
            ans.pb(SZ(ans)+k+1);
        }

        for(int i=0; i<SZ(ans); i++)
        {
            printf("%d",ans[i]);
            if(i!=SZ(ans)-1)
                printf(" ");
        }
        printf("\n");
//        clear_tree(root);

    }

    return 0;
}

SPOJ: SEGSQRSS – Sum of Squares with Segment Tree

Problem Link : http://www.spoj.com/problems/SEGSQRSS/

Solution Idea:

    This problem is a nice example of segment tree with lazy propagation. All you need to solve this kind of problem is to do some experiment with the formula and convert them into a suitable form. From which we can drive the segment tree solution.

    In this problem given an integer array A=[a1,a2,a3,a4…]. You need to perform 3 kinds of operation on it.

    type 0: Set all the element in the interval l to r to x.
    type 1: Increase all the element in the interval l to r by x.
    type 2: Print the value of square sum of the interval l to r. For example let l=1 and r=3. then you need to print a1^2 + a2^2 + a3^2.

    At first think we have a pre-calculated square sum array. Then if we perform type 1 operation which is increase it by x then what scenario will happen?

    Our sum now become (a1+x)^2 + (a2+x)^2 + (a3+x)^2. Let expand this equation-

    (a1+x)^2 + (a2+x)^2 + (a3+x)^2
    = a1^2+ 2*a1*x + x^2 + a2^2+ 2*a2*x + x^2 + a3^2+ 2*a3*x + x^2
    = (a1^2 + a2^2 + a3^2) + 3*x^2 + 2*x*(a1 + a2 + a3)

    for a range l to r the generalized equation is –

    (a_l^2 + a_l+1^2 +….+ a_r^2) + (r-l+1)*x^2 + 2*x*(a_l + a_l+1 +….+ a_r)

    We can store the information about sum, square_sum, type_0 lazy and type_1 lazy of an interval in each segment tree node. And perform type 1 operation then we can calculate then sum value for a node over a range by multiplication and square sum value by above equation.

    For every type 0 operation we can simply put the value of sum and square sum by using some basic calculation and arithmetic multiplication operation.

    And for every type 2 operation we just need to get the sum of square sum value over a range l to r.

    So we can perform each of 3 operation using a segment tree with lazy propagation.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
    ll sum,sqrsum,lazy,upd;
};

data tree[3*mx];

ll ara[mx];

void push_down(int n, int b, int e)
{
    segment_tree;
    if(tree[n].upd)
    {
        tree[l].lazy=0;
        tree[r].lazy=0;
        tree[l].sum=(mid-b+1)*tree[n].upd;
        tree[l].sqrsum=(mid-b+1)*sqr(tree[n].upd);
        tree[r].sum=(e-mid)*tree[n].upd;
        tree[r].sqrsum=(e-mid)*sqr(tree[n].upd);
        tree[l].upd=tree[n].upd;
        tree[r].upd=tree[n].upd;
        tree[n].upd=0;
    }
    if(tree[n].lazy)
    {
//        tree[l].lazy+=tree[n].lazy;
//        tree[l].status=1;
//        tree[r].lazy+=tree[n].lazy;
//        tree[r].status=1;
//        tree[n].status=0;
        tree[l].sqrsum+=(tree[l].sum*(2*tree[n].lazy))+(mid-b+1)*sqr(tree[n].lazy);
        tree[r].sqrsum+=(tree[r].sum*(2*tree[n].lazy))+(e-mid)*sqr(tree[n].lazy);
        tree[l].sum+=(mid-b+1)*tree[n].lazy;
        tree[r].sum+=(e-mid)*tree[n].lazy;
        tree[l].lazy+=tree[n].lazy;
        tree[r].lazy+=tree[n].lazy;
        tree[n].lazy=0;
    }
}

void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].sum=ara[b];
        tree[n].sqrsum=sqr(ara[b]);
        tree[n].lazy=0;
        tree[n].upd=0;
        return;
    }
    segment_tree;
    init(l,b,mid);
    init(r,mid+1,e);
    tree[n].sum=tree[l].sum+tree[r].sum;
    tree[n].sqrsum=tree[l].sqrsum+tree[r].sqrsum;
    tree[n].lazy=0;
    tree[n].upd=0;
}

void update(int n, int b, int e, int i, int j, ll val, int type)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        if(type==0)
        {
            tree[n].sum=(e-b+1)*val;
            tree[n].sqrsum=(e-b+1)*sqr(val);
            tree[n].lazy=0;
            tree[n].upd=val;
        }
        else
        {
            tree[n].sqrsum+=(tree[n].sum*2*val)+((e-b+1)*sqr(val));
            tree[n].sum+=(e-b+1)*val;
            tree[n].lazy+=val;
        }
        return;
    }

    push_down(n,b,e);

    segment_tree;

    update(l,b,mid,i,j,val,type);
    update(r,mid+1,e,i,j,val,type);
    tree[n].sum=tree[l].sum+tree[r].sum;
    tree[n].sqrsum=tree[l].sqrsum+tree[r].sqrsum;
}

ll query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return 0;
    if(b>=i && e<=j)
        return tree[n].sqrsum;
    push_down(n,b,e);
    segment_tree;
    ll p=query(l,b,mid,i,j);
    ll q=query(r,mid+1,e,i,j);
    return p+q;
}

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,q;
        sff(n,q);
        loop1(i,n) sfl(ara[i]);
        init(1,1,n);
        LINE_PRINT_CASE;
        while(q--)
        {
            int a,b,c,d;
            sfff(a,b,c);
            if(a==2)
            {
                ll ans=query(1,1,n,b,c);
                printf("%lld\n",ans);
            }
            else
            {
                sf(d);
                if(a==1)
                    update(1,1,n,b,c,d,1);
                else
                    update(1,1,n,b,c,d,0);
            }
        }
    }

    return 0;
}


SPOJ: BTCODE_G – Coloring Trees

Problem Link : http://www.spoj.com/problems/BTCODE_G/

Solution Idea:

    The solution idea of this problem is not so hard. This one can be solve with Heavy Light Decomposition. But as the time limit is very tight we need a lot of optimization. To solve this problem we need to convert the tree to an array using Euler tour or in-order traversal on the tree. Now there are 2 types of operation. Let consider each tree node as a special node which contain a 30 size array for storing it’s color information.

    Now let a paint operation is 1 a b. Now add +1 to array index [b] of discovery_time(a)node and -1 to array index [b] of finishing_time[a) node.

    For each query operation 2 a b we need to check for each color. Now at first determine the LCA of node a and b in the original given graph. Now for the i’th color we need to count the summation of array[i] from root node to discovery_time(a) node. Let this summation is x. Then we need count the summation of array[i] from root node to discovery_time(b) node. Let this summation is y. Here we add root to LCA node’s value twice but we don’t need this. So we need to subtract this from the sum. So we need count the summation of array[i] from root node to discovery_time(LCA) node. Let this is z. Now if we subtract 2*z then we will delete the LCA node’s value so wee need to add this value too.

    So Total number of i’th color node in the path from a to b is

    =x+y-(2*z)+ array[i] value of LCA node.

    We can do this for each of 30 color and When we get a color which fill every node in the range a to b then we will print YES otherwise NO.

    I have implemented this solution using segment tree but got TLE several time. Then I implement the same idea using BIT and got AC. I think the main idea behind the TLE in segment tree is wee need to copy the 30 size array element several time in segment tree. Which will take some time. As the time limit is very tight, the segment tree solution is inefficient.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 200005

vector<int>g[mx];
pii times[mx];
int dfsnum;
int parent[mx],level[mx],node_cnt[2*mx];

void dfs(int u, int p)
{
    times[u].ff=++dfsnum;
    parent[u]=p;
    for(int i=0; i<SZ(g[u]); i++)
    {
        int v=g[u][i];
        if(v==p) continue;
        level[v]=level[u]+1;
        dfs(v,u);
    }
    times[u].ss=++dfsnum;
}

int dp[mx][21];

int func_lca(int idx, int p)
{
    if(p==0)
    {
        return dp[idx][p]=parent[idx];
    }
    int &ret=dp[idx][p];
    if(ret!=-1) return ret;
    int u=func_lca(idx,p-1);
    ret=func_lca(u,p-1);
    return ret;
}


int lca_query(int p, int q)
{
    if(level[q]>level[p]) swap(p,q);
    for(int i=20;i>=0;i--)
    {
        int a=func_lca(p,i);
        if(level[a]>=level[q])
            p=a;
    }

    if(p==q) return p;

    for(int i=20;i>=0;i--)
    {
        int a=func_lca(p,i);
        int b=func_lca(q,i);
        if(a!=b)
        {
            p=a;
            q=b;
        }
    }

    return parent[p];
}


int tree[31][2*mx];

void update(int id, int idx, int val)
{
    for(;idx<=dfsnum && idx;idx+=idx&-idx)
        tree[id][idx]+=val;
}

int query(int id, int idx)
{
    int ret=0;
    for(;idx;idx-=idx&-idx)
        ret+=tree[id][idx];
    return ret;
}




int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n;
    sf(n);
    for(int i=1; i<n; i++)
    {
        int a,b;
        sff(a,b);
        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(0,0);

    int qq;
    sf(qq);

    for(int i=0;i<n;i++)
    {
        node_cnt[times[i].ff]=1;
        node_cnt[times[i].ss]=-1;
    }

    partial_sum(node_cnt,node_cnt+(2*mx),node_cnt);


    ms(dp,-1);

    while(qq--)
    {
        int a,b,c;
        sfff(a,b,c);
        if(a==1)
        {
            update(c,times[b].ff,1);
            update(c,times[b].ss,-1);
        }
        else
        {
            if(times[b].ff>times[c].ff)
                swap(b,c);

            bool ans=0;

            int lca=lca_query(b,c);

            for(int i=1;i<=30;i++)
            {
                int x=query(i,times[c].ff);
                int y=query(i,times[b].ff);
                int z=query(i,times[lca].ff);
                x=(x+y-(2*z));
                x+=query(i,times[lca].ff)-query(i,times[lca].ff-1);
                y=node_cnt[times[b].ff]+node_cnt[times[c].ff]-(2*node_cnt[times[lca].ff])+(node_cnt[times[lca].ff]-node_cnt[times[lca].ff-1]);
                if(x)
                {
                    if(x==y)
                        ans=1;
                    break;
                }
            }


            if(ans==0)
                printf("NO\n");
            else
                printf("YES\n");

        }
    }
    return 0;
}


SPOJ: SUMSUM – Enjoy Sum with Operations

Problem Link : http://www.spoj.com/problems/SUMSUM/

Solution Idea:

    This one is a interesting problem. The main idea behind the problem is combinatorics. At first we need to count the number of 1 bit and number of 0 bit in the i_th position of a given number. Then we need to do some combinatorial calculation.

    Now think about an array of 4 number A=[1,0,1,0]. If we perform OR operation in the range 1 to 4 what will we get? We get 5 as answer. If we form pair from this number and perform OR operation between then then we will get the answer. Now as here is 4 element so we can perform pair in 4*(4-1)/2 = 6 ways. Now comes the tricky part. For OR operation how many pair will contribute nothing ?? Here is 2 zero and we can form 1 pair from this two element who will not contribute anything. So for i_th bit position the contribution for OR operation is number_of_active_pair*(2^i).

    For AND operation we need to consider the number of pair can be form by 1 bit and for XOR the number of pair will be number_of_one_bit*number_of_zero_bit.

    We can consider a number as an array of 30 element whose value is either 0 or 1 and perform above operation.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005

int tree[28][mx];

void update(int id, int idx, int val)
{
    for(;idx<mx && idx;idx+=idx&-idx)
        tree[id][idx]+=val;
}

ll query(int id, int idx)
{
    ll ret=0;
    for(;idx;idx-=idx&-idx)
        ret+=tree[id][idx];
    return ret;
}

int ara[mx];

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n,q;
    sff(n,q);
    for(int i=1;i<=n;i++) sf(ara[i]);

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<28;j++)
        {
            if(check(ara[i],j))
                update(j,i,1);
        }
    }

    while(q--)
    {
        int a,b,c;
        sf(a);
        if(a==1)
        {
            sff(b,c);
            for(int i=0;i<28;i++)
            {
                if(check(ara[c],i))
                    update(i,c,-1);
            }
            ara[c]=b;
            for(int i=0;i<28;i++)
            {
                if(check(ara[c],i))
                    update(i,c,1);
            }
        }
        else
        {
            char ss[10];
            scanf(" %s",&ss);
            string str=string(ss);
            sff(b,c);
            ll temp[30];
            for(int i=0;i<28;i++)
            {
                temp[i]=query(i,c);
            }
            for(int i=0;i<28;i++)
            {
                temp[i]-=query(i,b-1);
            }

            ll ans=0;

            for(int i=0;i<28;i++)
            {
                ll one=temp[i];
                ll zero=(c-b+1)-one;
                ll pairs=0;
                if(str=="OR")
                {
                    ll total=one+zero;
                    pairs=(total*(total-1))/2;
                    pairs-=(zero*(zero-1))/2;
                }
                else if(str=="AND")
                {
                    pairs=(one*(one-1))/2;
                }
                else if(str=="XOR")
                {
                    pairs=one*zero;
                }
                ans+=(1LL<<i)*pairs;
            }

            printf("%lld\n",ans);
        }
    }


    return 0;
}

SPOJ: FREQUENT – Frequent values

Problem Link : http://www.spoj.com/problems/FREQUENT/

Solution Idea:

    In this problem an array of non-decreasing order is given. In each query a range l and r is given. You have to tell the maximum frequency of a number in the range l to r.

    Now as the given array is in non-decreasing order. So you can replace array a = {1 1 1 2 2 3 3 3 3} by another array b = {3 2 4}. After this compression the problem is converted to a Range Maximum query problem which can be easily solved by segment tree or sparse table. Now for each query determine the index in the compress array and perform range maximum query on that range.

    Think about the first and index of the query range. You need to handle them separately.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005

pii block[mx];

int dp[mx][20];

int ara[mx],id[mx],cnt=0,table[mx];

int func(int idx, int p)
{
    if(idx>cnt) return 0;
    if(p==0)
    {
        return dp[idx][p]=table[idx];
    }
    int &ret=dp[idx][p];
    if(ret!=-1) return ret;
    ret=max(func(idx,p-1),func(idx+(1<<(p-1)),p-1));
    return ret;
}

int query(int l, int r)
{
    if(r<l) return 0;
    if(l==r) return table[l];
    int log=(int)log2(r-l);
    return max(func(l,log),func(r-(1<<log)+1,log));
}

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int n,q;
    while(sf(n))
    {
        if(n==0) break;
        sf(q);
        for(int i=1; i<=n; i++)
        {
            sf(ara[i]);
        }
        cnt=0;
        ms(table,0);
        ms(dp,-1);
//        ms(block,0);
//        ms(id,0);
        for(int i=1; i<=n; i++)
        {
            int j=i;
            cnt++;
            block[cnt].ff=i;
            while(ara[j]==ara[i] && j<=n)
            {
                id[j]=cnt;
                table[cnt]++;
                j++;
            }
            j--;
            block[cnt].ss=j;
            i=j;
        }

        while(q--)
        {
            int a,b;
            sff(a,b);
            if(id[a]==id[b])
            {
                printf("%d\n",b-a+1);
            }
            else
            {
                int l=id[a];
                int r=id[b];
                int ans=0;
                ans=max(ans,block[l].ss-a+1);
                l++;
                ans=max(ans,b-block[r].ff+1);
                r--;
                ans=max(ans,query(l,r));
                printf("%d\n",ans);
            }
        }

    }

    return 0;
}