CF – 464E The Classic Problem

Category: Data Structure, Persistent segment Tree
Solution:
See official Editorial here for understanding the basics.

Implementation:

#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define pb(a)                   push_back((a))
#define SZ(a)                   (int) a.size()
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define xx                      first
#define yy                      second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))

/*************************** END OF TEMPLATE ****************************/

const int N = 2e5+500;
int n,m,sz;
vector<pair<int,int> > G[N];
int root[N];
long long B = 37;
long long MOD = 1e9 + 7;
long long POW[N], POWER[N];
int zero;
struct  Node
{
	int ls,rs;
	int cnt;
	long long hash;	
} node[N*40];

void build(int &n,int b,int e)
{
	n = ++sz;
	if(b==e) {
		node[n].hash = node[n].cnt = 0;
		return;
	}
	int mid = (b+e)/2;
	build(node[n].ls, b, mid);
	build(node[n].rs, mid+1,e);
	node[n].cnt = node[node[n].ls].cnt + node[node[n].rs].cnt;
	node[n].hash = node[node[n].ls].hash +  POW[mid - b + 1] * node[node[n].rs].hash;
}
void update(int &n,int pre,int b,int e,int pos)
{
	n = ++sz;
	node[n] = node[pre];
	if(b==e && b == pos) {
		node[n].hash = 1;
		node[n].cnt = 1;
		return;
	}
	int mid = (b+e)/2;
	if(pos <= mid) update(node[n].ls, node[pre].ls , b, mid, pos);
	else update(node[n].rs, node[pre].rs, mid+1,e,pos);
	node[n].cnt = node[node[n].ls].cnt + node[node[n].rs].cnt;
	node[n].hash = node[node[n].ls].hash +  POW[mid - b + 1] * node[node[n].rs].hash;
}
void updateRange(int &n,int pre,int id2 , int b,int e,int i, int j)
{
	
	n = ++sz;
	node[n] = node[pre];
	if(b>j || e < i) return;

	if(b >= i && e <= j ) {
		node[n] = node[id2];
		return;
	}
	int mid = (b+e)/2;
	updateRange(node[n].ls, node[pre].ls, node[id2].ls, b, mid, i, j);
	updateRange(node[n].rs, node[pre].rs, node[id2].rs, mid+1,e,i, j);
	node[n].cnt = node[node[n].ls].cnt + node[node[n].rs].cnt;
	node[n].hash = node[node[n].ls].hash +  POW[mid - b + 1] * node[node[n].rs].hash;
}

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 node[n].cnt;
	int mid = (b+e)/2;
	return query(node[n].ls, b, mid, i, j) + query(node[n].rs, mid+1,e,i,j);
}
int find(int root,int w)
{
	
	int low = w, high = N , mid, ans = w - 1;
	while(low <= high) {
		mid = (low + high ) /2;
		int oo = query(root,0,N,w,mid);
		
		if( oo == mid - w+ 1) {
			ans = mid ;
			low = mid+1;
		}
		else high = mid-1;
	}
	return ans + 1;
}

bool queryIn(int r1 ,int r2, int b,int e)
{
	if(b==e) {
		return node[r1].hash > node[r2].hash;
	}
	int mid = (b+e)/2;
	if( node[node[r1].rs]. hash == node[node[r2].rs]. hash ) return queryIn(node[r1].ls, node[r2].ls, b , mid ) ;
	else return queryIn(node[r1].rs, node[r2].rs, mid+1,e);
}
long long tot = 0;
void Trv(int n,int b,int e)
{


	if(b==e) {
		if(node[n].hash) { 
			tot += POWER[b];
			tot %= MOD;
		}
		return;
	}
	int mid = (b+e)/2;
	Trv(node[n].ls, b, mid);
	Trv(node[n].rs, mid+1,e);
}

