Mobius Inversion (Mobius Precalculate)

 const ll N=1e6+5;

ll lp[N];

ll mob[N];

void mobiusPreCalc(){

    mob[1] = 1;

    for (ll i = 2; i < N; ++i) {

        if (!lp[i]) for (ll j = i; j < N; j += i)

            if (!lp[j]) lp[j] = i;

        mob[i] = [](ll x) {

            ll cnt = 0;

            while (x > 1) {

                ll k = 0, d = lp[x];

                while (x % d == 0) {

                    x /= d;

                    ++k;

                    if (k > 1) return 0;

                }

                ++cnt;

            }

            if (cnt & 1) return -1;

            return 1;

        }(i);

    }

}

Detect Cycle and Print Cycle in an directed Graph

Problem :

https://leetcode.com/problems/course-schedule-ii/ 

class Solution {

public:

    vector<int>vis;

    vector<int>vec[5005];

    vector<int> ans;

    bool dfsAndReturnCycle(int src)

    {

        if(vis[src] == 1) 

            return true;

        if(vis[src] == 2) 

            return false;

        vis[src] = 1; 

        for (const auto& nextNode: vec[src])

        {

if(dfsAndReturnCycle(nextNode))

                return true;

        }

        vis[src] = 2;

        ans.push_back(src);

        return false;

        

    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& ar) {

        int n=ar.size();

        for(int i=0;i<n;i++){

            int v=ar[i][0];

            int u=ar[i][1];

            vec[u].push_back(v);

        }

        int flag=0;

        vis = vector<int>(numCourses+2,0);

        for(int i=0;i<numCourses;i++)

        {

            if(vis[i]==0){

                if(dfsAndReturnCycle(i))

                {

                    return {};

                }

            }

        }

        reverse(ans.begin(),ans.end());

        return ans;

    }

};

FREQ2 - Most Frequent Value- Using Mo's Algorithm

You are given a sequence of n integers a0, a1, ..., an-1. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n-1). For each query, determine the number of occurrences of the most frequent value among the integers ai, ..., aj.

Mo's Algorithm Related Problem:

1) DQUERY - D-query , 2) FREQ2 - Most Frequent Value , 3) D. Cut and Stick  , 4) D. Powerful array , 5) Chef and Graph Queries 6) D. Tree and Queries 7) Sherlock and Inversions

   

 

///...................SUBHASHIS MOLLICK...................///

///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///

///.............ISLAMIC UNIVERSITY,BANGLADESH.............///

///....................SESSION-(14-15)....................///

#include<bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")

#pragma GCC optimization ("O3")

#pragma GCC optimization ("unroll-loops")

#define sf(a) scanf("%d",&a)

#define sf2(a,b) scanf("%d %d",&a,&b)

#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)

#define pf(a) printf("%d",a)

#define pf2(a,b) printf("%d %d",a,b)

#define pf3(a,b,c) printf("%d %d %d",a,b,c)

#define sfl(a) scanf("%lld",&a)

#define sfl2(a,b) scanf("%lld %lld",&a,&b)

#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define pfl(a) printf("%lld",a)

#define pfl2(a,b) printf("%lld %lld",a,b)

#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)

#define nl printf("\n")

#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long

#define pb push_back

#define MPI map<int,int>mp;

#define fr(i,n) for(i=0;i<n;i++)

#define fr1(i,n) for(i=1;i<=n;i++)

#define frl(i,a,b) for(i=a;i<=b;i++)

#define tz 100005

#define clr0(a) memset(a,0,sizeof(a))

#define clr1(a) memset(a,-1,sizeof(a))

#define space " "

#define yesp cout<<"YES"<<endl;

#define nop cout<<"NO"<<endl;

/*primes in range 1 - n

1 - 100(1e2) -> 25 pimes

1 - 1000(1e3) -> 168 primes

1 - 10000(1e4) -> 1229 primes

1 - 100000(1e5) -> 9592 primes

1 - 1000000(1e6) -> 78498 primes

1 - 10000000(1e7) -> 664579 primes

large primes ->

104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697

*/

//freopen("Input.txt","r",stdin);

//freopen("Output.txt","w",stdout);

//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

#define flagone(f) cout<<(f?"YES":"NO")<<endl;

#define flagzero(f) cout<<(f?"NO":"YES")<<endl;

int ar[tz],cnt[tz],ans[tz],freq[tz];

struct node

{

    int lft,right,index;

};

int mx=0;

node query[tz];

int blockSize=317;

bool cmp(node fst,node scnd)

{

    if(fst.lft/blockSize == scnd.lft/blockSize)

    {

        return fst.right/blockSize < scnd.right/blockSize;

    }

    return fst.lft<scnd.lft;

}

void addValue(int pos)

{

    cnt[ar[pos]]++;

    freq[cnt[ar[pos]]]++;

    mx=max(mx,cnt[ar[pos]]);

}

void removeValue(int pos)

{

    freq[cnt[ar[pos]]]--;

    if(freq[cnt[ar[pos]]]==0)

        mx--;

    cnt[ar[pos]]--;

}

