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);
}
}