void show(int r,int b , int e)
{
	if(b==e) {printf("%lld",node[r].hash);
                  return;
        }
	int mid = (b+e)/2;
	show(node[r].ls, b , mid);
	show(node[r].rs , mid+1,e);
}
struct Vertex
{
	int id;
	int r;
	bool operator<(const Vertex &p) const {
		return queryIn(r,p.r,0,N);
	}
} vlist[N];
bool vis[N];
int F[N];
bool see[N];
void print(Vertex x)
{
	printf("Value of %d : ", x.id);
	show(x.r,0,N);
	cout << endl;
}
void dij(int s,int t)
{
	Vertex S = {s,zero};
	//print(S);
	priority_queue<Vertex> pq;
	pq.push(S);
	while(!pq.empty()){
		Vertex u  = pq.top(); pq.pop();
		if(vis[u.id]) continue;
		vis[u.id] = 1;
		if(u.id == t) break;

		for(auto a : G[u.id]) {
			int v = a.first, w = a.second;
			if(vis[v]) continue;
			int ho = find(u.r,w);
			int tmp, tmp2;
			
			update(tmp, u.r, 0, N , ho  );
			updateRange(tmp2, tmp, zero, 0, N , w, ho - 1);
			
			Vertex T = {v, tmp2};
			//print(T);
			if(see[v] == 0 ||  vlist[v] < T ) {
				
				vlist[v] = T;
				see[v] = 1;
				F[v] = u.id;
				pq.push(vlist[v]);
				
			}
		}
	}
	

	if(vis[t]) {
		Trv(vlist[t].r, 0, N);
		cout << tot << endl;
		vector<int> ans;
		while(t!= s) {
			ans.pb(t);
			t = F[t];
		}
		ans.pb(s);
		reverse(all(ans));
		printf("%ld\n",ans.size());
		for(auto a: ans ) printf("%d ",a);
		printf("\n");
		
	}

	else printf("-1\n");
	

}
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d %d",&n,&m);
	POW[0] = POWER[0] = 1;
	for(int i = 1; i < N; i ++ ) POW[i] = (POW[i-1] * B) % MOD, POWER[i] = (POWER[i-1] * 2) % MOD;
	for(int i = 0; i < m ; i ++ ) {
		int a,b,x;
		scanf("%d %d %d",&a,&b,&x);
		G[a].pb(mp(b,x));
		G[b].pb(mp(a,x));

	}
	build(zero,0,N);
	int s,t;
	scanf("%d %d",&s,&t);

 	dij(s,t);
	return 0;
}

SPOJ MKTHNUM – K-th Number

Category: Data Structure
Problem Link : MKTHNUM
Solution:
1. Segment tree with vectors
2. Persistent segment tree

First Solution:
For each node of the segment tree, we store a vector. All the numbers of the array in node range is stored in sorted order.So that we can easily count the number of integer in this node has value <= v;

How to build this tree ?

Just like normal segment tree. When we merge the left and right child , We need to merge them in such a way that the parent becomes sorted. This takes O(n) time where n is the number of nodes. C++ has merge function defined which easily merge two vector and sort them into a new vector

Query

We can binary search on the answer to find out answer.
First fix a value x to be a answer. Then count the number of integer = k , then we go left side, otherwise right.

Complexity:
Building Segment Tree = nlogn^2
Query = m logn ^ 3
Memory = n log n

My implementation :

#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define xx                      first
#define yy                      second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))

/*************************** END OF TEMPLATE ****************************/

const int N = 4e5+5;
int n,q;
int a[N];
vector<int>v;
vector<int> seg[N];
void build(int n,int b,int e)
{
	if(b==e){
		seg[n].pb(a[b]);
		return;
	}
	int mid = (b+e)/2;
	build(lc,b,mid);
	build(rc,mid+1,e);
	merge(seg[lc].begin() , seg[lc].end(), seg[rc].begin(), seg[rc].end(),back_inserter(seg[n]));
}

int query(int n,int b,int e,int i,int j,int v)
{
	if(b>j || e< i) return 0;
	if(b>=i && e<= j) {
		int k = upper_bound(all(seg[n]), v ) - seg[n].begin();
		return k;
	}
	int mid = (b+e)/2;
	return query(lc,b,mid,i,j,v) + query(rc,mid+1,e,i,j,v);
}