main()

{

    timesave;

    //freopen("Input.txt","r",stdin);

    //freopen("Output.txt","w",stdout);

    int n,q,a,b;

    sf2(n,q);

    for(int i=0; i<n; i++)

    {

        sf(ar[i]);

    }

    for(int i=0; i<q; i++)

    {

        sf2(a,b);

        query[i].lft=a;

        query[i].right=b;

        query[i].index=i;

    }

    sort(query,query+q,cmp);

    int leftPointer = 0,rightPointer=0;

    for(int i=0; i<q; i++)

    {

        int leftValue = query[i].lft;

        int rightValue = query[i].right;

        int queryIndex = query[i].index;

        while(leftPointer<leftValue)

        {

            removeValue(leftPointer);

            leftPointer++;

        }

        while(leftPointer>leftValue)

        {

            addValue(leftPointer-1);

            leftPointer--;

        }

        while(rightPointer<=rightValue)

        {

            addValue(rightPointer);

            rightPointer++;

        }

        while(rightPointer>rightValue+1)

        {

            removeValue(rightPointer-1);

            rightPointer--;

        }

        ans[query[i].index]=mx;

        //cout<<leftValue<<" "<<rightValue<<" "<<mx<<endl;

    }

    for(int i=0; i<q; i++)

    {

        printf("%d\n",ans[i]);

    }

}

 

Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution

F. Counter RMQ 

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int ts,cs=1;

    cin>>ts;

    while(ts--)

    {

        int n,q,ar[20005]={0},i,j,a,b,x;

        cin>>n>>q;

        for(i=1;i<=q;i++)

        {

            cin>>a>>b>>x;

            for(j=a;j<=b;j++)

            {

                ar[j]=max(ar[j],x);

            }

        }

        printf("Case %d:",cs++);

        for(i=1;i<=n;i++)

        {

            if(ar[i]==0)

            {

                ar[i]=20000;

            }

            cout<<" "<<ar[i];

        }

        cout<<endl;

    }

    return 0;

}

I. Gadgets of Tomishu

#include <bits/stdc++.h>

#define sf1(a) scanf("%ld",&a)

#define sf2(a,b) scanf("%ld%ld",&a,&b);

#define sf3(a,b,c) scanf("%ld%ld%ld",&a,&b,&c);

using namespace std;

main()

{

    long ts,cs=1;

    sf1(ts);

    while(ts--)

    {

        long long i,ans,ar[100010]={0};

        long long n,k,mod;

        cin>>n>>k>>mod;

        //ar[0]=k%mod;

        ar[1]=((k%mod)*(k%mod))%mod ;

        ar[2]= ((ar[1]%mod) * (k%mod));

        for(i=3;i<=n;i++)

        {

           ar[i]=((ar[i-1]%mod) * (ar[i-2]%mod))%mod;

           //cout<<ar[i]<<" "<<ar[i-1]<<" "<<ar[i-2]<<endl;

        }

        ans=ar[n];

        printf("Case %ld: %lld\n",cs++,ans);

    }

}

Distinct numbers between a query

Problem Link: https://atcoder.jp/contests/abc174/tasks/abc174_e

Input:

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Output:

1
2
2
1
2
2
6
3
3
3

#include<bits/stdc++.h>

using namespace std;

const int N = (int) 5e5 + 5;

struct query

{

    int l,r,id;

} q[N];

int a[N],k=1000,l=1,r=0;

bool compare(query &a,query &b)

{

    int b_a = a.l/k;

    int b_b = b.l/k;

    if(b_a==b_b)

        return a.r<b.r;

    return b_a<b_b;

}

int cnt[N],ans[N];

int res=0;

void add(int x)

{

    cnt[a[x]]++;

    if(cnt[a[x]]==1)

        ++res;

}

void remove(int x)

{

    cnt[a[x]]--;

    if(cnt[a[x]]==0)

        --res;

}

int main()

{

    int n,Q;

    cin>>n>>Q;

    for(int i=1; i<=n; ++i)

        cin>>a[i];

    for(int i=1; i<=Q; ++i)

    {

        cin>>q[i].l>>q[i].r;

        q[i].id=i;

    }

    sort(q+1,q+Q+1,compare);

    for(int i=1; i<=Q; ++i)

    {

        while(l > q[i].l)

            add(--l);

        while(r < q[i].r)

            add(++r);

        while(l < q[i].l)

            remove(l++);

        while(r > q[i].r)

            remove(r--);

        ans[q[i].id]=res;

    }

    for(int i=1; i<=Q; ++i)

    {

        printf("%d\n", ans[i]);

    }

    return 0;

}

LCA Problem

In this problem you have to find the maximum weight between a path.
Suppose in the sample test case 2 to  6 have a path 2->1->6
In here 2->1 the weight is 1 & 1->6 the weight is 2 so the maximum weight is MAX(1,2)=2
Again 5 to 2  there have a path 5->3->1->2
In here 5->3 the weight is 8 & 3->1 the weight is 5  & 1->2 the weight is 1 so the maximum weight is  MAX(8,5,1)=8

