Untitled

//package Family_tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.TreeSet;

class UserSolution
{
	class Node {
		String name;
		int firstday;
		int lastday;
		int child;
		Node parent;
		String lc;
		
		int level;
		public Node(String name, int firstday, int lastday,
				int level) {
			super();
			this.name = name;
			this.firstday = firstday;
			this.lastday = lastday;
			this.parent = null;
			this.level = level;
			this.lc="";
		}
		
	}
	String charttoString(char[] a) {
		int i = 0;
		String str = "";
		while (a[i] != '\0') {
			str += a[i];
			i++;
		}
		return str;
	}
	HashMap<String, Node> nodeMap;
	int[] time;
	int[][] time1;
	
	void init(char mAncestor[], int mDeathday)
	{
		time=new int[1001];
		time1=new int[1001][1001];
		nodeMap=new HashMap<String, UserSolution.Node>();
		
		String str=charttoString(mAncestor);
		Node root=new Node(str, 0, mDeathday, 0);
		nodeMap.put(str, root);
		updateTime(0, mDeathday);
		return;
	}

	int add(char mName[], char mParent[], int mBirthday, int mDeathday)
	{
		String str=charttoString(mName);
		Node parent=nodeMap.get(charttoString(mParent));
		Node child=new Node(str,mBirthday,mDeathday,parent.level+1);
		child.parent=parent;
		if(parent.child==0){
			child.lc=parent.lc+"L";
		}
		else{
			child.lc=parent.lc+"R";
		}
		parent.child++;
		nodeMap.put(str, child);
		updateTime(mBirthday, mDeathday);
		return child.level;
	}
	
	int distance(char mName1[], char mName2[])
	{
		int ans=0;
		Node node1=nodeMap.get(charttoString(mName1));
		Node node2=nodeMap.get(charttoString(mName2));
		int min=Math.min(node1.lc.length(), node2.lc.length());
		for(int i=0;i<min;i++){
			if(node1.lc.charAt(i)!=node2.lc.charAt(i)){
				break;
			}
			ans++;
		}
//		while(node1!=node2){
//			if(node1.level>node2.level){
//				ans++;
//				node1=node1.parent;
//			}
//			else if(node1.level<node2.level){
//				ans++;
//				node2=node2.parent;
//			}
//			else{
//				ans+=2;
//				node1=node1.parent;
//				node2=node2.parent;
//			}
//		}
		return node1.lc.length()+node2.lc.length()-2*ans;
	}
	
	
	void updateTime(int start,int end){
		int startrow=start/1000;
		int startcol=start%1000;
		int endrow=end/1000;
		int endcol=end%1000;
		if(startrow==endrow){
			for(int i=startcol;i<=endcol;i++){
				time1[startrow][i]++;
			}
		}
		else{
			for(int i=startcol;i<=1000;i++){
				time1[startrow][i]++;
			}
			for(int i=0;i<=endcol;i++){
				time1[endrow][i]++;
			}
			for(int i=startrow+1;i<endrow;i++){
				time[i]++;
			}
		}
	}
	int count(int mDay)
	{
		int start=mDay/1000;
		int end=mDay%1000;
		int ans=time[start]+time1[start][end];
		return ans;
	}
}



package String_Management;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;



class UserSolution
{
	class Node{
		char id;
		Node prev;
		Node next;
		public Node(char id) {
			super();
			this.id = id;
			this.prev = null;
			this.next = null;
		}
		void delete(){
			connect(prev,next);
		}
		
	}
	class DoubleLL{
		Node head,tail;

		public DoubleLL() {	
			this.head = new Node(' ');
			this.tail = new Node(' ');
			connect(head,tail);
		}
		void reset(){
			connect(head,tail);
		}
		boolean isEmpty(){
			return head.next==tail;
		}
		void addLast(Node s){
			connect(tail.prev, s);
			connect(s,tail);
		}
		void addFisrt(Node s){
			connect(s,head.next);
			connect(head,s);
		}
	}
	void connect(Node a,Node b){
		a.next=b;
		b.prev=a;
	}
	
	boolean Reverse;
	DoubleLL LL;
	int[] count1;
	int[][] count2;
	int[][][]count3;
	int[][][][] count4;
	