int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d %d",&n,&q);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%d",&a[i]);
		v.pb(a[i]);
	}
	sort(all(v));
	for(int i = 1;i <= n; i ++ ) {
		a[i] = lower_bound(all(v),a[i]) - v.begin() + 1;
	}

	build(1,1,n);
	
	while(q--) {
		int l,r,x;
		scanf("%d %d %d",&l,&r,&x);
		int low = 1, high = n , mid, ans ;
		while(low <= high) {
			mid = low + high >> 1;
			int k = query(1,1,n,l,r,mid);
			
			if(k >= x) {
				ans = mid;
				high = mid-1;
			}
			else low = mid+1;
		}
		printf("%d\n",v[ans-1]);
	}
	return 0;
}

Second Solution:
Using Persistent Segment Tree.

You can learn this data structure here , here , here

My code without Pointer:

#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define xx                      first
#define yy                      second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))

/*************************** END OF TEMPLATE ****************************/

const int N = 4e5+5;
int n,q;
int a[N],b[N];
int sz;
vector<int>v;
int root[N];
struct Node{
	int ls,rs,cnt;
}node[N*20];
void update(int &n,int pre,int b,int e,int pos)
{
	n = ++sz;
	node[n] = node[pre];
	if(b==e && b== pos) {
		node[n].cnt ++;
		node[n].ls = node[n].rs = 0;
		return;
	}
	int mid = (b+e)/2;
	if(pos<= mid) update(node[n].ls, node[pre].ls, b, mid,pos);
	else update(node[n].rs, node[pre].rs, mid+1,e,pos);
	node[n].cnt = node[node[n].ls].cnt + node[node[n].rs].cnt;
}

int query(int r1,int r2, int b,int e,int x )
{
	if(b==e) return b;
	int oo = node[node[r1].ls].cnt - node[node[r2].ls].cnt;
	int mid = (b+e)/2;
	if(oo >= x) return query(node[r1].ls, node[r2].ls,b, mid,x);
	else return query(node[r1].rs , node[r2].rs, mid+1,e,x - oo );
}
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d %d",&n,&q);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%d",&a[i]);
		v.pb(a[i]);
	}
	sort(all(v));
	for(int i = 1;i <= n; i ++ ) {
		a[i] = lower_bound(all(v),a[i]) - v.begin() + 1;
	}
	int S = v.size();
	update(root[1], 0, 1, S,a[1]); // 0 -> is the initial empty segment tree
	for(int i = 2; i <= n; i ++ ) {
		update(root[i], root[i-1],1,S,a[i]);
	}
	
	while(q--) {
		int l,r,x;
		scanf("%d %d %d",&l,&r,&x);
		int k = query(root[r], root[l-1], 1,S,x);
		printf("%d\n",v[k-1]);
	}
	return 0;
}

Pallindromic Tree Applications

Category: Data Structure, String.

Discussion:
You should read this blog post before you go.

I think you have finished reading this blog and understand basics of Pallindromic Tree.

const int MAXN = 100005; // Length of the String
typedef int T;          //
struct Node{
    int nxt[26]; //In case alphabet is fixed,Change Accordingly
    int len, link;
    T val;
};
struct PalTree{
    Node node[MAXN]; // Node for each pallindrome
    char s[MAXN];   // String
    int go,sz;

    void init()     // Call this Before Any Computation
    {
        node[1].len= -1, node[1].link = 1;
        node[2].len = 0, node[2].link = 1;
        go = sz = 2;
    }

