代码

#include "router.h"

#include <stdint.h>
#include <arpa/inet.h>

#include <algorithm>

static inline bool in_entry_range(const RoutingTableEntry &e, uint32_t addr) {
	return (uint64_t) (addr ^ e.addr) >> (32 - e.len) == 0;
}

const int MAXN = 900000;

static uint32_t left[MAXN * 2];
static uint32_t nexthops[MAXN * 2];
static int n_intervals;

static inline void append(uint32_t l, uint32_t nexthop) {
	if (left[n_intervals - 1] == l) {
		nexthops[n_intervals - 1] = nexthop;
	} else if (left[n_intervals - 1] < l) {
		left[n_intervals] = l;
		nexthops[n_intervals] = nexthop;
		++n_intervals;
	}
}

static uint64_t bitmap[1 << (32 - 6)];
static int sum[1 << (32 - 6)];

void init(int n, int q, const RoutingTableEntry *a) {
	RoutingTableEntry stack[34];
	int top = 0;
	
	stack[0].nexthop = -1u;
	
	n_intervals = 1;
	left[0] = 0;
	nexthops[0] = 0;
	
	for (int i = 0; i < n; i++) {
		RoutingTableEntry tmp = a[i];
		uint32_t addr = tmp.addr = htonl(tmp.addr);
		while (top && !in_entry_range(stack[top], addr)) {
			append(stack[top].addr + (1ull << (32 - stack[top].len)), stack[top - 1].nexthop);
			--top;
		}
		stack[++top] = tmp;
		append(tmp.addr, tmp.nexthop);
	}
	
	while (top) {
		append(stack[top].addr + (1ull << (32 - stack[top].len)), stack[top - 1].nexthop);
		--top;
	}
	
	for (int i = 0; i < n_intervals; i++) {
		uint32_t l = left[i];
		bitmap[l >> 6] |= 1ull << (l & 63);
	}
	
	int s = 0;
	for (int i = 0; i < 1 << (32 - 6); i++) {
		sum[i] = s;
		s += __builtin_popcountll(bitmap[i]);
	}
}

unsigned query(unsigned addr) {
	addr = htonl(addr);
	
	uint32_t idx = addr >> 6;
	uint32_t bits = addr & 63;
	int s1 = sum[idx];
	int s2 = __builtin_popcountll(bitmap[idx] & ((2ull << bits) - 1ull));
	return nexthops[s1 + s2 - 1];
}

评测结果