#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 14 important bits, giving max value of (2^15 - 1)
#define BITS 14
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
typedef struct {
int count;
int capacity;
int *indexes; // position (i.e. j) where number is
} INDEXLIST;
typedef struct NODE_STRUCT {
struct NODE_STRUCT *left, *right;
int minIndex, maxIndex;
int value; // for a leaf
INDEXLIST *indexList; // for a leaf
} NODE;
INDEXLIST *add_index_to_list(INDEXLIST *list, int index) {
if (!list) {
list
= (INDEXLIST
*)malloc(sizeof(INDEXLIST
)); list->count = 0;
list->capacity = 8;
list
->indexes
= (int *)malloc(8 * sizeof(int)); }
if ((list->count + 1) >= list->capacity) {
int newCapacity = list->capacity + 8;
int *newList
= (int *)malloc(newCapacity
* sizeof(int)); memcpy(newList
, list
->indexes
, list
->capacity
* sizeof(int)); list->indexes = newList;
list->capacity = newCapacity;
}
list->indexes[list->count++] = index;
return list;
}
// expands range, adds to index list if at end, otherwise traverses based on bit
NODE *add_index_to_node(NODE *node, int index, int value, int depth) {
int bit;
// if node is null, we need to create a node
if (!node) {
node
= (NODE
*)malloc(sizeof(NODE
)); node->minIndex = 0x7fffffff;
node->maxIndex = 0;
node->indexList = NULL;
node->left = node->right = NULL;
node->value = 0;
}
// expand node range
node->minIndex = MIN(index, node->minIndex);
node->maxIndex = MAX(index, node->maxIndex);
// get bit at this position
bit = (BITS - depth);
// if bit is < 0, we are at a leaf and there are no more bits, just an index list
if (bit < 0) {
node->indexList = add_index_to_list(node->indexList, index);
node->value = value;
return node;
}
// if he has THIS bit, go right, otherwise left
if (value & (1 << bit)) {
node->right = add_index_to_node(node->right, index, value, depth + 1);
} else {
node->left = add_index_to_node(node->left, index, value, depth + 1);
}
return node;
}
// will call with find_largest(root, value, p, q, 0)
// NOTES:
// * it WILL return the maximum value from any node with index in range
// * once you have a non-zero value (found an index in range), it is no longer
// necessary to traverse the other side (left/right) than you started with
int find_largest(NODE *node, int value, int minIndex, int maxIndex, int depth)
{
int i, result;
INDEXLIST *list;
// make sure there's a node
if (!node)
return 0;
// make sure index ranges overlap
if (minIndex > node->maxIndex || maxIndex < node->minIndex)
return 0;
// if we're at maximum depth we have an INDEXLIST, check it and return
list = node->indexList;
if (list) {
for (i = 0; i < list->count; i++) {
if (list->indexes[i] >= minIndex && list->indexes[i] <= maxIndex) {
return (value ^ node->value);
}
}
return 0;
}
// if bit of value is set, go left first (to get numbers that when xored with value would have 1 there)
if (value & (1 << BITS - depth)) {
result = find_largest(node->left, value, minIndex, maxIndex, depth + 1);
if (!result)
result = result = find_largest(node->right, value, minIndex, maxIndex, depth + 1);
} else {
result = find_largest(node->right, value, minIndex, maxIndex, depth + 1);
if (!result)
result = result = find_largest(node->left, value, minIndex, maxIndex, depth + 1);
}
return result;
}
void free_node(NODE *node) {
if (!node)
return;
if (node->indexList) {
free(node
->indexList
->indexes
); }
free_node(node->left);
free_node(node->right);
}
int main() {
int T, N, Q, a, p, q, i, k, x, v, largest, index, result;
NODE *root = NULL;
while (T--) {
for (i = 1; i <= N; i++) {
root = add_index_to_node(root, i, x, 0);
}
for (i = 0; i < Q; i++) {
scanf("%d %d %d", &a
, &p
, &q
); result = find_largest(root, a, p, q, 0);
}
// free memory
free_node(root);
root = NULL;
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgoKLy8gMTQgaW1wb3J0YW50IGJpdHMsIGdpdmluZyBtYXggdmFsdWUgb2YgKDJeMTUgLSAxKQojZGVmaW5lIEJJVFMgMTQKCiNkZWZpbmUgTUlOKGEsYikgKCgoYSk8KGIpKT8oYSk6KGIpKQojZGVmaW5lIE1BWChhLGIpICgoKGEpPihiKSk/KGEpOihiKSkKCnR5cGVkZWYgc3RydWN0IHsKCWludCBjb3VudDsKCWludCBjYXBhY2l0eTsKCWludCAqaW5kZXhlczsgLy8gcG9zaXRpb24gKGkuZS4gaikgd2hlcmUgbnVtYmVyIGlzCn0gSU5ERVhMSVNUOwoKdHlwZWRlZiBzdHJ1Y3QgTk9ERV9TVFJVQ1QgewoJc3RydWN0IE5PREVfU1RSVUNUICpsZWZ0LCAqcmlnaHQ7CglpbnQgbWluSW5kZXgsIG1heEluZGV4OwoJaW50IHZhbHVlOyAvLyBmb3IgYSBsZWFmCglJTkRFWExJU1QgKmluZGV4TGlzdDsgLy8gZm9yIGEgbGVhZgp9IE5PREU7CgpJTkRFWExJU1QgKmFkZF9pbmRleF90b19saXN0KElOREVYTElTVCAqbGlzdCwgaW50IGluZGV4KSB7CglpZiAoIWxpc3QpIHsKCQlsaXN0ID0gKElOREVYTElTVCAqKW1hbGxvYyhzaXplb2YoSU5ERVhMSVNUKSk7CgkJbGlzdC0+Y291bnQgPSAwOwoJCWxpc3QtPmNhcGFjaXR5ID0gODsKCQlsaXN0LT5pbmRleGVzID0gKGludCAqKW1hbGxvYyg4ICogc2l6ZW9mKGludCkpOwoJfQoJaWYgKChsaXN0LT5jb3VudCArIDEpID49IGxpc3QtPmNhcGFjaXR5KSB7CgkJaW50IG5ld0NhcGFjaXR5ID0gbGlzdC0+Y2FwYWNpdHkgKyA4OwoJCWludCAqbmV3TGlzdCA9IChpbnQgKiltYWxsb2MobmV3Q2FwYWNpdHkgKiBzaXplb2YoaW50KSk7CgkJbWVtY3B5KG5ld0xpc3QsIGxpc3QtPmluZGV4ZXMsIGxpc3QtPmNhcGFjaXR5ICogc2l6ZW9mKGludCkpOwoJCWZyZWUobGlzdC0+aW5kZXhlcyk7CgkJbGlzdC0+aW5kZXhlcyA9IG5ld0xpc3Q7CgkJbGlzdC0+Y2FwYWNpdHkgPSBuZXdDYXBhY2l0eTsKCX0KCWxpc3QtPmluZGV4ZXNbbGlzdC0+Y291bnQrK10gPSBpbmRleDsKCXJldHVybiBsaXN0Owp9CgovLyBleHBhbmRzIHJhbmdlLCBhZGRzIHRvIGluZGV4IGxpc3QgaWYgYXQgZW5kLCBvdGhlcndpc2UgdHJhdmVyc2VzIGJhc2VkIG9uIGJpdApOT0RFICphZGRfaW5kZXhfdG9fbm9kZShOT0RFICpub2RlLCBpbnQgaW5kZXgsIGludCB2YWx1ZSwgaW50IGRlcHRoKSB7CglpbnQgYml0OwoKCS8vIGlmIG5vZGUgaXMgbnVsbCwgd2UgbmVlZCB0byBjcmVhdGUgYSBub2RlCglpZiAoIW5vZGUpIHsKCQlub2RlID0gKE5PREUgKiltYWxsb2Moc2l6ZW9mKE5PREUpKTsKCQlub2RlLT5taW5JbmRleCA9IDB4N2ZmZmZmZmY7CgkJbm9kZS0+bWF4SW5kZXggPSAwOwoJCW5vZGUtPmluZGV4TGlzdCA9IE5VTEw7CgkJbm9kZS0+bGVmdCA9IG5vZGUtPnJpZ2h0ID0gTlVMTDsKCQlub2RlLT52YWx1ZSA9IDA7Cgl9CgoJLy8gZXhwYW5kIG5vZGUgcmFuZ2UKCW5vZGUtPm1pbkluZGV4ID0gTUlOKGluZGV4LCBub2RlLT5taW5JbmRleCk7Cglub2RlLT5tYXhJbmRleCA9IE1BWChpbmRleCwgbm9kZS0+bWF4SW5kZXgpOwoKCS8vIGdldCBiaXQgYXQgdGhpcyBwb3NpdGlvbgoJYml0ID0gKEJJVFMgLSBkZXB0aCk7CgoJLy8gaWYgYml0IGlzIDwgMCwgd2UgYXJlIGF0IGEgbGVhZiBhbmQgdGhlcmUgYXJlIG5vIG1vcmUgYml0cywganVzdCBhbiBpbmRleCBsaXN0CglpZiAoYml0IDwgMCkgewoJCW5vZGUtPmluZGV4TGlzdCA9IGFkZF9pbmRleF90b19saXN0KG5vZGUtPmluZGV4TGlzdCwgaW5kZXgpOwoJCW5vZGUtPnZhbHVlID0gdmFsdWU7CgkJcmV0dXJuIG5vZGU7Cgl9CgoJLy8gaWYgaGUgaGFzIFRISVMgYml0LCBnbyByaWdodCwgb3RoZXJ3aXNlIGxlZnQKCWlmICh2YWx1ZSAmICgxIDw8IGJpdCkpIHsKCQlub2RlLT5yaWdodCA9IGFkZF9pbmRleF90b19ub2RlKG5vZGUtPnJpZ2h0LCBpbmRleCwgdmFsdWUsIGRlcHRoICsgMSk7Cgl9IGVsc2UgewoJCW5vZGUtPmxlZnQgPSBhZGRfaW5kZXhfdG9fbm9kZShub2RlLT5sZWZ0LCBpbmRleCwgdmFsdWUsIGRlcHRoICsgMSk7Cgl9CgoJcmV0dXJuIG5vZGU7Cn0KCi8vIHdpbGwgY2FsbCB3aXRoIGZpbmRfbGFyZ2VzdChyb290LCB2YWx1ZSwgcCwgcSwgMCkKLy8gTk9URVM6Ci8vCQkqIGl0IFdJTEwgcmV0dXJuIHRoZSBtYXhpbXVtIHZhbHVlIGZyb20gYW55IG5vZGUgd2l0aCBpbmRleCBpbiByYW5nZQovLwkJKiBvbmNlIHlvdSBoYXZlIGEgbm9uLXplcm8gdmFsdWUgKGZvdW5kIGFuIGluZGV4IGluIHJhbmdlKSwgaXQgaXMgbm8gbG9uZ2VyCi8vCQkJCW5lY2Vzc2FyeSB0byB0cmF2ZXJzZSB0aGUgb3RoZXIgc2lkZSAobGVmdC9yaWdodCkgdGhhbiB5b3Ugc3RhcnRlZCB3aXRoCmludCBmaW5kX2xhcmdlc3QoTk9ERSAqbm9kZSwgaW50IHZhbHVlLCBpbnQgbWluSW5kZXgsIGludCBtYXhJbmRleCwgaW50IGRlcHRoKQp7CglpbnQgaSwgcmVzdWx0OwoJSU5ERVhMSVNUICpsaXN0OwoKCS8vIG1ha2Ugc3VyZSB0aGVyZSdzIGEgbm9kZQoJaWYgKCFub2RlKQoJCXJldHVybiAwOwoKCS8vIG1ha2Ugc3VyZSBpbmRleCByYW5nZXMgb3ZlcmxhcAoJaWYgKG1pbkluZGV4ID4gbm9kZS0+bWF4SW5kZXggfHwgbWF4SW5kZXggPCBub2RlLT5taW5JbmRleCkKCQlyZXR1cm4gMDsKCgkvLyBpZiB3ZSdyZSBhdCBtYXhpbXVtIGRlcHRoIHdlIGhhdmUgYW4gSU5ERVhMSVNULCBjaGVjayBpdCBhbmQgcmV0dXJuCglsaXN0ID0gbm9kZS0+aW5kZXhMaXN0OwoJaWYgKGxpc3QpIHsKCQlmb3IgKGkgPSAwOyBpIDwgbGlzdC0+Y291bnQ7IGkrKykgewoJCQlpZiAobGlzdC0+aW5kZXhlc1tpXSA+PSBtaW5JbmRleCAmJiBsaXN0LT5pbmRleGVzW2ldIDw9IG1heEluZGV4KSB7CgkJCQlyZXR1cm4gKHZhbHVlIF4gbm9kZS0+dmFsdWUpOwoJCQl9CgkJfQoJCXJldHVybiAwOwoJfQoKCS8vIGlmIGJpdCBvZiB2YWx1ZSBpcyBzZXQsIGdvIGxlZnQgZmlyc3QgKHRvIGdldCBudW1iZXJzIHRoYXQgd2hlbiB4b3JlZCB3aXRoIHZhbHVlIHdvdWxkIGhhdmUgMSB0aGVyZSkKCWlmICh2YWx1ZSAmICgxIDw8IEJJVFMgLSBkZXB0aCkpIHsKCQlyZXN1bHQgPSBmaW5kX2xhcmdlc3Qobm9kZS0+bGVmdCwgdmFsdWUsIG1pbkluZGV4LCBtYXhJbmRleCwgZGVwdGggKyAxKTsKCQlpZiAoIXJlc3VsdCkKCQkJcmVzdWx0ID0gcmVzdWx0ID0gZmluZF9sYXJnZXN0KG5vZGUtPnJpZ2h0LCB2YWx1ZSwgbWluSW5kZXgsIG1heEluZGV4LCBkZXB0aCArIDEpOwoJfSBlbHNlIHsKCQlyZXN1bHQgPSBmaW5kX2xhcmdlc3Qobm9kZS0+cmlnaHQsIHZhbHVlLCBtaW5JbmRleCwgbWF4SW5kZXgsIGRlcHRoICsgMSk7CgkJaWYgKCFyZXN1bHQpCgkJCXJlc3VsdCA9IHJlc3VsdCA9IGZpbmRfbGFyZ2VzdChub2RlLT5sZWZ0LCB2YWx1ZSwgbWluSW5kZXgsIG1heEluZGV4LCBkZXB0aCArIDEpOwoJfQoJcmV0dXJuIHJlc3VsdDsKfQoKdm9pZCBmcmVlX25vZGUoTk9ERSAqbm9kZSkgewoJaWYgKCFub2RlKQoJCXJldHVybjsKCWlmIChub2RlLT5pbmRleExpc3QpIHsKCQlmcmVlKG5vZGUtPmluZGV4TGlzdC0+aW5kZXhlcyk7CgkJZnJlZShub2RlLT5pbmRleExpc3QpOwoJfQoJZnJlZV9ub2RlKG5vZGUtPmxlZnQpOwoJZnJlZV9ub2RlKG5vZGUtPnJpZ2h0KTsKCWZyZWUobm9kZSk7Cn0KCmludCBtYWluKCkgewoKCWludCBULCBOLCBRLCBhLCBwLCBxLCBpLCBrLCB4LCB2LCBsYXJnZXN0LCBpbmRleCwgcmVzdWx0OwoJTk9ERSAqcm9vdCA9IE5VTEw7CgoJc2NhbmYoIiVkIiwgJlQpOwoKCXdoaWxlIChULS0pIHsKCQlzY2FuZigiJWQgJWQiLCAmTiwgJlEpOwoJCWZvciAoaSA9IDE7IGkgPD0gTjsgaSsrKSB7CgkJCXNjYW5mKCIlZCIsICZ4KTsKCQkJcm9vdCA9IGFkZF9pbmRleF90b19ub2RlKHJvb3QsIGksIHgsIDApOwoJCX0KCgkJZm9yIChpID0gMDsgaSA8IFE7IGkrKykgewoJCQlzY2FuZigiJWQgJWQgJWQiLCAmYSwgJnAsICZxKTsKCQkJcmVzdWx0ID0gZmluZF9sYXJnZXN0KHJvb3QsIGEsIHAsIHEsIDApOwoJCQlwcmludGYoIiVkXG4iLCByZXN1bHQpOwoJCX0KCgkJLy8gZnJlZSBtZW1vcnkKCQlmcmVlX25vZGUocm9vdCk7CgkJcm9vdCA9IE5VTEw7Cgl9Cn0=