    bool add(int pos)
    {
        int ch = s[pos]-'a';
        int curlen=0,cur = go;
        while(true) {
            curlen = node[cur].len;
            if(pos-1-curlen >= 0 && s[pos-1-curlen] == s[pos]) break;
            cur=node[cur].link;
        }
        if(node[cur].nxt[ch]){
            go = node[cur].nxt[ch];         // Previously occurred Pallindrome, Here may need some computation
            return 0;
        }
        // Adding New Pallindrome
        sz++;
        go = sz;
        node[cur].nxt[ch] = go;
        node[go].len = 2 + node[cur].len;

        if(node[go].len == 1) {
            node[go].link = 2;              // First occurance of a letter, By definition a pallindrome
            return 1;
        }

        while(true) {
            cur = node[cur].link;
            curlen = node[cur].len;
            if(pos-1-curlen >= 0 && s[pos-1-curlen] == s[pos]) {
                node[go].link = node[cur].nxt[ch];
                break;
            }
        }
        node[go].link = node[cur].nxt[ch];  // Giving Suffix Link
                                            // May need some computation
        return 1;

    }
    void clear(){
        for(int i= 0;i <= sz ;i ++) memset(node[i].nxt,0,sizeof(node[i].nxt));
    }
};

Main ideas:

init()

Initialize pallindromic tree.
node[1] -> is a pallindrome of -1 length to accept odd length pallindrome(“a”, “c”, “d” is accepted by this node, in other words single character pallindrome are accepted by this )
node[2] -> is a pallindrome of 0 length to accept even length pallindrome (“aa”, “bb”,”abba” is accepted by this)

add()

add s[pos] to the pallindromic tree
String s is 0 based.
return : Is addition of s[pos] form a new pallindrome different from the previous ly present?
return 1 is yes. 0 otherwise.

clear()

Clears Tree . Needed for multiple testcases

Characteristics of Pallindromic Tree:

# Every Node represents a pallindrome of the string except node[1] and node[2]. They are sentinel
# Every Node has a suffix link to a pallindrome which corespondence to the pallindrome stricly smaller length and suffix of current node.
# Time and space complexity is O(n)

Now we see some applications.

Longest Pallindrome

This problem can be solved using manacher algorithm in O(n). Also solvable by binary search and hashing. But for our pallindromic tree,it is a basic operation, just iterate through all tree node and return the maximum
My code link: longest Pallindromic Substring

How many different Pallindrome

Problem Link: Problem
As the add() function returns whether any distinct pallindrome generated by adding s[pos]. So this is simply the sum of add()
My code Link : How many different Pallindrome

Number of Occurrences of Each Pallindrome

Here the link becomes handy.Each node is storing the information occuring itself.
S = “ababa”
Now for each occurrences of a node, all the node upto root are reachable by using suffix link are also occurred. “ababa” -> “aba”->”a” . All gets updated one by one using topological order.
So we add occurrences of each pallindrome to its suffix link. The nodes are created in topological order. So We just iterate from the end node to root and update suffix links.

Here is Practice Problem : How Many Occurrences
My code: Number of Occurrences of Each Pallindrome

Longest Common Pallindromic Substring

Build one pallindromic tree for each string. Then dfs from root, As the blog post said we have two root, We need to do dfs from each root
Here is a problem harder than discussed task. I think you will be able to understand.
Problem Link : The Problem to Slow Down You
My code: Problem to Slow Down You

ONBRIDGE – Online Bridge Searching

Category : Graph, Bridges
Problem Link : ONBRIDGE

Problem Description: Given a empty undirected graph with n nodes. Then a list of m edges, output the number of bridges in the graph after adding each edge.

Solution:
Normally, We can calculate bridges in a graph in O(n+m). But for each each edge, we can not do the following.In that case complexity will be O(n+m) * m, which is large.
To solve this problem We should know about Biconnected Component(BCC)\

To know about BCC, I can refer https://en.wikipedia.org/wiki/Biconnected_component
But simply, BCC is a collection of nodes, Where there are more than one path from any node to another node.In other words, a bcc doesn’t contain any bridges. They are simply cycles.

Again, What is Connected Components?
Connected Components is a set of nodes, where there is atleast a path from each node to other node.
I think these definition is enough to understand the solution.

Claim: In a undirected graph, A connected components forms a tree where nodes are BCC.(Think ? )

