代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include "router.h"
#include <bits/stdc++.h>
#include <arpa/inet.h>
using namespace std;

struct MyEntry
{
    unsigned len, addr, nexthop;
};
bool operator<(const MyEntry &a, const MyEntry &b)
{
    return *(unsigned long long *) &a < *(unsigned long long *) &b;
}

struct VEntry
{
    unsigned addr, nexthop;
};
bool operator<(const VEntry &a, const VEntry &b)
{
    return a.addr < b.addr;
}

static vector<VEntry> V;
const int FAST_OFFSET = 18;
static VEntry *fastV[1 << FAST_OFFSET | 1];
static set<MyEntry> S;

static unsigned pow2(unsigned x)
{
    if(x >= 32) return 0;
    return 1u << x;
}

static void gao(int l, int r, VEntry *lp, VEntry *rp)
{
    if(r - l <= 16)
    {
        for(int m = l; m <= r; m++) fastV[m] = lower_bound(lp, rp, (VEntry) {m << (32 - FAST_OFFSET), 0});
        return;
    }
    int m = (l + r) >> 1;
    VEntry *cp = lower_bound(lp, rp, (VEntry) {m << (32 - FAST_OFFSET), 0});
    fastV[m] = cp;
    gao(l, m, lp, cp); gao(m + 1, r, cp, rp);
}

void init(int n, int q, const RoutingTableEntry *a)
{
    for(int i = 0; i < n; i++) S.insert(S.end(), (MyEntry) {a[i].len, htonl(a[i].addr), a[i].nexthop});
    S.insert(S.begin(), (MyEntry) {0, 0, 0});
    for(auto it = S.begin(); it != S.end();)
    {
        auto jt = it; ++jt;
        if(jt != S.end() && jt->addr <= it->addr + pow2(32 - it->len) - 1u)
        {
            S.insert(it, (MyEntry) {it->len + 1, it->addr, it->nexthop});
            S.insert(it, (MyEntry) {it->len + 1, it->addr | pow2(31 - it->len), it->nexthop});
        }
        else V.push_back((VEntry) {it->addr, it->nexthop});
        jt = it; ++jt;
        S.erase(it); it = jt;
    }
    gao(0, 1 << FAST_OFFSET, V.data(), V.data() + V.size());
}

unsigned query(unsigned addr)
{
    addr = htonl(addr);
    int tm = addr >> (32 - FAST_OFFSET);
    return lower_bound(fastV[tm], fastV[tm + 1], (VEntry) {addr + 1, 0})[-1].nexthop;
}

评测结果