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

Advertisements

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

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


Codeforces: 61 E. Enemy is weak

2

Problem Link : http://codeforces.com/contest/61/problem/E

Solution Idea:

    In this problem we need to count the number of triple inverse triplets on a given array. A triple inverse triplet is three positions i, j, k on an array A=[] such that i < j  Aj > Ak.

    Now to solve this problem we need some range update and query data structure like segment tree or binary indexed tree. The idea is at first compress the array by mapping the numbers from range 1 to 10^6. After that read the array from reverse order and query the value of that mapped index on segment tree(let this mapped index is id)and store it on an array let name this array ara2=[]. After that increment the value of the index id+1 to n. It means that when we read any number from id+1 to n we can know that current number id have impact on this number. Here id is the k_th element of the triplet and all the number from id+1 to n is the j_th element of the triplet. Now each ara2[] index hold the number of inverse pair starting at id.

    Now read the array element from the reverse order again and do the same thing. This time we need another segment tree. This time when we stand on position id add the value of the segment tree of position id to the answer and update all position in the range id+1 to n by ara2[index_of_id]. Do this for the whole array.

    We can repeat this technique for 4,5,6 element inversion too.



#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 1000006

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();
        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();
        ans+=query(1,id);
        update(1,id+1,ara2[i]);
//        update(1,id-1,-ara2[i]);
    }

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

    return 0;
}

Codeforces: 877E. Danil and a Part-time Job

Problem Link : http://codeforces.com/contest/877/problem/E

Solution Idea:

    Run a dfs on the given for getting the Euler tour order or inorder traversal order. Then the tree is converted to a liner 1D array. Now we can apply range query and update on this array.

    Now use a range update query data structure. Here I have used segment tree. Now initialize the tree with the initial value and now our job is to just toggle a subtree of the given tree and perform query operation. Use a propagation for the update and answer the query.



#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
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
pii info[mx];
vector<int>g[mx];
int cnt=0;
int maps[mx],ara[mx];

void dfs(int u, int par)
{
    info[u].ff=++cnt;
    maps[cnt]=u;
    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];
        if(v==par) continue;
        dfs(v,u);
    }
    info[u].ss=cnt;
}

struct data
{
    int val, prop;
};

data tree[3*mx];

void push_down(int n, int b, int e)
{
    if(tree[n].prop%2)
    {
        segment_tree;
        tree[l].val=(mid-b+1)-tree[l].val;
        tree[l].prop++;
        tree[r].val=(e-mid)-tree[r].val;
        tree[r].prop++;
        tree[n].prop=0;
    }
}

void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].val=ara[maps[b]];
        tree[n].prop=0;
        return;
    }
    segment_tree;
    init(l,b,mid);
    init(r,mid+1,e);
    tree[n].val=tree[l].val+tree[r].val;
}

void update(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        tree[n].val=(e-b+1)-tree[n].val;
        tree[n].prop++;
        return;
    }
    push_down(n,b,e);
    segment_tree;
    update(l,b,mid,i,j);
    update(r,mid+1,e,i,j);
    tree[n].val=tree[l].val+tree[r].val;
}

int 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].val;
    push_down(n,b,e);
    segment_tree;
    int p=query(l,b,mid,i,j);
    int q=query(r,mid+1,e,i,j);
    return p+q;
}

char str[10];

int main()
{

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

    int n;
    sf(n);
    for(int i=2;i<=n;i++)
    {
        int a;
        sf(a);
        g[a].pb(i);
    }

    for(int i=1;i<=n;i++) sf(ara[i]);
    dfs(1,1);
    init(1,1,n);
    int q;
    sf(q);
    while(q--)
    {
        int a;
        scanf(" %s %d",str,&a);
        if(str[0]=='g')
        {
            int x=query(1,1,n,info[a].ff,info[a].ss);
            printf("%d\n",x);
        }
        else
        {
            update(1,1,n,info[a].ff,info[a].ss);
        }
    }



    return 0;
}

Codeforces Gym: 101484 E. Double Fence

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