We are going to add edges one by one and calculate the bridges.

Lets add a-b edge:
Three case may occur.

Case 1.

a and b in same BCC. like adding a edge between 2 and 3.
because this two nodes are already in same bcc, this doesn’t add any bridge or reduces # of bridges.

Case 2.

if a and b are in two different connected component.
This edge is a bridge edge because adding this edge decreases the number of connected components.
bridges get increased by 1.
Now we need to merge this two connected components according to their respective size. This ensures O(1) running time.
Let’s see an example:

without loss of generality, Lets assume a is in small connected component. What we need to do is make a as a root of his connected component. This is done going towards its parent ans reversing the link.
Finally Link a to b.

Case 3.

If a and b is in same connected component. So there is a cycle formed in the tree. So we need to traverse the cycle and compress all the nodes in a BCC.

Lets see an example:

So all the tree edges in this components were bridges earlier. So we cancel them out.
This is done by finding the lca then traverse trough all the nodes on the path. Make them in the same bcc.

Here is The solution:

My code :

#include<bits/stdc++.h>
using namespace std;

const int N = 5e4+4;
int n,bridge,m;
int bcc[N],comp[N], link[N],SZ[N];
void init()
{
    for(int i = 0;i < n; i ++ ){
        bcc[i] = comp[i] = i;   // BCC and CC of a node, Initially all are isolate.
        link[i] = -1;           // Link to the parent in a CC
        SZ[i] = 1;              // Size of a CC 
    }
    bridge = 0;
}
// Output the BCC of a node
int getBCC(int a)
{
    if(a==-1)return -1;
    if(bcc[a]==a) return a;
    else return bcc[a] = getBCC(bcc[a]);
}
// Output the root of the component where a is.
int getCOMP(int a)
{
    if(comp[a]==a) return a;
    else return comp[a] = getCOMP(comp[a]);
}
// Merging two path, a->lca, b->lca.
int cs = 0, vis[N];
void MergePath(int a,int b)
{
    cs++;
    a = getBCC(a);
    b = getBCC(b);
    vector<int> va,vb;
    int lca = -1;
    while(1) {
        if(a!=-1) {
            a = getBCC(a);
            va.push_back(a);
            if(vis[a] == cs) {
                lca = a;
                break;
            }
            vis[a] = cs;
            a = link[a];
        }
        if(b!=-1) {
            b = getBCC(b);
            vb.push_back(b);
            if(vis[b]==cs) {
                lca = b;
                break;
            }
            vis[b] = cs;
            b = link[b];
        }
    }
    for(int i = 0;i < va.size();i  ++) {
        bcc[va[i]] = lca;   // Compressing in same BCC
        if(va[i]==lca) break;
        bridge --;
    }
    for(int i = 0;i < vb.size() ; i ++ ) {
        bcc[vb[i]] = lca;   // Compressing in same BCC
        if(vb[i]==lca) break;
        bridge --;
    }

}

// This reverses the edge of a to root of the connected component
void MakeRoot(int a)
{
    int root = a,child = -1;
    while(a!=-1) {
        int p = getBCC(link[a]);
        link[a] = child;
        comp[a] = root;
        child = a;
        a = p;
    }
    SZ[root] = SZ[child];
}


void addEdge(int a,int b)
{
    a = getBCC(a), b= getBCC(b);
    if(a==b) return;   // Case 1

    int u = getCOMP(a), v = getCOMP(b);
    if(u!=v) {      // Case 2
        bridge ++;
        if(SZ[u] > SZ[v]) {
            swap(a,b);
            swap(u,v);
        }
        MakeRoot(a);
        link[a] = comp[a] = b;
        SZ[v] += SZ[a];
    }
    else MergePath(a,b);    // Case 3
}
int main()
{

    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        init();
        for(int i= 0;i < m; i ++ ) {
            int a,b;
            scanf("%d %d",&a,&b);
            addEdge(a,b);
            printf("%d\n",bridge);
        }
    }
    return 0;
}