Timus 2002

16/12/2015 by Мария Илларионова

Идея решения состоит в том, чтобы использовать 2 ассоциативных массива, один из которых хранит в качестве ключа и значения логин и пароль пользователь, а второй — логин и состояние (онлайн/оффлайн).

На С++ можно обойтись и одним ассоциативным массивом, если воспользоваться такой структурой: map<string, pair<string, bool> > m.

Код программы (http://ideone.com/3Uqhuh):

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone {
	public static void main (String[] args) {
		Map<String, String> m = new HashMap<String, String>();
		Map<String, Boolean> u = new HashMap<String, Boolean>();
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s;
		for(int i = 0; i < n; i++) {
			s = in.next();
			if (s.equals("register")) {
				String a, b;
				a = in.next();
				b = in.next();
				if (m.containsKey(a)) {
					System.out.println("fail: user already exists");
				}
				else {
					m.put(a, b);
					u.put(a, false);
					System.out.println("success: new user added");
				}
			}
			else if (s.equals("login")) {
				String a, b;
				a = in.next();
				b = in.next();
				if (!m.containsKey(a)) {
					System.out.println("fail: no such user");
				}
				else if (!b.equals(m.get(a))) {
					System.out.println("fail: incorrect password");
				}
				else {
					if (u.get(a) == false) {
						u.put(a, true);
						System.out.println("success: user logged in");
					}
					else {
						System.out.println("fail: already logged in");
					}
				}
			}
			else {
				String a;
				a = in.next();
				if (!m.containsKey(a)) {
					System.out.println("fail: no such user");
				}
				else {
					if (u.get(a) == true) {
						u.put(a, false);
						System.out.println("success: user logged out");
					}
					else {
						System.out.println("fail: already logged out");
					}
				}
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Map<String, String> m = new HashMap<String, String>();

Map<String, Boolean> u = new HashMap<String, Boolean>();

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String s;

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

s = in.next();

if (s.equals("register")) {

String a, b;

a = in.next();

b = in.next();

if (m.containsKey(a)) {

System.out.println("fail: user already exists");

}

else {

m.put(a, b);

u.put(a, false);

System.out.println("success: new user added");

}

else if (s.equals("login")) {

String a, b;

a = in.next();

b = in.next();

if (!m.containsKey(a)) {

System.out.println("fail: no such user");

}

else if (!b.equals(m.get(a))) {

System.out.println("fail: incorrect password");

}

else {

if (u.get(a) == false) {

u.put(a, true);

System.out.println("success: user logged in");

}

else {

System.out.println("fail: already logged in");

}

else {

String a;

a = in.next();

if (!m.containsKey(a)) {

System.out.println("fail: no such user");

}

else {

if (u.get(a) == true) {

u.put(a, false);

System.out.println("success: user logged out");

}

else {

System.out.println("fail: already logged out");

}

BinarySearchTree

16/12/2015 by Мария Илларионова

Двоичное дерево поиска, или BST, — это структура данных, предназначенная для работы с упорядоченными множествами.

Свойство дерева: если мы находимся в вершине с ключом k, то в левом поддереве находятся только ключи, которые строго меньше k, а в правом — строго больше.

Описание методов, реализованных в классе BinarySearchTree:

метод add():
- если дерево пустое, то говорим, что корень — это наш узел;
- сравниваем поступивший ключ с ключом узла:
  - если ключ меньше, то идём в левое поддерево;
  - если ключ равен, то задаём узлу новое поступившее значение;
  - если ключ больше, то идём в правое поддерево;
методы minKey() и maxKey():
- по свойству дерева, минимальный ключ располагается в самом левом поддереве, а максимальный — в самом правом;
метод delete():
- сначала находим нужный элемент по ключу (если такового нет, то выходим из метода);
- если у удаляемого узла нет правого поддерева, то мы просто замещаем узел его левым поддеревом;
- иначе находим в правом поддереве узел с минимальным ключом:
  - если у этого узла родитель — это удаляемый узел, то мы просто говорим, что правое поддерево удаляемого узла есть правое поддерево найденного, а ключ и значение удаляемого узла — это ключ и значение найденного;
  - если у этого узла другой родитель, то мы замещаем найденный узел его же правым поддеревом, а ключ и значение удаляемого узла — это ключ и значение найденного;

Код программы (http://ideone.com/Z2hbBv):

import java.util.*;
import java.lang.*;
import java.io.*;
 
class BinarySearchTree <Key extends Comparable<Key>, Value> {
	private class Node {
		Key key;
		Value value;
		Node left, right;
		public Node (Key key, Value value) {
			this.key = key;
			this.value = value;
			this.left = this.right = null;
		}
	}
	private Node root;
	
	private Node add(Node node, Key key, Value value) {
		if (node == null) node = new Node(key, value);
		else {
			int compareResult = key.compareTo(node.key);
	        if(compareResult < 0) node.left = add(node.left, key, value);
    	    else if (compareResult == 0) node.value = value; 
        	else node.right = add(node.right, key, value);
		}
        return node;
	}
	public void add(Key key, Value value) {
		root = add(root, key, value);
	}
        
	public Key MinKey(){
        Node cur = root;
        while (cur.left != null) cur = cur.left;
        return cur.key;
    }
    
	public Key MaxKey(){
        Node cur = root;
        while (cur.right != null) cur = cur.right;
        return cur.key;
    }

	public void delete(Key key) {
        Node cur = root;
        Node prev = null;
        while (true) {
            if (cur == null) return;
            int compareResult = key.compareTo(cur.key);
            if (compareResult < 0) {
                prev = cur; 
                cur = cur.left;
            }
            else if (compareResult == 0) break;
            else {
            	prev = cur;
                cur = cur.right;
            }
        }
        if (cur.right == null) {
        	if (cur == prev.left) prev.left = cur.left;
        	else prev.right = cur.left;
        }
        else {
        	Node minFromRight = cur.right;
        	prev = null;
        	while (minFromRight.left != null) {
        		prev = minFromRight;
        		minFromRight = minFromRight.left;
        	}
        	if (prev == null) cur.right = minFromRight.right;
        	else prev.left = minFromRight.right;
        	cur.key = minFromRight.key;
        	cur.value = minFromRight.value;
        }
	}
	
	public Value get(Key key) {
        Node cur = root;
        while (true) {
            if (cur == null) break;
            int compareResult = key.compareTo(cur.key);
            if (compareResult < 0) cur = cur.left;
            else if (compareResult == 0) break;
            else cur = cur.right;
        }
        return cur == null ? (Value)null : cur.value;
	}
	
	private void print(Node node, int level) {
		if (node != null) {
			print(node.right, level + 1);
			for (int i = 0; i < level; i++) {
				System.out.print("\t");
			}
			System.out.println(node.key);
			//System.out.println(node.key + " -> " + node.value); 
			print(node.left, level + 1);
		}
	}
	public void print() {
		print(root, 0);
	}
}
 
class Ideone {
	public static void main (String[] args) {
		BinarySearchTree<Integer, Integer> a = new BinarySearchTree<Integer, Integer>();
		int n = 10;
		for(int i = 0; i < n; i++) {
			a.add((int)(Math.random()*10), (int)(Math.random()*1000));
		}
		System.out.println(a.MaxKey() + " -> " + a.get(a.MaxKey()));
		System.out.println(a.MinKey() + " -> " + a.get(a.MinKey()));
		a.print();
		System.out.println("\n\n");
		Integer x = (int)(Math.random()*10);
		System.out.println(x);
		System.out.println("\n\n");
		a.delete(x);
		a.print();
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

import java.util.*;

import java.lang.*;

import java.io.*;

class BinarySearchTree <Key extends Comparable<Key>, Value> {

private class Node {

Key key;

Value value;

Node left, right;

public Node (Key key, Value value) {

this.key = key;

this.value = value;

this.left = this.right = null;

}

private Node root;

private Node add(Node node, Key key, Value value) {

if (node == null) node = new Node(key, value);

else {

int compareResult = key.compareTo(node.key);

if(compareResult < 0) node.left = add(node.left, key, value);

else if (compareResult == 0) node.value = value;

else node.right = add(node.right, key, value);

}

return node;

}

public void add(Key key, Value value) {

root = add(root, key, value);

}

public Key MinKey(){

Node cur = root;

while (cur.left != null) cur = cur.left;

return cur.key;

}

public Key MaxKey(){

Node cur = root;

while (cur.right != null) cur = cur.right;

return cur.key;

}

public void delete(Key key) {

Node cur = root;

Node prev = null;

while (true) {

if (cur == null) return;

int compareResult = key.compareTo(cur.key);

if (compareResult < 0) {

prev = cur;

cur = cur.left;

}

else if (compareResult == 0) break;

else {

prev = cur;

cur = cur.right;

}

if (cur.right == null) {

if (cur == prev.left) prev.left = cur.left;

else prev.right = cur.left;

}

else {

Node minFromRight = cur.right;

prev = null;

while (minFromRight.left != null) {

prev = minFromRight;

minFromRight = minFromRight.left;

}

if (prev == null) cur.right = minFromRight.right;

else prev.left = minFromRight.right;

cur.key = minFromRight.key;

cur.value = minFromRight.value;

}

public Value get(Key key) {

Node cur = root;

while (true) {

if (cur == null) break;

int compareResult = key.compareTo(cur.key);

if (compareResult < 0) cur = cur.left;

else if (compareResult == 0) break;

else cur = cur.right;

}

return cur == null ? (Value)null : cur.value;

}

private void print(Node node, int level) {

if (node != null) {

print(node.right, level + 1);

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

System.out.print("\t");

}

System.out.println(node.key);

//System.out.println(node.key + " -> " + node.value);

print(node.left, level + 1);

}

public void print() {

print(root, 0);

}

class Ideone {

public static void main (String[] args) {

BinarySearchTree<Integer, Integer> a = new BinarySearchTree<Integer, Integer>();

int n = 10;

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

a.add((int)(Math.random()*10), (int)(Math.random()*1000));

}

System.out.println(a.MaxKey() + " -> " + a.get(a.MaxKey()));

System.out.println(a.MinKey() + " -> " + a.get(a.MinKey()));

a.print();

System.out.println("\n\n");

Integer x = (int)(Math.random()*10);

System.out.println(x);

System.out.println("\n\n");

a.delete(x);

a.print();

}

Обратная польская нотация

09/12/2015 by Мария Илларионова

Передо мной стояли задачи:

перевести выражение в обратную польскую нотацию;
посчитать значение выражения.

Также я реализовала унарный минус, деление и функции cube(), sqrt(), pow10().

Выражение	Обратная польская нотация	Результат
15 * -(3 — 4)	15 3 4 — u- *	15
sqrt(4) + (8 * 0.5)	4 sqrt 8 0.5 * +	6
-cube(-3)	3 u- cube u-	27
92 / 10	92 10 /	9.2
pow10(2) — 95 + 4 * 8	2 pow10 95 — 4 8 * +	37

Алгоритм перевода в обратную польскую запись:

считываем поочерёдно все лексемы, попутно убирая пробелы;
если лексема — это число или переменная, то добавляем её в результирующий список;
если лексема — это функция, то добавляем её в стэк;
если лексема — это открывающая скобка, то добавляем её в стэк;
если лексема — это закрывающая скобка, то:
- помещаем элементы из стэка в результирующую строку пока не встретим открывающую скобку, притом открывающая скобка удаляется из стэка, но в результирующую строку не добавляется;
- если на вершине стэка оказывается символ функции, то мы помещаем его из стэка в результирующую строку;
- если открывающая скока не была встречена, то скобки не согласованы.
если лексема — это оператор, то:
- если это последний символ выражения, то выражение некорректно;
- если это унарный минус, то добавляем его в стэк;
- иначе:
  - выталкиваем верхние элементы стэка в результирующую строку, пока приоритет текущего оператора меньше либо равен приоритету оператора, находящегося на верине стэка;
  - помещаем текущий оператор в стэк;
когда все данные считаны, выталкиваем все элементы стэка в результирующую строку; если в стэке оказались символы не операторов, то скобки не согласованы.

Алгоритм вычисления значения выражения в обратной польской нотации:

если в записи встретили число, то кладём его в стэк;
если в записи встретили функцию или унарный минус, то :
- вытаскиваем из стэка верхний элемент;
- применяем функцию к нему;
- кладём элемент обратно в стэк;
если в записи встретили бинарный оператор, то:
- вытаскиваем из стэка два верхних элемента;
- выполняем над ними операцию;
- кладём в стэк результат выполнения операции;
выводим последний элемент стэка.

Код программы

ideone.com

import java.util.*;
import java.lang.*;
import java.io.*;

class ExpressionParser {
	private static String operators = "+-*/";
	private static String delimiters = "() " + operators;
	public static boolean flag = true;
	private static boolean isDelimiter(String token) {
		if (token.length() != 1) return false;
		for (int i = 0; i < delimiters.length(); i++) {
			if (token.charAt(0) == delimiters.charAt(i)) return true;
		}
		return false;
	}
	
	private static boolean isOperator(String token) {
		if (token.equals("u-")) return true;
		for (int i = 0; i < operators.length(); i++) {
			if (token.charAt(0) == operators.charAt(i)) return true;
		}
		return false;
	}
	
	private static boolean isFunction(String token) {
		if (token.equals("sqrt") || token.equals("cube") || token.equals("pow10")) return true;
		return false;
	}
	
	private static int priority(String token) {
		if (token.equals("(")) return 1;
		if (token.equals("+") || token.equals("-")) return 2;
		if (token.equals("*") || token.equals("/")) return 3;
		return 4;
	}
	
	public static List<String> parse(String infix) {
		List<String> postfix = new ArrayList<String>();
		Deque<String> stack = new ArrayDeque<String>();
		StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true);
		String prev = "";
		String curr = "";
		while (tokenizer.hasMoreTokens()) {
			curr = tokenizer.nextToken();
			if (!tokenizer.hasMoreTokens() && isOperator(curr)) {
				System.out.println("Некорректное выражение.");
				flag = false;
				return postfix;
			}
			if (curr.equals(" ")) continue;
			if (isFunction(curr)) stack.push(curr);
			else if (isDelimiter(curr)) {
				if (curr.equals("(")) stack.push(curr);
				else if (curr.equals(")")) {
					while (!stack.peek().equals("(")) {
						postfix.add(stack.pop());
						if (stack.isEmpty()) {
							System.out.println("Скобки не согласованы.");
							flag = false;
							return postfix;
						}
					}
					stack.pop();
					if (!stack.isEmpty() && isFunction(stack.peek())) {
						postfix.add(stack.pop());
					}
				}
				else {
					if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev)  && !prev.equals(")")))) {
						// унарный минус
						curr = "u-";
					}
					else {
						while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek()))) {
							postfix.add(stack.pop());
						}
						
					}
					stack.push(curr);
				}
				
			}
			
			else {
				postfix.add(curr);
			}
			prev = curr;
		}
		
		while (!stack.isEmpty()) {
			if (isOperator(stack.peek())) postfix.add(stack.pop());
			else {
				System.out.println("Скобки не согласованы.");
				flag = false;
				return postfix;
			}
		}
		return postfix;
	}
}

class Ideone {
	public static Double calc(List<String> postfix) {
		Deque<Double> stack = new ArrayDeque<Double>();
		for (String x : postfix) {
			if (x.equals("sqrt")) stack.push(Math.sqrt(stack.pop()));
			else if (x.equals("cube")) {
				Double tmp = stack.pop();
				stack.push(tmp * tmp * tmp);
			}
			else if (x.equals("pow10")) stack.push(Math.pow(10, stack.pop()));
			else if (x.equals("+")) stack.push(stack.pop() + stack.pop());
			else if (x.equals("-")) {
				Double b = stack.pop(), a = stack.pop();
				stack.push(a - b);
			}
			else if (x.equals("*")) stack.push(stack.pop() * stack.pop());
			else if (x.equals("/")) {
				Double b = stack.pop(), a = stack.pop();
				stack.push(a / b);
			}
			else if (x.equals("u-")) stack.push(-stack.pop());
			else stack.push(Double.valueOf(x));
		}
		return stack.pop();
	}
	
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
		ExpressionParser n = new ExpressionParser();
		List<String> expression = n.parse(s);
		boolean flag = n.flag;
		if (flag) {
			for (String x : expression) System.out.print(x + " ");
			System.out.println();
			System.out.println(calc(expression));
		}
	}
}

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

import java.util.*;

import java.lang.*;

import java.io.*;

class ExpressionParser {

private static String operators = "+-*/";

private static String delimiters = "() " + operators;

public static boolean flag = true;

private static boolean isDelimiter(String token) {

if (token.length() != 1) return false;

for (int i = 0; i < delimiters.length(); i++) {

if (token.charAt(0) == delimiters.charAt(i)) return true;

}

return false;

}

private static boolean isOperator(String token) {

if (token.equals("u-")) return true;

for (int i = 0; i < operators.length(); i++) {

if (token.charAt(0) == operators.charAt(i)) return true;

}

return false;

}

private static boolean isFunction(String token) {

if (token.equals("sqrt") || token.equals("cube") || token.equals("pow10")) return true;

return false;

}

private static int priority(String token) {

if (token.equals("(")) return 1;

if (token.equals("+") || token.equals("-")) return 2;

if (token.equals("*") || token.equals("/")) return 3;

return 4;

}

public static List<String> parse(String infix) {

List<String> postfix = new ArrayList<String>();

Deque<String> stack = new ArrayDeque<String>();

StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true);

String prev = "";

String curr = "";

while (tokenizer.hasMoreTokens()) {

curr = tokenizer.nextToken();

if (!tokenizer.hasMoreTokens() && isOperator(curr)) {

System.out.println("Некорректное выражение.");

flag = false;

return postfix;

}

if (curr.equals(" ")) continue;

if (isFunction(curr)) stack.push(curr);

else if (isDelimiter(curr)) {

if (curr.equals("(")) stack.push(curr);

else if (curr.equals(")")) {

while (!stack.peek().equals("(")) {

postfix.add(stack.pop());

if (stack.isEmpty()) {

System.out.println("Скобки не согласованы.");

flag = false;

return postfix;

}

stack.pop();

if (!stack.isEmpty() && isFunction(stack.peek())) {

postfix.add(stack.pop());

}

else {

if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev) && !prev.equals(")")))) {

// унарный минус

curr = "u-";

}

else {

while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek()))) {

postfix.add(stack.pop());

}

stack.push(curr);

}

else {

postfix.add(curr);

}

prev = curr;

}

while (!stack.isEmpty()) {

if (isOperator(stack.peek())) postfix.add(stack.pop());

else {

System.out.println("Скобки не согласованы.");

flag = false;

return postfix;

}

return postfix;

}

class Ideone {

public static Double calc(List<String> postfix) {

Deque<Double> stack = new ArrayDeque<Double>();

for (String x : postfix) {

if (x.equals("sqrt")) stack.push(Math.sqrt(stack.pop()));

else if (x.equals("cube")) {

Double tmp = stack.pop();

stack.push(tmp * tmp * tmp);

}

else if (x.equals("pow10")) stack.push(Math.pow(10, stack.pop()));

else if (x.equals("+")) stack.push(stack.pop() + stack.pop());

else if (x.equals("-")) {

Double b = stack.pop(), a = stack.pop();

stack.push(a - b);

}

else if (x.equals("*")) stack.push(stack.pop() * stack.pop());

else if (x.equals("/")) {

Double b = stack.pop(), a = stack.pop();

stack.push(a / b);

}

else if (x.equals("u-")) stack.push(-stack.pop());

else stack.push(Double.valueOf(x));

}

return stack.pop();

}

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

String s = in.nextLine();

ExpressionParser n = new ExpressionParser();

List<String> expression = n.parse(s);

boolean flag = n.flag;

if (flag) {

for (String x : expression) System.out.print(x + " ");

System.out.println();

System.out.println(calc(expression));

}

BitSegmentedArray

04/11/2015 by Мария Илларионова

Мне предоставили реализовать класс, который наследует SegmentedArray и характеризуется следующим:

принимает большой массив
элементы массива — 0 и 1
частые запросы get() и set()

Чтобы была возможность хранить очень большой массив, я решила построить класс с помощью битовых операций. Это было возможно, так как элемент моего массива — это 0 и 1, и любое число можно представить в виде последовательности нулей и единиц. Поэтому внутри класса если массив long, в одной ячейке которого может храниться до 64 элементов. Так была решена проблема с расходом памяти.

Из-за представления чисел в двоичном коде, к ним легко применимы битовые операции. Например, для реализации метода get() достаточно использовать битовый сдвиг и битовое «и». Следовательно, метод работает за О(1).

В реализации метода set() мне помогла блочная структура (64 элемента в 1 ячейке массива). А именно: я проверяю границы заданного отрезка, а ячейки, которые попали внутрь полностью просто приравниваю константе: 0 — если все элементы ячейки нули, -1 — если все элементы ячейки единицы.

Точно так же реализован метод add().

С методом min() всё и того проще: ответом служит либо 0, либо 1. Первый же ноль, встреченный на заданном отрезке, определяет ответ.

Также я предположила, что, как и в большинстве олимпиадных задач, индексация массива начинается с единицы. То есть в методе get(), set(), add() и min() необходима сначала уменьшить каждый индекс на единицу, а лишь потом проводить операции над массивом, так как индексация в нём начинается с нуля.

Теоретическая оценка сложности методов:

get(i): O(1);
set(x, y, val): O((y-x)/64);
add(x, y, val): O((y-x)/64) — для val%2==1, и O(1) — для val%2==0;
min(x, y) — O((x-y)/64) — в худшем случае (на отрезке все элементы нули), O(1) — в лучшем случае (на отрезке все элементы единицы).

Код программы:

import java.util.*;
import java.lang.*;
import java.io.*;

interface SegmentedArray {
	long size(); // <= 2^31 - 1
	long get(long index);
	SegmentedArray set(int start, int end, long value); // [start, end) <- value % 2
	SegmentedArray add(int start, int end, long value); // [start, end) += value % 2
	int min(int start, int end); // [start, end)
}

class BitSegmentedArray implements SegmentedArray {
	long size;
	long realSize;
	long []storage;
	public BitSegmentedArray(long size) {
		this.size = size;
		if (size%64!=0) this.realSize = size/64 + 1;
		else this.realSize = size/64;
		storage = new long [(int)realSize];
		for (int i = 0; i < realSize; i++) {
			storage[i] = 0;
		}
	}
	public long size() {
		return size;
	}
	public long get(long index) {
		index--;
		return storage[(int)index/64] >> (index%64) & 1;
	}
	public void print() {
		for (int i = 0; i < this.realSize; i++) {
			for (int j = 0; j < 64; j++) {
				System.out.print(this.storage[i] >> j & 1);
				System.out.print(" ");
			}
		}
		System.out.println();
	}
	public SegmentedArray set(int start, int end, long value) {
		start--;
		end--;
		int realStart = start/64;
		int realEnd = end/64;
		if (realStart != realEnd) {
			for (int i = start%64; i < 64; i++) {
				if (value%2 == 1) storage[realStart] |= (value&1) << i;
				else if (this.get(i+1) == 1) storage[realStart] ^= ((long)1 << i);
			}
			for (int i = realStart + 1; i < realEnd; i++) {
				if (value%2 == 0) storage[i] = 0;
				else storage[i] = -1;
			}
			for (int i = 0; i < end%64; i++) {
				if (value%2 == 1) storage[realEnd] |= (value&1) << i;
				else if (this.get(i+1) == 1) storage[realEnd] ^= ((long)1 << i);
			}
		}
		else {
			for (int i = start%64; i < end%64; i++) {
				if (value%2 == 1) storage[realStart] |= (value&1) << i;
				else if (this.get(i+1) == 1) storage[realStart] ^= ((long)1 << i);
			}
		}
		return this;
	} 
	public SegmentedArray add(int start, int end, long value) {
		if (value % 2 == 0) return this;
		start--;
		end--;
		int realStart = start/64;
		int realEnd = end/64;
		if (realStart != realEnd) {
			for (int i = start%64; i < 64; i++) {
				storage[realStart] ^= (value&1) << i;
			}
			for (int i = realStart + 1; i < realEnd; i++) {
				if (storage[i] == 0) storage[i] = -1;
				else storage[i] = 0;
			}
			for (int i = 0; i < end%64; i++) {
				storage[realEnd] ^= (value&1) << i;
			}
		}
		else {
			for (int i = start%64; i < end%64; i++) {
				storage[realStart] ^= (value&1) << i;
			}
		}
		return this;
	}
	public int min(int start, int end) {
		start--;
		end--;
		int realStart = start/64;
		int realEnd = end/64;
		if (realStart != realEnd) {
			for (int i = start%64; i < 64; i++) {
				long tmp = (storage[realStart] >> i) & 1;
				if (tmp != 1) return 0;
			}
			for (int i = realStart + 1; i < realEnd; i++) {
				if (storage[i] != -1) return 0;
			}
			for (int i = 0; i < end%64; i++) {
				long tmp = (storage[realEnd] >> i) & 1;
				if (tmp != 1) return 0;
			}
		}
		else {
			for (int i = start%64; i < end%64; i++) {
				long tmp = (storage[realStart] >> i) & 1;
				if (tmp != 1) return 0;
			}
		}
		return 1;
	}
	public static void main(String[] args)	{
		BitSegmentedArray b = new BitSegmentedArray (10000);
		long start, end;
		start = System.nanoTime();
		b.set(50, 4566, 1);
		end = System.nanoTime();
		System.out.println("Set в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");
		b.set(130, 740, 0);
		b.set(1000, 1084, 0);
		b.set(3006, 3070, 0);
		
		start = System.nanoTime();
		long get = b.get(111);
		end = System.nanoTime();
		System.out.println("Get в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");
		System.out.println(get);
		
		start = System.nanoTime();
		b.add(76, 830, 1);
		end = System.nanoTime();
		System.out.println("Add в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");
		b.add(60, 92, 0);
		
		start = System.nanoTime();
		int minimum = b.min(130, 1400);
		end = System.nanoTime();
		System.out.println("Min в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");
		System.out.println(minimum);
	}
}

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

import java.util.*;

import java.lang.*;

import java.io.*;

interface SegmentedArray {

long size(); // <= 2^31 - 1

long get(long index);

SegmentedArray set(int start, int end, long value); // [start, end) <- value % 2

SegmentedArray add(int start, int end, long value); // [start, end) += value % 2

int min(int start, int end); // [start, end)

}

class BitSegmentedArray implements SegmentedArray {

long size;

long realSize;

long []storage;

public BitSegmentedArray(long size) {

this.size = size;

if (size%64!=0) this.realSize = size/64 + 1;

else this.realSize = size/64;

storage = new long [(int)realSize];

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

storage[i] = 0;

}

public long size() {

return size;

}

public long get(long index) {

index--;

return storage[(int)index/64] >> (index%64) & 1;

}

public void print() {

for (int i = 0; i < this.realSize; i++) {

for (int j = 0; j < 64; j++) {

System.out.print(this.storage[i] >> j & 1);

System.out.print(" ");

}

System.out.println();

}

public SegmentedArray set(int start, int end, long value) {

start--;

end--;

int realStart = start/64;

int realEnd = end/64;

if (realStart != realEnd) {

for (int i = start%64; i < 64; i++) {

if (value%2 == 1) storage[realStart] |= (value&1) << i;

else if (this.get(i+1) == 1) storage[realStart] ^= ((long)1 << i);

}

for (int i = realStart + 1; i < realEnd; i++) {

if (value%2 == 0) storage[i] = 0;

else storage[i] = -1;

}

for (int i = 0; i < end%64; i++) {

if (value%2 == 1) storage[realEnd] |= (value&1) << i;

else if (this.get(i+1) == 1) storage[realEnd] ^= ((long)1 << i);

}

else {

for (int i = start%64; i < end%64; i++) {

if (value%2 == 1) storage[realStart] |= (value&1) << i;

else if (this.get(i+1) == 1) storage[realStart] ^= ((long)1 << i);

}

return this;

}

public SegmentedArray add(int start, int end, long value) {

if (value % 2 == 0) return this;

start--;

end--;

int realStart = start/64;

int realEnd = end/64;

if (realStart != realEnd) {

for (int i = start%64; i < 64; i++) {

storage[realStart] ^= (value&1) << i;

}

for (int i = realStart + 1; i < realEnd; i++) {

if (storage[i] == 0) storage[i] = -1;

else storage[i] = 0;

}

for (int i = 0; i < end%64; i++) {

storage[realEnd] ^= (value&1) << i;

}

else {

for (int i = start%64; i < end%64; i++) {

storage[realStart] ^= (value&1) << i;

}

return this;

}

public int min(int start, int end) {

start--;

end--;

int realStart = start/64;

int realEnd = end/64;

if (realStart != realEnd) {

for (int i = start%64; i < 64; i++) {

long tmp = (storage[realStart] >> i) & 1;

if (tmp != 1) return 0;

}

for (int i = realStart + 1; i < realEnd; i++) {

if (storage[i] != -1) return 0;

}

for (int i = 0; i < end%64; i++) {

long tmp = (storage[realEnd] >> i) & 1;

if (tmp != 1) return 0;

}

else {

for (int i = start%64; i < end%64; i++) {

long tmp = (storage[realStart] >> i) & 1;

if (tmp != 1) return 0;

}

return 1;

}

public static void main(String[] args) {

BitSegmentedArray b = new BitSegmentedArray (10000);

long start, end;

start = System.nanoTime();

b.set(50, 4566, 1);

end = System.nanoTime();

System.out.println("Set в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");

b.set(130, 740, 0);

b.set(1000, 1084, 0);

b.set(3006, 3070, 0);

start = System.nanoTime();

long get = b.get(111);

end = System.nanoTime();

System.out.println("Get в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");

System.out.println(get);

start = System.nanoTime();

b.add(76, 830, 1);

end = System.nanoTime();

System.out.println("Add в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");

b.add(60, 92, 0);

start = System.nanoTime();

int minimum = b.min(130, 1400);

end = System.nanoTime();

System.out.println("Min в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");

System.out.println(minimum);

}

Протестировать программу можно здесь.

Простейшая реализация интерфейса: SimpleSegmentedArray.

Сравнение скорости работы методов:

Set в BitSegmentedArray отрабатывает за 25626 нс.
Get в BitSegmentedArray отрабатывает за 717 нс.
1
Add в BitSegmentedArray отрабатывает за 16785 нс.
Min в BitSegmentedArray отрабатывает за 6521 нс.
0

Set в BitSegmentedArray отрабатывает за 25626 нс.

Get в BitSegmentedArray отрабатывает за 717 нс.

Add в BitSegmentedArray отрабатывает за 16785 нс.

Min в BitSegmentedArray отрабатывает за 6521 нс.

Set в SimpleSegmentedArray отрабатывает за 200334 нс.
Get в SimpleSegmentedArray отрабатывает за 10362 нс.
1
Add в SimpleSegmentedArray отрабатывает за 43084 нс.
Min в SimpleSegmentedArray отрабатывает за 52949 нс.
0

Set в SimpleSegmentedArray отрабатывает за 200334 нс.

Get в SimpleSegmentedArray отрабатывает за 10362 нс.

Add в SimpleSegmentedArray отрабатывает за 43084 нс.

Min в SimpleSegmentedArray отрабатывает за 52949 нс.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Author Archives: Мария Илларионова

Timus 2002

BinarySearchTree

Обратная польская нотация

Код программы

BitSegmentedArray