Solution Idea:

    Let P1 and P2 be respectively the set of points of the first polygon and the set of points of the second polygon. Let ch(X) be the set of points on the convex hull of the set of points X, including colinear points on the edges. A polygon is strictly inside the other if ch(P1 U P2 equals to P1 or P2.

#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<iostream>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<climits>
#include<complex>
#define mp make_pair
#define pb push_back
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const double inf=1e20;
const int maxp=200007;
int dblcmp(double d)
{
    if (fabs(d)<eps)return 0;
    return d>eps?1:-1;
}
inline double sqr(double x)
{
    return x*x;
}

struct point
{
    double x,y;
    point()             {                                    }
    point(double _x,double _y)
    {
        x = _x;
        y = _y;
    }
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    void output()
    {
        printf("%.2f %.2f\n",x,y);
    }
    bool operator==(point a)const
    {
        return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;
    }
    bool operator<(point a)const
    {
        return dblcmp(a.x - x) == 0 ? dblcmp(y - a.y) < 0 : x < a.x;
    }
    point operator-(point a)const
    {
        return point(x-a.x, y-a.y);
    }
    double len()
    {
        return hypot(x, y);
    }
    double len2()
    {
        return x * x + y * y;
    }
    double distance(point p)
    {
        return hypot(x - p.x, y - p.y);
    }
    point add(point p)
    {
        return point(x + p.x, y + p.y);
    }
    point sub(point p)
    {
        return point(x - p.x, y - p.y);
    }
    point mul(double b)
    {
        return point(x * b, y * b);
    }
    point div(double b)
    {
        return point(x / b, y / b);
    }
    double dot(point p)
    {
        return x*p.x+y*p.y;
    }
    double det(point p)
    {
        return x*p.y-y*p.x;
    }
    double rad(point a,point b)
    {
        point p=*this;
        return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));
    }
    point trunc(double r)
    {
        double l=len();
        if (!dblcmp(l))return *this;
        r/=l;
        return point(x*r,y*r);
    }
    point rotleft()
    {
        return point(-y,x);
    }
    point rotright()
    {
        return point(y,-x);
    }
    point rotate(point p,double angle)
    {
        point v=this->sub(p);
        double c=cos(angle),s=sin(angle);
        return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    }
};

struct line
{
    point a,b;
    line()              {                                    }
    line(point _a,point _b)
    {
        a=_a;
        b=_b;
    }
    bool operator==(line v)
    {
        return (a==v.a)&&(b==v.b);
    }
    line(point p,double angle)
    {
        a=p;
        if (dblcmp(angle-pi/2)==0)
        {
            b=a.add(point(0,1));
        }
        else
        {
            b=a.add(point(1,tan(angle)));
        }
    }
    //ax+by+c=0
    line(double _a,double _b,double _c)
    {
        if (dblcmp(_a)==0)
        {
            a=point(0,-_c/_b);
            b=point(1,-_c/_b);
        }
        else if (dblcmp(_b)==0)
        {
            a=point(-_c/_a,0);
            b=point(-_c/_a,1);
        }
        else
        {
            a=point(0,-_c/_b);
            b=point(1,(-_c-_a)/_b);
        }
    }
    void input()
    {
        a.input();
        b.input();
    }
    void adjust()
    {
        if(b<a)swap(a,b);
    }
    double length()
    {
        return a.distance(b);
    }
    double angle()
    {
        double k=atan2(b.y-a.y,b.x-a.x);
        if (dblcmp(k)<0)k+=pi;
        if (dblcmp(k-pi)==0)k-=pi;
        return k;
    }
    int relation(point p)
    {
        int c=dblcmp(p.sub(a).det(b.sub(a)));
        if (c<0)return 2;
        if (c>0)return 1;
        return 0;
    }
    bool pointonseg(point p)
    {
        return dblcmp(p.sub(a).det(b.sub(a)))==0&&dblcmp(p.sub(a).dot(p.sub(b)))<=0;
    }
    bool parallel(line v)
    {
        return dblcmp(b.sub(a).det(v.b.sub(v.a)))==0;
    }
    int segcrossseg(line v)
    {
        int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
        int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
        int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
        if ((d1^d2)==-2&&(d3^d4)==-2)return 2;
        return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||
                d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||
                d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||
                d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);
    }
    int segcrossseg_inside(line v)
    {
        if(v.pointonseg(a) || v.pointonseg(b) || pointonseg(v.a) || pointonseg(v.b)) return 0;
        int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
        int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
        int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
        if ((d1^d2)==-2&&(d3^d4)==-2)return 1;
        return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||
                d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||
                d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||
                d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);
    }
    int linecrossseg(line v) //*this seg v line
    {
        int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
        if ((d1^d2)==-2)return 2;
        return (d1==0||d2==0);
    }
    int linecrossline(line v)
    {
        if ((*this).parallel(v))
        {
            return v.relation(a)==3;
        }
        return 2;
    }
    point crosspoint(line v)
    {
        double a1=v.b.sub(v.a).det(a.sub(v.a));
        double a2=v.b.sub(v.a).det(b.sub(v.a));
        return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));
    }
    double dispointtoline(point p)
    {
        return fabs(p.sub(a).det(b.sub(a)))/length();
    }
    double dispointtoseg(point p)
    {
        if (dblcmp(p.sub(b).dot(a.sub(b)))<0||dblcmp(p.sub(a).dot(b.sub(a)))<0)
        {
            return min(p.distance(a),p.distance(b));
        }
        return dispointtoline(p);
    }
    point lineprog(point p)
    {
        return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));
    }
    point symmetrypoint(point p)
    {
        point q=lineprog(p);
        return point(2*q.x-p.x,2*q.y-p.y);
    }
};

