Data Structure – Live with passion

719

Asif NaeemJanuary 18, 2016

The solution solves the problem within time limit but there are better solutions, by sorting the array using counting sort might give a better timing. There is also a solution without using a suffix array , simply by adding the string with itself and comparing which one is the lowest sub string.

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

int n;
string str;

struct node{
	int fst,ed,idx;
}arr[20005];

int L[30][20005];

bool cmp(node a,node b)
{
	return ( (a.fst==b.fst)?(a.ed<b.ed):(a.fst<b.fst) );
}
void makesa()
{
	int len = str.size();
	int stp=1;
	for(int i=0;i<str.size();i++)
		L[0][i]=str[i]-'a';
	for(int cnt=1;cnt/2<len;cnt<<=1,stp++)
	{
		for(int i=0;i<len;i++)
		{
			arr[i].fst = L[stp-1][i];
			arr[i].ed = (i+cnt)<len?L[stp-1][i+cnt]:-1;
			arr[i].idx = i;
		}
		sort(arr,arr+len,cmp);
		for(int i=0;i<len;i++)
			L[stp][arr[i].idx]= ( (i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i );
	}
}
int main()
{
	scanf("%d",&n);
	string s;
	while(n--)
	{
		cin>>s;
		str=s;
		str.append(s);
		str.append(1u,'~');
		makesa();
		printf("%d\n",arr[0].idx+1);
	}
	return 0;
}

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <algorithm>

using namespace std;

int n;

string str;

struct node{

int fst,ed,idx;

}arr[20005];

int L[30][20005];

bool cmp(node a,node b)

{

return ( (a.fst==b.fst)?(a.ed<b.ed):(a.fst<b.fst) );

}

void makesa()

{

int len = str.size();

int stp=1;

for(int i=0;i<str.size();i++)

L[0][i]=str[i]-'a';

for(int cnt=1;cnt/2<len;cnt<<=1,stp++)

{

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

{

arr[i].fst = L[stp-1][i];

arr[i].ed = (i+cnt)<len?L[stp-1][i+cnt]:-1;

arr[i].idx = i;

}

sort(arr,arr+len,cmp);

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

L[stp][arr[i].idx]= ( (i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i );

}

int main()

{

scanf("%d",&n);

string s;

while(n--)

{

cin>>s;

str=s;

str.append(s);

str.append(1u,'~');

makesa();

printf("%d\n",arr[0].idx+1);

}

return 0;

}

11512

Asif NaeemJanuary 17, 2016

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;
string str;
struct node{
	int fst;
	int ed;
	int idx;
}arr[1010];
int L[17][1010];
int RANK[1010];
int lcp[1010];
int FoundAtIndex;
int cnt;
string resStr;

bool cmp(node a,node b)
{
	return (a.fst==b.fst?(a.ed<b.ed?1:0):(a.fst<b.fst?1:0));
}

void suffixArray()
{
	for(int i=0;i<str.size();i++)
		L[0][i]=str[i]-'A';
	int stp=1;
	for(int cnt=1;cnt/2<str.size();cnt*=2,stp++)
	{
		for(int i=0;i<str.size();i++)
		{
			arr[i].fst=L[stp-1][i];
			arr[i].ed=(i+cnt)<str.size()?L[stp-1][i+cnt]:-1;
			arr[i].idx=i;
		}
		sort(arr,arr+str.size(),cmp);
		for(int i=0;i<str.size();i++)
		{
			L[stp][arr[i].idx]=(i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i;
		}
	}
}

int isLess(string a,string b)
{
	for(int i=0;i<a.size();i++)
	{
		if((a[i]-'0')<(b[i]-'0'))
		return 1;
		if((a[i]-'0')>(b[i]-'0'))
		return -1;
	}
	return 0;
}
int MaxLCP()
{
	for(int i=0;i<str.size();i++)
	{
		lcp[i]=0;
		RANK[arr[i].idx]=i;
	}
	string tmp;
	int k=0,j;
	int len=str.size();
	int mx=0;
	cnt=0;
	for(int i=0;i<len;i++,k?k--:0)
	{
		if(RANK[i]==str.size()-1)
		continue;
		i = arr[RANK[i]].idx;
		j = arr[RANK[i]+1].idx;
		while(i+k<len && j+k<len && str[i+k]==str[j+k])
		k+=1;
		lcp[RANK[i]]=k;
		if(mx<k)
		{
			mx=k;
			FoundAtIndex=i;
			cnt=2;
			resStr="";
			for(int l=i;l<i+k;l++)
			resStr.append(1u,str[l]);
		}
		else if(mx==k)
		{
			tmp="";
			for(int l=i;l<i+k;l++)
			tmp.append(1u,str[l]);
			int f=isLess(tmp,resStr);
			if(f==1)
			{
				resStr=tmp;
				cnt=2;
			}
			else if(f==0)
			cnt+=1;
		}

	}
	return mx;
}
int main()
{
	int n,mxLength;
	scanf("%d",&n);
	while(n--)
	{
		cin>>str;
		suffixArray();
		mxLength = MaxLCP();
		if(mxLength==0)
		{
			printf("No repetitions found!\n");
		}
		else
		{
			cout<<resStr<<" "<<cnt<<"\n";
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

#include <algorithm>

#include <cstring>

using namespace std;

string str;

struct node{

int fst;

int ed;

int idx;

}arr[1010];

int L[17][1010];

int RANK[1010];

int lcp[1010];

int FoundAtIndex;

int cnt;

string resStr;

bool cmp(node a,node b)

{

return (a.fst==b.fst?(a.ed<b.ed?1:0):(a.fst<b.fst?1:0));

}

void suffixArray()

{

for(int i=0;i<str.size();i++)

L[0][i]=str[i]-'A';

int stp=1;

for(int cnt=1;cnt/2<str.size();cnt*=2,stp++)

{

for(int i=0;i<str.size();i++)

{

arr[i].fst=L[stp-1][i];

arr[i].ed=(i+cnt)<str.size()?L[stp-1][i+cnt]:-1;

arr[i].idx=i;

}

sort(arr,arr+str.size(),cmp);

for(int i=0;i<str.size();i++)

{

L[stp][arr[i].idx]=(i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i;

}

int isLess(string a,string b)

{

for(int i=0;i<a.size();i++)

{

if((a[i]-'0')<(b[i]-'0'))

return 1;

if((a[i]-'0')>(b[i]-'0'))

return -1;

}

return 0;

}

int MaxLCP()

{

for(int i=0;i<str.size();i++)

{

lcp[i]=0;

RANK[arr[i].idx]=i;

}

string tmp;

int k=0,j;

int len=str.size();

int mx=0;

cnt=0;

for(int i=0;i<len;i++,k?k--:0)

{

if(RANK[i]==str.size()-1)

continue;

i = arr[RANK[i]].idx;

j = arr[RANK[i]+1].idx;

while(i+k<len && j+k<len && str[i+k]==str[j+k])

k+=1;

lcp[RANK[i]]=k;

if(mx<k)

{

mx=k;

FoundAtIndex=i;

cnt=2;

resStr="";

for(int l=i;l<i+k;l++)

resStr.append(1u,str[l]);

}

else if(mx==k)

{

tmp="";

for(int l=i;l<i+k;l++)

tmp.append(1u,str[l]);

int f=isLess(tmp,resStr);

if(f==1)

{

resStr=tmp;

cnt=2;

}

else if(f==0)

cnt+=1;

}

return mx;

}

int main()

{

int n,mxLength;

scanf("%d",&n);

while(n--)

{

cin>>str;

suffixArray();

mxLength = MaxLCP();

if(mxLength==0)

{

printf("No repetitions found!\n");

}

else

{

cout<<resStr<<" "<<cnt<<"\n";

}

return 0;

}

10298

Asif NaeemDecember 31, 2015

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;

int lps[1000005];

void prefixArray(string s)
{
	memset(lps,0,sizeof(lps));
	int len=0;//length of prev longest prefix
	int i=1;
	lps[0]=0;
	int length = s.size();
	while(i<length)
	{
		if(s[i]==s[len])
		{
			len+=1;
			lps[i]=len;
			i+=1;
		}
		else
		{
			if(len!=0)
			{
				len = lps[len-1];
			}
			else
			{
				lps[i]=0;
				i+=1;
			}
		}
	}
}
int main()
{
	string s;
	int lastval,minimal_length_of_repeated_string;
	while(cin>>s)
	{
		if(s==".")
		break;
		prefixArray(s);
		lastval = lps[s.size()-1];
		minimal_length_of_repeated_string = s.size()-lastval;
		if(s.size()%minimal_length_of_repeated_string==0)
		printf("%d\n",s.size()/minimal_length_of_repeated_string);
		else
		printf("1\n");
	}
	return 0;
}

#include <iostream>

#include <cstring>

#include <cstdio>

#include <string>

using namespace std;

int lps[1000005];

void prefixArray(string s)

{

memset(lps,0,sizeof(lps));

int len=0;//length of prev longest prefix

int i=1;

lps[0]=0;

int length = s.size();

while(i<length)

{

if(s[i]==s[len])

{

len+=1;

lps[i]=len;

i+=1;

}

else

{

if(len!=0)

{

len = lps[len-1];

}

else

{

lps[i]=0;

i+=1;

}

int main()

{

string s;

int lastval,minimal_length_of_repeated_string;

while(cin>>s)

{

if(s==".")

break;

prefixArray(s);

lastval = lps[s.size()-1];

minimal_length_of_repeated_string = s.size()-lastval;

if(s.size()%minimal_length_of_repeated_string==0)

printf("%d\n",s.size()/minimal_length_of_repeated_string);

else

printf("1\n");

}

return 0;

}

615

Asif NaeemOctober 23, 2015

The problem is to finding a tree from a given graph.The main challenge is that the value of the node is not provided. So adjacency matrix can not be used to solve the problem. To define a tree for a directed graph : total edges = total vertices -1;root can not be more than one,

Continue Reading “615” →

11610

Asif NaeemOctober 19, 2015

To solve the problem indexes of the array are also needed to be updated and queried.

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

struct RevPrime{
	int reversePrime;
	int factorCount;
};

int prime[1000001];
RevPrime arr[80000];
int Bit[2][80000];

vector<int> vb;
int k=1;

int reverse(int a)
{
	int num=0;
	while(a)
	{
		num*=10;
		num += (a%10);
		a/=10;
	}
	return num;
}

bool cmp(RevPrime a,RevPrime b)
{
	return a.reversePrime<b.reversePrime;
}

void update(int row,int idx,int val)
{
	while(idx<k)
	{
		Bit[row][idx]+=val;
		idx +=(idx & (-idx));
	}
}

int query(int row,int idx)
{
	int ret=0;
	while(idx>0)
	{
		ret+=Bit[row][idx];
		idx -= (idx & (-idx));
	}
	return ret;
}

int binarySearch(int lw,int hi,int val)
{
	if(hi<lw)
		return 0;
	int mid = (hi+lw)>>1;
	if(arr[mid].reversePrime<val)
	{
		return binarySearch(mid+1,hi,val);
	}
	else if(arr[mid].reversePrime>val)
	{
		return binarySearch(lw,mid,val);
	}
	else if(arr[mid].reversePrime==val)
		return mid;
	return 0;
}

int findIndex_bianarySearch(int lw,int hi,int modifiedIndex_value)
{
	if(hi<lw)
		return 0;
	int mid =(hi+lw)>>1;
	int mid_val=query(1,mid);
	if(mid_val<modifiedIndex_value)
		return findIndex_bianarySearch(mid+1,hi,modifiedIndex_value);
	else if(mid_val>modifiedIndex_value)
		return findIndex_bianarySearch(lw,mid,modifiedIndex_value);
	else
		return mid;
	return 0;
}

int main () {
    int b;
	int tmp;
    for(int i=2;i<1000001;i++)
    {
    	if(prime[i]==0)
    	{
    		prime[i]+=1;
    		vb.push_back(i);
    		for(int j=i+i;j<1000001;j+=i)
    		{
    			prime[j]+=1;
    			tmp=j/i;
    			while(tmp%i==0)
    			{
    				prime[j]+=1;
    				tmp/=i;
    			}
    		}
    	}
    }
    for(int i=0;i<vb.size();i++)
    {
    	b = reverse(vb[i]);
    	arr[k].factorCount=prime[b];
    	while(b<1000000)
    	{
    		b*=10;
    		arr[k].factorCount+=2;
    	}
    	arr[k].reversePrime=b;
    	k+=1;
    }
    sort(arr,arr+k,cmp);
    for(int i=1;i<k;i++)
    {
		update(0,i,arr[i].factorCount);
		update(1,i,1);
	}
    char ch;
    int n;
    while(scanf("%c", &ch)!=EOF)
    {
    	scanf("%d",&n);
    	if(ch=='q')
    	{
			int original_index=findIndex_bianarySearch(1,k,n+1);
    		cout<<query(0,original_index)<<"\n";
    	}
    	if(ch=='d')
    	{
    		int idx = binarySearch(1,k,n);
    		update(0,idx,(-1)*arr[idx].factorCount);
			update(1,idx,-1);

    	}
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

struct RevPrime{

int reversePrime;

int factorCount;

};

int prime[1000001];

RevPrime arr[80000];

int Bit[2][80000];

vector<int> vb;

int k=1;

int reverse(int a)

{

int num=0;

while(a)

{

num*=10;

num += (a%10);

a/=10;

}

return num;

}

bool cmp(RevPrime a,RevPrime b)

{

return a.reversePrime<b.reversePrime;

}

void update(int row,int idx,int val)

{

while(idx<k)

{

Bit[row][idx]+=val;

idx +=(idx & (-idx));

}

int query(int row,int idx)

{

int ret=0;

while(idx>0)

{

ret+=Bit[row][idx];

idx -= (idx & (-idx));

}

return ret;

}

int binarySearch(int lw,int hi,int val)

{

if(hi<lw)

return 0;

int mid = (hi+lw)>>1;

if(arr[mid].reversePrime<val)

{

return binarySearch(mid+1,hi,val);

}

else if(arr[mid].reversePrime>val)

{

return binarySearch(lw,mid,val);

}

else if(arr[mid].reversePrime==val)

return mid;

return 0;

}

int findIndex_bianarySearch(int lw,int hi,int modifiedIndex_value)

{

if(hi<lw)

return 0;

int mid =(hi+lw)>>1;

int mid_val=query(1,mid);

if(mid_val<modifiedIndex_value)

return findIndex_bianarySearch(mid+1,hi,modifiedIndex_value);

else if(mid_val>modifiedIndex_value)

return findIndex_bianarySearch(lw,mid,modifiedIndex_value);

else

return mid;

return 0;

}

int main () {

int b;

int tmp;

for(int i=2;i<1000001;i++)

{

if(prime[i]==0)

{

prime[i]+=1;

vb.push_back(i);

for(int j=i+i;j<1000001;j+=i)

{

prime[j]+=1;

tmp=j/i;

while(tmp%i==0)

{

prime[j]+=1;

tmp/=i;

}

for(int i=0;i<vb.size();i++)

{

b = reverse(vb[i]);

arr[k].factorCount=prime[b];

while(b<1000000)

{

b*=10;

arr[k].factorCount+=2;

}

arr[k].reversePrime=b;

k+=1;

}

sort(arr,arr+k,cmp);

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

{

update(0,i,arr[i].factorCount);

update(1,i,1);

}

char ch;

int n;

while(scanf("%c", &ch)!=EOF)

{

scanf("%d",&n);

if(ch=='q')

{

int original_index=findIndex_bianarySearch(1,k,n+1);

cout<<query(0,original_index)<<"\n";

}

if(ch=='d')

{

int idx = binarySearch(1,k,n);

update(0,idx,(-1)*arr[idx].factorCount);

update(1,idx,-1);

}

return 0;

}

10666

Asif NaeemOctober 18, 2015

#include <iostream>
#include <cstdio>

using namespace std;
//no of 1' indicate how many times at least it lost a game
//no of 0' indicate how many times at least it lost a game
//so if a team id does not contain a 0 it can be the last of the tournament at it pessimist decision
int NoOfRounds;
int TeamNo;
int TwosPower[31];

int main()
{
	int t;
	int countOne;
	int countZero;
	scanf("%d",&t);
	TwosPower[0]=1;
	for(int i=1;i<31;i++)
		TwosPower[i]=TwosPower[i-1]<<1;
	while(t--)
	{
		scanf("%d%d",&NoOfRounds,&TeamNo);
		int tmp = TeamNo;
		countOne=0;
		while(tmp)
		{
			if(tmp%2)
			countOne+=1;
			tmp = tmp>>1;
		}
		//to find the worst case : after the first lost rest of the game can be considered as lost
		//so find the the first lost=first 1 from the left
		//from this we can find least number of winning match
		//subtract this from total number of matches of that tournaments.
		//each zero from the left means the team is better than the rest of the players of that round.
		tmp = TeamNo;
		countZero=0;
		int i=0;
		while(i<NoOfRounds)
		{
			if(tmp%2)
			break;
			else
			countZero+=TwosPower[i++];
			tmp=tmp>>1;
		}
		printf("%d %d\n",countOne+1,TwosPower[NoOfRounds]-countZero);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

//no of 1' indicate how many times at least it lost a game

//no of 0' indicate how many times at least it lost a game

//so if a team id does not contain a 0 it can be the last of the tournament at it pessimist decision

int NoOfRounds;

int TeamNo;

int TwosPower[31];

int main()

{

int t;

int countOne;

int countZero;

scanf("%d",&t);

TwosPower[0]=1;

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

TwosPower[i]=TwosPower[i-1]<<1;

while(t--)

{

scanf("%d%d",&NoOfRounds,&TeamNo);

int tmp = TeamNo;

countOne=0;

while(tmp)

{

if(tmp%2)

countOne+=1;

tmp = tmp>>1;

}

//to find the worst case : after the first lost rest of the game can be considered as lost

//so find the the first lost=first 1 from the left

//from this we can find least number of winning match

//subtract this from total number of matches of that tournaments.

//each zero from the left means the team is better than the rest of the players of that round.

tmp = TeamNo;

countZero=0;

int i=0;

while(i<NoOfRounds)

{

if(tmp%2)

break;

else

countZero+=TwosPower[i++];

tmp=tmp>>1;

}

printf("%d %d\n",countOne+1,TwosPower[NoOfRounds]-countZero);

}

return 0;

}

1428

Asif NaeemOctober 17, 2015

The problem can be solved using Binary Indexed tree or Fenwick tree.

#include <cstdio>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>

#define SZ 100000+5
#define ll long long

using namespace std;

int arr[SZ];
ll Left[SZ],Right[SZ],sum[SZ];
int mx;

ll Cumulative(int idx)
{
	ll value=0;
	while(idx>0)
	{
		value += sum[idx];
		idx -= (idx & (-idx));
	}
	return value;
}

void update(int idx)
{
	while(idx<=mx)
	{
		sum[idx]+=1;
		idx += (idx & (-idx));
	}
}
int main()
{
	int t,N;
	ll ans;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&N);
		mx=-1;
		for(int i=1;i<=N;i++)
		{
			scanf("%d",&arr[i]);
			if(mx<arr[i])
			mx=arr[i];
		}
		memset(Left,0,sizeof(Left));
		memset(Right,0,sizeof(Right));
		memset(sum,0,sizeof(sum));

		for(int i=1;i<=N;i++)
		{
			Left[i]=Cumulative(arr[i]);//finds the number of smaller number than arr[i] to its Left
			update(arr[i]);
		}
		memset(sum,0,sizeof(sum));
		for(int i=N;i>=1;i--)
		{
			Right[i]=Cumulative(arr[i]);
			update(arr[i]);
			//ans += Left[i]*(N-)
		}
		ans = 0;
		for(int i=N;i>=1;i--)
		{
			ans += Left[i]*(N-i-Right[i]) + Right[i]*(i-1-Left[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <string>

#define SZ 100000+5

#define ll long long

using namespace std;

int arr[SZ];

ll Left[SZ],Right[SZ],sum[SZ];

int mx;

ll Cumulative(int idx)

{

ll value=0;

while(idx>0)

{

value += sum[idx];

idx -= (idx & (-idx));

}

return value;

}

void update(int idx)

{

while(idx<=mx)

{

sum[idx]+=1;

idx += (idx & (-idx));

}

int main()

{

int t,N;

ll ans;

scanf("%d",&t);

while(t--)

{

scanf("%d",&N);

mx=-1;

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

{

scanf("%d",&arr[i]);

if(mx<arr[i])

mx=arr[i];

}

memset(Left,0,sizeof(Left));

memset(Right,0,sizeof(Right));

memset(sum,0,sizeof(sum));

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

{

Left[i]=Cumulative(arr[i]);//finds the number of smaller number than arr[i] to its Left

update(arr[i]);

}

memset(sum,0,sizeof(sum));

for(int i=N;i>=1;i--)

{

Right[i]=Cumulative(arr[i]);

update(arr[i]);

//ans += Left[i]*(N-)

}

ans = 0;

for(int i=N;i>=1;i--)

{

ans += Left[i]*(N-i-Right[i]) + Right[i]*(i-1-Left[i]);

}

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

}

return 0;

}

To know something More. From the above source:

Let's take the first example - 3, 1, 2. At the beginning the BIT is 0, 0, 0. After inserting 3 the BIT is 0, 0, 1. After inserting 1 the BIT is 1, 0, 1 which gives 1 inversion. After inserting 2, the BIT is 1, 1, 1 which gives again 1 inversion. 1 + 1 = 2 total inversions.

Let's take the second example - 2, 3, 8, 6, 1.
BIT - 0, 0, 0, 0, 0, 0, 0, 0. Insert 2:
BIT - 0, 1, 0, 0, 0, 0, 0, 0. Insert 3:
BIT - 0, 1, 1, 0, 0, 0, 0, 0. Insert 8:
BIT - 0, 1, 1, 0, 0, 0, 0, 1. Insert 6: +1 inversions
BIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversions
BIT - 1, 1, 1, 0, 0, 1, 0, 1.

P.S. In the examples I haven't included the compression for clarity.

Let's take the first example - 3, 1, 2. At the beginning the BIT is 0, 0, 0. After inserting 3 the BIT is 0, 0, 1. After inserting 1 the BIT is 1, 0, 1 which gives 1 inversion. After inserting 2, the BIT is 1, 1, 1 which gives again 1 inversion. 1 + 1 = 2 total inversions.

Let's take the second example - 2, 3, 8, 6, 1.

BIT - 0, 0, 0, 0, 0, 0, 0, 0. Insert 2:

BIT - 0, 1, 0, 0, 0, 0, 0, 0. Insert 3:

BIT - 0, 1, 1, 0, 0, 0, 0, 0. Insert 8:

BIT - 0, 1, 1, 0, 0, 0, 0, 1. Insert 6: +1 inversions

BIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversions

BIT - 1, 1, 1, 0, 0, 1, 0, 1.

P.S. In the examples I haven't included the compression for clarity.

Sample code implementing the binary indexed tree data structure to find the # of smaller numbers than a number of an array.

#include<iostream>

using namespace std;

int ftree[10000001]={0};

int cum(int idx){
	int result=0;
	while(idx>0){
		result=result+ftree[idx];
		idx=idx-(idx & -idx);
	}

	return result;
}

void update(int idx,int val){
	while(idx<=10000000){
		ftree[idx]=ftree[idx]+val;
		idx=idx+(idx & -idx);
	}
}

int main()
{
	int t;
	cin>>t;
	for(int w=0;w<t;w++){
		int n;
		cin>>n;
		int ele;
		long int count=0;
		for(int i=0;i<n;i++){
			cin>>ele;
			update(ele,1);
			count=count+cum(10000000)-cum(ele);
		}
		cout<<count<<"\n";
		for(int i=1;i<=10000000;i++)
			ftree[i]=0;
	}
	return 0;
}

#include<iostream>

using namespace std;

int ftree[10000001]={0};

int cum(int idx){

int result=0;

while(idx>0){

result=result+ftree[idx];

idx=idx-(idx & -idx);

}

return result;

}

void update(int idx,int val){

while(idx<=10000000){

ftree[idx]=ftree[idx]+val;

idx=idx+(idx & -idx);

}

int main()

{

int t;

cin>>t;

for(int w=0;w<t;w++){

int n;

cin>>n;

int ele;

long int count=0;

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

cin>>ele;

update(ele,1);

count=count+cum(10000000)-cum(ele);

}

cout<<count<<"\n";

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

ftree[i]=0;

}

return 0;

}

11402

Asif NaeemSeptember 12, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

#define sz 1024001
#define INV 1
#define SET 2
#define RESET 3

using namespace std;

struct segment{
	int pending_op_typ;
	int sum;

	int left,right;
	int len;
};
segment tree[sz*4];
string ss;

void init(int node,int b,int e)
{
	tree[node].len = e-b+1;
	tree[node].left=b;
	tree[node].right=e;
	tree[node].pending_op_typ=0;
	if(b==e)
	{

		if(ss[b]=='1')
		tree[node].sum=1;
		else
		tree[node].sum=0;
		return;
	}
	int Left = node*2;
	int Right = (node<<1)|1;
	int mid = (b+e)>>1;
	init(Left,b,mid);
	init(Right,mid+1,e);
	tree[node].sum=tree[Left].sum+tree[Right].sum;
}

void change(int node,int opr)
{
	if(opr==SET)
	{
		tree[node].sum=tree[node].len;
		tree[node].pending_op_typ=opr;
	}
	else if(opr==RESET)
	{
		tree[node].sum=0;
		tree[node].pending_op_typ=opr;
	}
	else if(opr==INV)
	{
		tree[node].sum=tree[node].len-tree[node].sum;
		if(tree[node].pending_op_typ==SET)//inverse the operation and apply
		{
			tree[node].pending_op_typ=RESET;
		}
		else if(tree[node].pending_op_typ==RESET)//inverse the operation and apply
		{
			tree[node].pending_op_typ=SET;
		}
		else if(tree[node].pending_op_typ==INV)//inverse the operation and apply
		{
			tree[node].pending_op_typ=0;
		}
		else if(tree[node].pending_op_typ==0)//inverse the operation and apply
		{
			tree[node].pending_op_typ=INV;
		}
	}

}

void propagate(int node)
{
	if(tree[node].pending_op_typ==0)
	return;
	int Left=2*node;
	int Right=2*node+1;
	change(Left,tree[node].pending_op_typ);
	change(Right,tree[node].pending_op_typ);
	tree[node].pending_op_typ=0;
}

int query(int node,int i,int j)
{
	int b=tree[node].left;
	int e=tree[node].right;
	if(i>e || j<b)
	return 0;
	propagate(node);
	if(i<=b && j>=e)
	{
		return tree[node].sum;
	}
	else
	{
		int Left = node<<1;
		int Right = (node<<1)|1;
		int p1 = query(Left,i,j);
		int p2 = query(Right,i,j);
		return p1+p2;
	}
}


void update(int node,int i,int j,int opr)
{
	int left = tree[node].left,right=tree[node].right;
	propagate(node);
	if(i>right || j<left)
	return;
	if(left>=i && right<=j)
	{
		change(node,opr);
		return;
	}
	else
	{
		int Left = node*2;
		int Right = node*2+1;
		update(Left,i,j,opr);
		update(Right,i,j,opr);
		tree[node].sum=tree[Left].sum+tree[Right].sum;
	}
}
// 0 for Barbary, 1 for Buccaneer
int main()
{
	int t,tym,M,qry;
	int a,b;
	int kase=1,cnt;
	bool flag;
	string s,str;
	scanf("%d",&t);

	while(t--)
	{
		flag=0;
		cnt=1;
		scanf("%d",&tym);
		s="";
		while(tym--)
		{
			scanf("%d",&M);
			cin>>str;
			while(M--)
				s.append(str);
		}
		ss = "2";
		ss.append(s);
		init(1,1,ss.size()-1);//init(1,1,ss.size()-1);
		scanf("%d",&qry);
		while(qry--)
		{
			cin>>str;
			scanf("%d%d",&a,&b);
			if(str=="F")
			{
				update(1,a+1,b+1,SET);//convert to buccaneer
			}
			else if(str=="E")
			{
				update(1,a+1,b+1,RESET);//convert to barbary =0
			}
			else if(str=="I")
			{
				update(1,a+1,b+1,INV);//inverse the pirates
			}
			else if(str=="S")
			{
				if(flag==0)
				{
					cout<<"Case "<<kase++<<":\n";
				}
				flag=1;
				cout<<"Q"<<cnt++<<": ";
				cout<<query(1,a+1,b+1)<<"\n";
			}
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#define sz 1024001

#define INV 1

#define SET 2

#define RESET 3

using namespace std;

struct segment{

int pending_op_typ;

int sum;

int left,right;

int len;

};

segment tree[sz*4];

string ss;

void init(int node,int b,int e)

{

tree[node].len = e-b+1;

tree[node].left=b;

tree[node].right=e;

tree[node].pending_op_typ=0;

if(b==e)

{

if(ss[b]=='1')

tree[node].sum=1;

else

tree[node].sum=0;

return;

}

int Left = node*2;

int Right = (node<<1)|1;

int mid = (b+e)>>1;

init(Left,b,mid);

init(Right,mid+1,e);

tree[node].sum=tree[Left].sum+tree[Right].sum;

}

void change(int node,int opr)

{

if(opr==SET)

{

tree[node].sum=tree[node].len;

tree[node].pending_op_typ=opr;

}

else if(opr==RESET)

{

tree[node].sum=0;

tree[node].pending_op_typ=opr;

}

else if(opr==INV)

{

tree[node].sum=tree[node].len-tree[node].sum;

if(tree[node].pending_op_typ==SET)//inverse the operation and apply

{

tree[node].pending_op_typ=RESET;

}

else if(tree[node].pending_op_typ==RESET)//inverse the operation and apply

{

tree[node].pending_op_typ=SET;

}

else if(tree[node].pending_op_typ==INV)//inverse the operation and apply

{

tree[node].pending_op_typ=0;

}

else if(tree[node].pending_op_typ==0)//inverse the operation and apply

{

tree[node].pending_op_typ=INV;

}

void propagate(int node)

{

if(tree[node].pending_op_typ==0)

return;

int Left=2*node;

int Right=2*node+1;

change(Left,tree[node].pending_op_typ);

change(Right,tree[node].pending_op_typ);

tree[node].pending_op_typ=0;

}

int query(int node,int i,int j)

{

int b=tree[node].left;

int e=tree[node].right;

if(i>e || j<b)

return 0;

propagate(node);

if(i<=b && j>=e)

{

return tree[node].sum;

}

else

{

int Left = node<<1;

int Right = (node<<1)|1;

int p1 = query(Left,i,j);

int p2 = query(Right,i,j);

return p1+p2;

}

void update(int node,int i,int j,int opr)

{

int left = tree[node].left,right=tree[node].right;

propagate(node);

if(i>right || j<left)

return;

if(left>=i && right<=j)

{

change(node,opr);

return;

}

else

{

int Left = node*2;

int Right = node*2+1;

update(Left,i,j,opr);

update(Right,i,j,opr);

tree[node].sum=tree[Left].sum+tree[Right].sum;

}

// 0 for Barbary, 1 for Buccaneer

int main()

{

int t,tym,M,qry;

int a,b;

int kase=1,cnt;

bool flag;

string s,str;

scanf("%d",&t);

while(t--)

{

flag=0;

cnt=1;

scanf("%d",&tym);

s="";

while(tym--)

{

scanf("%d",&M);

cin>>str;

while(M--)

s.append(str);

}

ss = "2";

ss.append(s);

init(1,1,ss.size()-1);//init(1,1,ss.size()-1);

scanf("%d",&qry);

while(qry--)

{

cin>>str;

scanf("%d%d",&a,&b);

if(str=="F")

{

update(1,a+1,b+1,SET);//convert to buccaneer

}

else if(str=="E")

{

update(1,a+1,b+1,RESET);//convert to barbary =0

}

else if(str=="I")

{

update(1,a+1,b+1,INV);//inverse the pirates

}

else if(str=="S")

{

if(flag==0)

{

cout<<"Case "<<kase++<<":\n";

}

flag=1;

cout<<"Q"<<cnt++<<": ";

cout<<query(1,a+1,b+1)<<"\n";

}

return 0;

}

12436

Asif NaeemSeptember 10, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define ll long long
#define sz 250005

using namespace std;

struct segment{
	ll left,right;
	ll len;

	ll first_inc,last_inc;
	ll totalAB;

	bool isSetvalue;
	ll cary;
	ll sum;

};

segment arr[sz*4];


void changeAB(ll frist_incr,ll last_incr,int node,ll step)
{
	arr[node].totalAB += step;
	arr[node].first_inc += frist_incr;
	arr[node].last_inc += last_incr;
	arr[node].sum += ((frist_incr+last_incr)*arr[node].len)/2;
}

void changeC(int node,ll val)
{
	arr[node].sum = arr[node].len*val;
	arr[node].isSetvalue=1;
	arr[node].cary=val;

	arr[node].totalAB=0;
	arr[node].first_inc=0;
	arr[node].last_inc=0;
}

void propagate(int node)
{
	ll add1 = arr[node].first_inc;
	ll add2 = arr[node].last_inc;
	ll step = arr[node].totalAB;

	if(arr[node].isSetvalue)
	{
		ll Left=2*node;
		ll Right=2*node+1;
		changeC(Left,arr[node].cary);
		changeC(Right,arr[node].cary);
		arr[node].isSetvalue=0;
		arr[node].cary=0;
	}
	if(add1 || add2 || step)
	{
		ll Left=2*node;
		ll Right=2*node+1;
		ll mid=add1+step*(arr[Left].len-1);
		changeAB(add1,mid,Left,step);
		changeAB(mid+step,add2,Right,step);

		arr[node].first_inc=0;
		arr[node].last_inc=0;
		arr[node].totalAB=0;
	}

}

//update node for the range
void updateAB(int node,int i,int j,ll step)
{
	ll Left=arr[node].left,Right=arr[node].right,mid;
	ll first_inc,last_inc;
	if(i>Right || j<Left)
	{
		return;
	}
	if(i<=Left && j>=Right)
	{
		ll k = step;
		if(step>=0)
		{
			first_inc = (Left-i+1);
			last_inc  = (Right-i+1);
		}
		else
		{
			first_inc = (j-Left+1);
			last_inc  = (j-Right+1);
		}
		changeAB(first_inc,last_inc,node,k);
		return;
	}
	else
	{
		propagate(node);
		Left=2*node;
		Right=(node<<1) | 1;
		updateAB(Left, i, j,step);
		updateAB(Right, i, j,step);
		arr[node].sum = arr[Left].sum+arr[Right].sum;
		return;
	}
	return;
}

void updateC(int node,int i,int j,ll val)
{
	ll Left,Right,mid;
	ll b=arr[node].left;
	ll e=arr[node].right;
	if(i>e || j<b)
	return;
	else if(i<=b && j>=e)
	{
		arr[node].sum = (val*(e-b+1));
		arr[node].cary=val;
		arr[node].isSetvalue=1;

		arr[node].totalAB=0;
		arr[node].first_inc=0;
		arr[node].last_inc=0;
		return;
	}
	else
	{
		propagate(node);
		Left = 2*node;
		Right = Left+1;
		mid = (b+e)>>1;
		updateC(Left,i,j,val);
		updateC(Right,i,j,val);
		arr[node].sum = (arr[Left].sum+arr[Right].sum);
		return;
	}
	return;
}

ll query(int node,int i,int j)
{
	ll b = arr[node].left;
	ll e = arr[node].right;

	if(i>e || j<b)
	{
		return 0;
	}
	if(i<=b && j>=e)
	{
		return arr[node].sum;
	}
	propagate(node);
	ll Left = node<<1;
	ll Right = Left+1;

	ll p1 = query(Left, i, j);
	ll p2 = query(Right, i, j);
	return p1+p2;
}


void _init(int b,int e,int node)
{
	arr[node].sum=0; arr[node].len=e-b+1;
	arr[node].totalAB=0;
	arr[node].cary=0;
	arr[node].first_inc=0; arr[node].last_inc=0;
	arr[node].isSetvalue=0;
	arr[node].left=b;arr[node].right=e;
	if(b!=e)
	{
		int mid=(b+e)/2;
		_init(b,mid,node<<1);
		_init(mid+1,e,(node<<1)|1);
	}
}
int main()
{
	int t;
	string s;
	int start,end,val;

	while(scanf("%d",&t)!=EOF)
	{
		_init(1,sz-5,1);
		while(t--)
		{
			cin>>s;
			if(s[0]=='A')
			{
				cin>>start>>end;
				updateAB(1,start,end,1);//+1 increment increasing ascending order
			}
			else if(s[0]=='B')
			{
				cin>>start>>end;
				updateAB(1,start,end,-1);//-1 increment decreasing ascending order
			}
			else if(s[0]=='C')
			{
				cin>>start>>end>>val;
				updateC(1,start,end,val);
			}
			else if(s[0]=='S')
			{
				cin>>start>>end;
				cout<<query(1,start,end)<<"\n";
			}
		}
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <vector>

#define ll long long

#define sz 250005

using namespace std;

struct segment{

ll left,right;

ll len;

ll first_inc,last_inc;

ll totalAB;

bool isSetvalue;

ll cary;

ll sum;

};

segment arr[sz*4];

void changeAB(ll frist_incr,ll last_incr,int node,ll step)

{

arr[node].totalAB += step;

arr[node].first_inc += frist_incr;

arr[node].last_inc += last_incr;

arr[node].sum += ((frist_incr+last_incr)*arr[node].len)/2;

}

void changeC(int node,ll val)

{

arr[node].sum = arr[node].len*val;

arr[node].isSetvalue=1;

arr[node].cary=val;

arr[node].totalAB=0;

arr[node].first_inc=0;

arr[node].last_inc=0;

}

void propagate(int node)

{

ll add1 = arr[node].first_inc;

ll add2 = arr[node].last_inc;

ll step = arr[node].totalAB;

if(arr[node].isSetvalue)

{

ll Left=2*node;

ll Right=2*node+1;

changeC(Left,arr[node].cary);

changeC(Right,arr[node].cary);

arr[node].isSetvalue=0;

arr[node].cary=0;

}

if(add1 || add2 || step)

{

ll Left=2*node;

ll Right=2*node+1;

ll mid=add1+step*(arr[Left].len-1);

changeAB(add1,mid,Left,step);

changeAB(mid+step,add2,Right,step);

arr[node].first_inc=0;

arr[node].last_inc=0;

arr[node].totalAB=0;

}

//update node for the range

void updateAB(int node,int i,int j,ll step)

{

ll Left=arr[node].left,Right=arr[node].right,mid;

ll first_inc,last_inc;

if(i>Right || j<Left)

{

return;

}

if(i<=Left && j>=Right)

{

ll k = step;

if(step>=0)

{

first_inc = (Left-i+1);

last_inc = (Right-i+1);

}

else

{

first_inc = (j-Left+1);

last_inc = (j-Right+1);

}

changeAB(first_inc,last_inc,node,k);

return;

}

else

{

propagate(node);

Left=2*node;

Right=(node<<1) | 1;

updateAB(Left, i, j,step);

updateAB(Right, i, j,step);

arr[node].sum = arr[Left].sum+arr[Right].sum;

return;

}

return;

}

void updateC(int node,int i,int j,ll val)

{

ll Left,Right,mid;

ll b=arr[node].left;

ll e=arr[node].right;

if(i>e || j<b)

return;

else if(i<=b && j>=e)

{

arr[node].sum = (val*(e-b+1));

arr[node].cary=val;

arr[node].isSetvalue=1;

arr[node].totalAB=0;

arr[node].first_inc=0;

arr[node].last_inc=0;

return;

}

else

{

propagate(node);

Left = 2*node;

Right = Left+1;

mid = (b+e)>>1;

updateC(Left,i,j,val);

updateC(Right,i,j,val);

arr[node].sum = (arr[Left].sum+arr[Right].sum);

return;

}

return;

}

ll query(int node,int i,int j)

{

ll b = arr[node].left;

ll e = arr[node].right;

if(i>e || j<b)

{

return 0;

}

if(i<=b && j>=e)

{

return arr[node].sum;

}

propagate(node);

ll Left = node<<1;

ll Right = Left+1;

ll p1 = query(Left, i, j);

ll p2 = query(Right, i, j);

return p1+p2;

}

void _init(int b,int e,int node)

{

arr[node].sum=0; arr[node].len=e-b+1;

arr[node].totalAB=0;

arr[node].cary=0;

arr[node].first_inc=0; arr[node].last_inc=0;

arr[node].isSetvalue=0;

arr[node].left=b;arr[node].right=e;

if(b!=e)

{

int mid=(b+e)/2;

_init(b,mid,node<<1);

_init(mid+1,e,(node<<1)|1);

}

int main()

{

int t;

string s;

int start,end,val;

while(scanf("%d",&t)!=EOF)

{

_init(1,sz-5,1);

while(t--)

{

cin>>s;

if(s[0]=='A')

{

cin>>start>>end;

updateAB(1,start,end,1);//+1 increment increasing ascending order

}

else if(s[0]=='B')

{

cin>>start>>end;

updateAB(1,start,end,-1);//-1 increment decreasing ascending order

}

else if(s[0]=='C')

{

cin>>start>>end>>val;

updateC(1,start,end,val);

}

else if(s[0]=='S')

{

cin>>start>>end;

cout<<query(1,start,end)<<"\n";

}

return 0;

}

Some good links to learn segmented data structure: click here

1282

Asif NaeemAugust 12, 2015

Theory: The idea for solving the problem is: for any fibonacci word F(n) = F(n-1)+F(n-2) = F(n-2)+F(n-3)+F(n-2), so word F(n-2) is both suffix and prefix of word F(n). After observing a little more we can find that F(n-2) will always be the prefix for all the rest of the fibonacci word.Now find the minimum F(n-3)

Continue Reading “1282” →

Category: Data Structure

719

11512

10298

615

11610

10666

1428

11402

12436

1282

Archives

Categories