Light OJ: 1267 – Points in Rectangle (II)

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1267

Solution Idea:

    This problem is similar to Codeforces gym 101484: B. Nicoleta‚Äôs Cleaning . We need line sweep technique and some data structure to solve this problem. We need to convert each rectangle to opening and closing with respective to it’s x coordinates. Then we need to sort all points and opening and closing together. then for each opening element we need to count how many points are before opening point let is is X and for each closing we need to count how many points are before and on the closing point in the range lower y coordinate to upper y coordinate let it is Y. Then the the number of points inside the rectangle is Y-X. For each given point we need to update it when we find it through scan line in x coordinate of it.


#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));}
/*------------------------------------------------*/

struct data
{
    int type,x,st,ed,id;
};

vector<int>x,y;
vector<data>v;

bool cmp(data a, data b)
{
    if(a.x<b.x) return true;
    if(a.x==b.x)
        return a.type<b.type;
    return false;
}

#define mx 300005

int tree[mx];

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

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

int ans[mx];

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,m;
        sff(n,m);
        for(int i=0; i<n; i++)
        {
            int a,b;
            sff(a,b);
            data temp;
            temp.type=2;
            temp.x=a;
            temp.ed=temp.st=b;
            v.pb(temp);
            x.pb(a);
            y.pb(b);
        }

        for(int i=0; i<m; i++)
        {
            int a,b,c,d;
            sff(a,b);
            sff(c,d);
            x.pb(a);
            x.pb(c);
            y.pb(b);
            y.pb(d);
            data temp;
            temp.type=3;
            temp.x=c;
            temp.st=b;
            temp.ed=d;
            temp.id=i;
            v.pb(temp);
            data temp1;
            temp1.type=1;
            temp1.x=a;
            temp1.st=b;
            temp1.ed=d;
            temp1.id=i;
            v.pb(temp1);
        }

//    sort(all(x));
        sort(all(y));
        sort(all(v),cmp);

        for(int i=0; i<SZ(v); i++)
        {
            data temp=v[i];
            if(temp.type==1)
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                int b=lower_bound(all(y),temp.ed)-y.begin()+1;
                int xx=query(b);
                int yy=query(a-1);
                ans[temp.id]=xx-yy;
            }
            else if(temp.type==3)
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                int b=lower_bound(all(y),temp.ed)-y.begin()+1;
                int xx=query(b);
                int yy=query(a-1);
                ans[temp.id]=(xx-yy)-ans[temp.id];
            }
            else
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                update(a,1);
//            int yy=query(a-1); // Never do this while range update on BIT -_-
//            ans[temp.id]=xx;
            }
        }

        LINE_PRINT_CASE;
        for(int i=0; i<m; i++)
            printf("%d\n",ans[i]);
        ms(tree,0);
        x.clear();
        y.clear();
        v.clear();
    }
    return 0;
}


Advertisements

Codeforces gym 101484: B. Nicoleta’s Cleaning

1

Problem Link : http://codeforces.com/gym/101484/problem/B

Solution Idea:

    To solve this problem we need line sweep technique and some data structure. At first convert each rectangle in two element with respect to it x coordinate which both x coordinate have same y coordinates. Now call first x point opening and 2nd x point closing of a rectangle. Now take a array of custom data type. and store every opening and closing of rectangles and the query points and sort the the array in the basis of x coordinate of each element and in case of a tie take closing element first then query point and then opening point.

    Now run a loop on the x axis and update every range by 1 if we find a opening and by -1 if we find a closing and if we find a query point just query the value of that point.

    Handle the boundary condition carefully.



#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));}
/*------------------------------------------------*/

struct data
{
    int type,x,st,ed,id;
};

vector<int>x,y;
vector<data>v;

bool cmp(data a, data b)
{
    if(a.x<b.x) return true;
    if(a.x==b.x)
        return a.type<b.type;
    return false;
}

#define mx 300005

int tree[mx];

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

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

int ans[mx];

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

    int n,m;
    sff(n,m);
    for(int i=0; i<n; i++)
    {
        int a,b;
        sff(a,b);
        data temp;
        temp.type=2;
        temp.x=a;
        temp.ed=temp.st=b;
        temp.id=i;
        v.pb(temp);
        x.pb(a);
        y.pb(b);
    }

    for(int i=0; i<m; i++)
    {
        int a,b,c,d;
        sff(a,b);
        sff(c,d);
        x.pb(a);
        x.pb(c);
        y.pb(b);
        y.pb(d);
        data temp;
        temp.type=1;
        temp.x=c;
        temp.st=b;
        temp.ed=d;
        v.pb(temp);
        data temp1;
        temp1.type=3;
        temp1.x=a;
        temp1.st=b;
        temp1.ed=d;
        v.pb(temp1);
    }

//    sort(all(x));
    sort(all(y));
    sort(all(v),cmp);

    for(int i=0; i<SZ(v); i++)
    {
        data temp=v[i];
        if(temp.type==1)
        {
            int a=lower_bound(all(y),temp.st)-y.begin()+1;
            int b=lower_bound(all(y),temp.ed)-y.begin()+1;
            update(a+1,-1);
            update(b,+1);
        }
        else if(temp.type==3)
        {
            int a=lower_bound(all(y),temp.st)-y.begin()+1;
            int b=lower_bound(all(y),temp.ed)-y.begin()+1;
            update(a+1,+1);
            update(b,-1);
        }
        else
        {
            int a=lower_bound(all(y),temp.st)-y.begin()+1;
            int xx=query(a);
//            int yy=query(a-1); // Never do this while range update on BIT -_-
            ans[temp.id]=xx;
        }
    }


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

    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;
}

