[TIOJ] 1998. 網路遮罩

題目連結:http://tioj.infor.org/problems/1998

---

可以發現其實每個IP都是一個32-bit的東東，所以可以直接用個unsigned int或long long存下來。而遮罩的那個區間其實就是那些x全填0到全填1，而我們要詢問一堆IP是不是在一堆區間內，其實就直接把那些區間當作區間加值，那查詢就只要查詢那個點是不是大於一就好了。不過因為範圍有點大，要先離散化掉就是了。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ALL(x) begin(x), end(x)
typedef long long lld;
typedef pair<lld,lld> PLL;
#define FF first
#define SS second
const int M = 200000 + 5;
const int N = 300000 + 5;

class LiSan{
	private:
		vector<lld> vv;
	public:
		inline void init(){vv.clear();}
		inline void insert(lld x){vv.PB(x);}
		inline void done(){
			sort(ALL(vv));
			vv.resize(distance(vv.begin(), unique(ALL(vv))));
		}
		inline int size(){return vv.size();}
		inline int get(lld x){
			return distance(vv.begin(), lower_bound(ALL(vv), x));
		}
} lisan;

PLL msk[M];
lld que[N];
int arr[2*M+N];

int main(){
	lisan.init();
	int m, n; scanf("%d%d",&m,&n);
	for(int i=0;i<m;i++){
		int a, b, c, d, x; scanf("%d.%d.%d.%d/%d",&a,&b,&c,&d,&x);
		lld ret = a;
		ret = ret*256 + b;
		ret = ret*256 + c;
		ret = ret*256 + d;
		bitset<32> bb(ret);
		for(int _=0;_<32-x;_++) bb[_]=0;
		msk[i].FF = bb.to_ulong();
		lisan.insert(msk[i].FF);
		for(int _=0;_<32-x;_++) bb[_]=1;
		msk[i].SS = bb.to_ulong();
		lisan.insert(msk[i].SS);
	}
	for(int i=0;i<n;i++){
		int a, b, c, d; scanf("%d.%d.%d.%d",&a,&b,&c,&d);
		lld ret = a;
		ret = ret*256 + b;
		ret = ret*256 + c;
		ret = ret*256 + d;
		que[i]=ret;
		lisan.insert(que[i]);
	}
	lisan.done();
	for(int i=0;i<m;i++){
		arr[lisan.get(msk[i].FF)]++;
		arr[lisan.get(msk[i].SS)+1]--;
	}
	int nn = lisan.size();
	for(int i=1;i<=nn;i++) arr[i]+=arr[i-1];
	for(int i=0;i<n;i++){
		int cur = lisan.get(que[i]);
		puts(arr[cur]?"TRUE":"FALSE");
	}
	return 0;
}