建一棵trie图，每次插入操作做到掩码深度即可，在结束节点打上时间标记。查询时，用一个栈来存即可，每次弹出比当前时间晚的节点，因为如果下面的节点更早出现，前面的节点就不会变化。
PS 这题考场上加了一个条件，就是掩码长度后面的数一定都是0，相当于侧面告诉你不会出现掩码长度相等且ip相等的情况。
#include<cmath>#include<cstdio>#include<vector>#include <queue>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 40000000#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;int n,tot,i,rt,cnt,a,b,c,d,e,l,r;int stk[40];struct trie{int tme,ch[2];} t[N];void insert(int &x,ll num,int dep,int len){ if (!x) x = ++tot; if (!len) {t[x].tme = cnt; return;} int p = (int)(num>>(32-dep)&1); insert(t[x].ch[p],num,dep+1,len-1);}int query(int x,ll num,int dep,int l,int r){ if (t[x].tme) { if (t[x].tme < l) stk[0] = 0; if (l <= t[x].tme & t[x].tme <= r) { while (stk[0] && stk[stk[0]] > t[x].tme) stk[0]--; stk[++stk[0]] = t[x].tme; } } if (dep == 33) return stk[0]; int p = (int)(num>>(32-dep)&1); query(t[x].ch[p],num,dep+1,l,r);}int main(){ scanf("%d",&n); fo(i,1,n) { char s[50]; scanf("%s",s); if (s[0] == 'A') { scanf("%lld.%lld.%lld.%lld/%d",&a,&b,&c,&d,&e); cnt++; insert(rt,(ll)(a<<24)+(ll)(b<<16)+(ll)(c<<8)+(ll)d,1,e); } if (s[0] == 'Q') { scanf("%lld.%lld.%lld.%lld",&a,&b,&c,&d); scanf("%d%d",&l,&r); stk[0] = 0; PRintf("%d/n",query(rt,(ll)(a<<24)+(ll)(b<<16)+(ll)(c<<8)+(ll)d,1,l,r)); } }}新闻热点
疑难解答