Input:
6
1 2 1
1 3 5
3 4 3
3 5 8
1 6 2
3
2 6
5 2
4 6
0

Output:
2
8
5

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

Code:

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//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
#define N 100000
ll weight[20][N+5];
vector<pair<int,int> >vec[N+5];
int par[N+5],dis[N+5],vis[N+5],sparse[20][N+5];
void bfs(int src)
{
    dis[src]=0;
    par[src]=-1;
    queue<int>q;
    q.push(src);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=1;
        for(int i=0;i<vec[u].size();i++)
        {
            int v=vec[u][i].first,w=vec[u][i].second;
            if(vis[v]==0)
            {
                q.push(v);
                dis[v]=dis[u]+1;
                par[v]=u;
                weight[0][v]=w;
            }
        }
    }
}
void init()
{
    for(int i=1;i<=N;i++)
    {
        sparse[0][i]=par[ i ];
        for( int j = 1; 1 << j <= N; j++ )
        {
            sparse[j][i]=-1;
        }
    }
    for(int j=1;1<<j<=N;j++ )
    {
        for(int i=1;i<=N;i++)
        {
            sparse[j][i]=sparse[j-1][sparse[j-1][i]];
            weight[j][i]=max(weight[j-1][i],weight[j-1][sparse[j-1][i]]);
        }
    }
}
int lca( int u, int v )
{
    int lg=0;
    if(dis[u]<dis[v])
    {
        swap(u,v);
    }
    if(!dis[u])
    {
        return u;
    }
    for(lg=0;1<<lg<=dis[u];lg++);
    lg--;
    for(int i=lg;i>=0;i--)
    {
        if(dis[u]-(1<<i)>=dis[ v ] )
        {
            u=sparse[i][u];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(int i=lg;i>=0;i--)
    {
        if(sparse[i][u]!=-1&&sparse[i][u]!=sparse[i][v])
        {
            u=sparse[i][u];
            v= sparse[i][v];
        }
    }
    return par[u];
}

long long query( int u, int v )
{
    int LCA=lca(u,v);
    int uv,uu;
    long long maxi=0;
    for(uv=0;1<<uv<=dis[v];uv++);
    uv--;
    for(uu=0;1<<uu<=dis[u];uu++);
    uu--;
    if(!dis[u]&&!dis[v])
    {
        return maxi;
    }
    for(int i=uu;i>=0;i--)
    {
        if(dis[u]-(1<<i)>=dis[LCA])
        {
            maxi=max(maxi,weight[i][u]);
            u=sparse[i][u];
        }
    }
    for(int i=uv;i>=0;i--)
    {
        if(dis[v]-(1<<i)>=dis[ LCA ] )
        {
            maxi = max( maxi,weight[i][v]);
            v=sparse[i][v];
        }
    }
    return maxi;
}
main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        for(int i=0;i<=N;i++)
        {
            vec[i].clear();
            par[i]=-1;
            dis[i]=0;
            vis[i]=0;
            for(int j=0;j<20;j++)
            {
                weight[j][i]=0;
                //sparse[j][i]=-1;
            }
        }
        int u,v,w;
        for(int i=1;i<n;i++)
        {
            sf3(u,v,w);
            vec[u].push_back({v,w});
            vec[v].push_back({u,w});
        }
        bfs(1);
        init();
        int q;
        sf(q);
        for(int i=1;i<=q;i++)
        {
            sf2(u,v);
            printf("%lld\n",query(u,v));
        }
    }
}

Articulation Bridge Print

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//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
vector<int>vec[100005];
vector<pair<int,int> >bridge;
int id[100005],low[1000005],vis[100005],somoy;
void dfs(int uu,int par)
{
    low[uu]=id[uu]=++somoy;
    vis[uu]=1;
    for(int ii=0;ii<vec[uu].size();ii++)
    {
        int vv=vec[uu][ii];
        if(vv==par)
        {
            continue;
        }
        if(vis[vv]==0)
        {
            dfs(vv,uu);
            low[uu]=min(low[uu],low[vv]);
            if(id[uu]<low[vv])
            {
                bridge.push_back({min(uu,vv),max(uu,vv)});
            }
        }
        else
        {
            low[uu]=min(low[uu],id[vv]);
        }
    }
}
main()
{
    timesave;
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        int i,u,v;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=m;i++)
        {
            cin>>u>>v;
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        somoy=0;
        for(i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                dfs(i,-1);
            }
        }
        for(i=0;i<bridge.size();i++)
        {
            cout<<bridge[i].first<<" "<<bridge[i].second<<endl;
        }
        bridge.clear();
        for(i=1;i<=n;i++)
        {
            vec[i].clear();
        }
    }
}


/*
INPUT:
6 5
1 2
2 3
2 4
2 5
4 5

4 2
1 2
2 3


OUTPUT:
2 3
1 2

1 2
2 3
*/