建一棵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;新聞熱點
疑難解答