struct polygon
{
    int n=0;
    point p[maxp];
    line l[maxp];
    void input(int _n)
    {
        n=_n;
        for (int i=0; i<n; i++)   p[i].input();
    }
    void add(point q)
    {
        p[n++]=q;
    }
    void getline()
    {
        for (int i=0; i<n; i++)
            l[i]=line(p[i],p[(i+1)%n]);
    }
    struct cmp
    {
        point p;
        cmp(const point &p0)
        {
            p=p0;
        }
        bool operator()(const point &aa,const point &bb)
        {
            point a=aa,b=bb;
            int d=dblcmp(a.sub(p).det(b.sub(p)));
            if (d==0)
                return dblcmp(a.distance(p)-b.distance(p))<0;
            return d>0;
        }
    };
    void norm()
    {
        point mi=p[0];
        for (int i=1; i<n; i++)mi=min(mi,p[i]);
        sort(p,p+n,cmp(mi));
    }
    void getconvex(polygon &convex)
    {
        int i;
        sort(p,p+n);
        convex.n=n;
        for (i=0; i<min(n,2); i++) convex.p[i]=p[i];
        if (n<=2)return;
        int &top=convex.n;
        top=1;
        for (i=2; i<n; i++)
        {
            while (top&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<0)
                top--;
            convex.p[++top]=p[i];
        }
        int temp=top;
        convex.p[++top]=p[n-2];
        for (i=n-3; i>=0; i--)
        {
            while (top!=temp&&convex.p[top].sub(p[i]).det(convex.p[top-1].sub(p[i]))<0)
                top--;
            convex.p[++top]=p[i];
        }
    }
    bool isconvex()
    {
        bool s[3];
        memset(s,0,sizeof(s));
        int i,j,k;
        for (i=0; i<n; i++)
        {
            j=(i+1)%n;
            k=(j+1)%n;
            s[dblcmp(p[j].sub(p[i]).det(p[k].sub(p[i])))+1]=1;
            if (s[0]&&s[2])return 0;
        }
        return 1;
    }

};

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    polygon a,b,ab;
    for(int i=0; i<n; i++)
    {
        double x,y;
        scanf("%lf %lf",&x,&y);
        a.add(point(x,y));
        ab.add(point(x,y));
    }
    for(int i=0; i<m; i++)
    {
        double x,y;
        scanf("%lf %lf",&x,&y);
        b.add(point(x,y));
        ab.add(point(x,y));
    }

    polygon cha, chb, chab;

//    a.getconvex(cha);
//    b.getconvex(chb);
    ab.getconvex(chab);

    sort(a.p,a.p+a.n);
    sort(b.p,b.p+b.n);
    sort(chab.p,chab.p+chab.n);

//       cout<<ab.n<<endl;
//    for(int i=0;i<ab.n;i++)
//        cout<<ab.p[i].x<<" "<<ab.p[i].y<<endl;
//
//    cout<<"---------------------"<<endl;
//
//    cout<<chab.n<<endl;
//    for(int i=0;i<chab.n;i++)
//        cout<<chab.p[i].x<<" "<<chab.p[i].y<<endl;

    if(a.n==chab.n)
    {
        bool check=0;
        for(int i=0; i<a.n; i++)
            if(a.p[i]==chab.p[i]) continue;
            else
            {
                check=1;
                break;
            }
        if(check==0)
        {
            printf("YES\n");
            return 0;
        }
    }

    if(b.n==chab.n)
    {
        bool check=0;
        for(int i=0; i<b.n; i++)
            if(b.p[i]==chab.p[i]) continue;
            else
            {
                check=1;
                break;
            }
        if(check==0)
        {
            printf("YES\n");
            return 0;
        }
    }

    printf("NO\n");
    return 0;

}