Timus: 1523. K-inversions

Problem Link : http://acm.timus.ru/problem.aspx?space=1&num=1523

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              1000000000
#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 20006

ll tree[12][mx];
ll ara[mx],ara2[12][mx];

void update(int id, int idx, ll 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;
}

//vector<ll>v;

int main()
{

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

    int n,k;
    sff(n,k);
//    v.pb(0);
    loop1(i,n)
    {
        sfl(ara[i]);
        ara2[1][i]=1;
//        v.pb(ara[i]);
    }
//    sort(all(v));

    ll ans=0;
    for(int j=1; j<k; j++)
    {
        for(int i=n; i>0; i--)
        {
//        int id=lower_bound(all(v),ara[i])-v.begin();
            int id=ara[i];
            ara2[j+1][i]=query(j,id)%MOD;
            update(j,id+1,ara2[j][i]);
//        update(0,id-1,-1);
        }
    }

//    for(int i=n; i>0; i--)
//    {
////        int id=lower_bound(all(v),ara[i])-v.begin();
//        int id=ara[i];
//        ans+=query(1,id);
//        update(1,id+1,ara2[i]);
////        update(1,id-1,-ara2[i]);
//    }

    for(int i=1; i<=n; i++)
        ans+=ara2[k][i];

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

    return 0;
}


SPOJ: TRIPINV – Mega Inversions

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

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));}
/*------------------------------------------------*/

#define mx 100006

ll tree[2][mx];
ll ara[mx],ara2[mx];

void update(int id, int idx, ll 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;
}

//vector<ll>v;

int main()
{

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

    int n;
    sf(n);
//    v.pb(0);
    loop1(i,n)
    {
        sfl(ara[i]);
//        v.pb(ara[i]);
    }
//    sort(all(v));

    ll ans=0;

    for(int i=n; i>0; i--)
    {
//        int id=lower_bound(all(v),ara[i])-v.begin();
        int id=ara[i];

        ara2[i]=query(0,id);
        update(0,id+1,1);
//        update(0,id-1,-1);
    }

    for(int i=n; i>0; i--)
    {
//        int id=lower_bound(all(v),ara[i])-v.begin();
        int id=ara[i];
        ans+=query(1,id);
        update(1,id+1,ara2[i]);
//        update(1,id-1,-ara2[i]);
    }

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

    return 0;
}


Codeforce gym: 101484 F. No Link, Cut Tree!

Problem Link : http://codeforces.com/gym/101484/problem/F

Solution Idea:

    My solution idea for this problem is at first make the given tree a full binary tree. A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. On the other hand A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. So we can convert a complete binary tree to a full binary tree by adding some dummy node whose cost is 0 so that they don’t contribute anything in the solution as well as they will help us to form our solution.

    Now classify the nodes according to their level and make their cumulative sum or insert them in segment tree or in a binary indexed tree. We need this data structure for every level. Now map the nodes by the inorder traversal of the tree and position of the level array like 1,2,3….

    Now here comes an important observation in a full binary tree at any level, if I want to delete a subtree starting at node u the will need to delete 1 node from level[u], 2 node from level[u]+1, 4 node from level[u]+2…2^i node form level[u]+i.

    Now form the data structure (here I have used Binary Indexed Tree(BIT)) just query the contribution of the deleted node subtract them form the total contribution of that level and take the maximum. We need to do this from level[u] to last level and we need to consider the whole level from level 1 to level[u]-1.


#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];

vector<int>level_g[20];

int map1[mx],levell[mx];
int map2_level[mx],cost[mx],max_depth,disc;
int tree[20][mx];
int n,m;


void dfs1(int u, int level)
{
    max_depth=max(max_depth,level);
    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];
        dfs1(v,level+1);
    }
}

void dfs(int u, int par, int level)
{
    levell[u]=level;
//    max_depth=max(max_depth,level);
    map1[u]=++disc;
    level_g[level].pb(u);

    if(levell[u]!=max_depth)
    {
        if(SZ(g[u])==0)
            g[u].pb(++n);
        if(SZ(g[u])==1)
            g[u].pb(++n);
    }

    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];
        if(v==par) continue;
        dfs(v,u,level+1);
    }
}



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

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

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


    sff(n,m);
    sf(cost[1]);

    for(int i=1;i<n;i++)
    {
        int a,b,c;
        sfff(a,b,c);
        g[b].pb(a);
        cost[a]=c;
    }
    dfs1(1,1);
//    int xx=n;
//    for(int i=1;i<=xx;i++)
//    {
//        if(SZ(g[i])==1)
//            g[i].pb(++n);
//    }

    dfs(1,1,1);

    for(int i=1;i<=max_depth;i++)
    {
        int num=0;
        for(int j=0;j<SZ(level_g[i]);j++)
        {
            int v=level_g[i][j];
            map2_level[map1[v]]=++num;
            update(i,num,cost[v]);
        }
    }

    while(m--)
    {
        int u;
        sf(u);
        int ans=0;
        for(int i=1;i<levell[u];i++)
            ans=max(ans,query(i,mx-1));
        int last=levell[u],pp=0,cur=map1[u];
        for(int i=levell[u];i<=max_depth;i++)
        {
            int total=query(i,mx-1);
            int sub=query(i,map2_level[cur]+(1<<pp)-1);
            int sub1=query(i,map2_level[cur]-1);
            total-=(sub-sub1);
            ans=max(ans,total);
            pp++;
            cur++;
        }

        printf("%d\n",ans);

    }



    return 0;
}