	void init(char mStr[])
	{
		
		//String str=charttoString(mStr);
		count1=new int[26];
		count2=new int[26][26];
		count3=new int[26][26][26];
		count4=new int[26][26][26][26];
		LL=new DoubleLL();
		LL.reset();
		Reverse=false;
		
		int j=0;
		while(mStr[j]!='\0'){
			Node node=new Node(mStr[j]);
			LL.addLast(node);
			count1[mStr[j]-'a']++;
			if(j>=1){
				count2[mStr[j-1]-'a'][mStr[j]-'a']++;
			}
			if(j>=2){
				count3[mStr[j-2]-'a'][mStr[j-1]-'a'][mStr[j]-'a']++;
			}
			if(j>=3){
				count4[mStr[j-3]-'a'][mStr[j-2]-'a'][mStr[j-1]-'a'][mStr[j]-'a']++;
			}
			j++;
		}
		
	}
	
	void appendWord(char mWord[])
	{
		if(Reverse){
			int i=0;
			while(mWord[i]!='\0'){
				Node node=new Node(mWord[i]);
				//LL.addFisrt(node);
				
				count1[mWord[i]-'a']++;
				count2[mWord[i]-'a'][LL.head.next.id-'a']++;
				count3[mWord[i]-'a'][LL.head.next.id-'a'][LL.head.next.next.id-'a']++;
				count4[mWord[i]-'a'][LL.head.next.id-'a'][LL.head.next.next.id-'a'][LL.head.next.next.next.id-'a']++;
				LL.addFisrt(node);
				i++;
			}
		}
		else{
			
			int i=0;
			while(mWord[i]!='\0'){
				Node node=new Node(mWord[i]);
				//LL.addLast(node);
				
				count1[mWord[i]-'a']++;
				count2[LL.tail.prev.id-'a'][mWord[i]-'a']++;
				count3[LL.tail.prev.prev.id-'a'][LL.tail.prev.id-'a'][mWord[i]-'a']++;
				count4[LL.tail.prev.prev.prev.id-'a'][LL.tail.prev.prev.id-'a'][LL.tail.prev.id-'a'][mWord[i]-'a']++;
				LL.addLast(node);
				i++;
			}
		}
		
		

	}

	void cut(int k)
	{
		
		if(Reverse){
			while(k>0){
				Node node=LL.head.next;
				
				count1[node.id-'a']--;
				count2[node.id-'a'][node.next.id-'a']--;
				count3[node.id-'a'][node.next.id-'a'][node.next.next.id-'a']--;
				count4[node.id-'a'][node.next.id-'a'][node.next.next.id-'a'][node.next.next.next.id-'a']--;
				node.delete();
				
				k--;
			}
			
		}
		else{
			while(k>0){
				Node node=LL.tail.prev;
				
				count1[node.id-'a']--;
				count2[node.prev.id-'a'][node.id-'a']--;
				count3[node.prev.prev.id-'a'][node.prev.id-'a'][node.id-'a']--;
				count4[node.prev.prev.prev.id-'a'][node.prev.prev.id-'a'][node.prev.id-'a'][node.id-'a']--;
				node.delete();
				
				k--;
			}
		}	
	}

	void reverse()
	{
		if(Reverse){
			Reverse=false;
			return;
		}
		Reverse=true;
	}

	int countOccurrence(char mWord[])
	{
		int ans=0;
		
		if(Reverse){
			int j=0;
			while(mWord[j]!='\0'){
				if(j==0){
					ans=count1[mWord[j]-'a'];
				}
				if(j>=1){
					ans=count2[mWord[j]-'a'][mWord[j-1]-'a'];
				}
				if(j>=2){
					ans=count3[mWord[j]-'a'][mWord[j-1]-'a'][mWord[j-2]-'a'];
				}
				if(j>=3){
					ans=count4[mWord[j]-'a'][mWord[j-1]-'a'][mWord[j-2]-'a'][mWord[j-3]-'a'];
				}
				j++;
			}
		}
		else{
			int j=0;
			while(mWord[j]!='\0'){
				if(j==0){
					ans=count1[mWord[j]-'a'];
				}
				if(j>=1){
					ans=count2[mWord[j-1]-'a'][mWord[j]-'a'];
				}
				if(j>=2){
					ans=count3[mWord[j-2]-'a'][mWord[j-1]-'a'][mWord[j]-'a'];
				}
				if(j>=3){
					ans=count4[mWord[j-3]-'a'][mWord[j-2]-'a'][mWord[j-1]-'a'][mWord[j]-'a'];
				}
				j++;
			}
		}
		return ans;
	}
}