题目链接
http://118.190.20.162/view.page?gpid=T162
题意
一个网络地址由 \(n\) (\(n \leq 512\) ，且是16的倍数)位二进制位组成（形如 xxxx:xxxx: .... :xxxx），有若干用户需要申请一些网络地址。
有三种操作：
- 申请。给出一个用户编号，和要查询的地址区间[L, R]，若全都没有被申请过，或者之前有一部分（不能是全部）被此用户申请过，输出YES，否则输出NO
- 单点查询。查询某地址p，返回申请者的编号，没有人申请过返回0
- 区间查询。查询地址区间[L, R]是否全部被某用户申请过，若是返回申请者编号，否返回0
一共有 \(q(q \leq 50000)\) 次操作
思路
20分做法
\(n \leq 16，q \leq 200\)，暴力枚举即可
100分做法
别问，问就是其他做法我不会
因为网络地址的范围很大（$ \leq 2^{512}$），而询问的数量是比较可观的，因此可以想到离散化。
这题的网络地址有一个特点，就是如果当作字符串读入的话，字符串的字典序和地址按照大小排列的顺序一致；还有一点需要注意，如果离散化之前的区间是[1,2],[4,5],离散化之后会变成[1,2],[3,4],从不连续变成了连续的，所以在离散化的时候需要把区间右端点+1的位置也一起排序，注意+1导致的地址进位问题。
具体步骤是先把网络地址以字符串的形式全部读入，直接用sort排好序，然后用lower_bound函数查找，用得到的下标给地址重新赋值
cin >> n >> q;
for(int i = 1; i <= q; i++) {
cin >> op[i];
if(op[i] == 1) {
cin >> id[i] >> l[i] >> r[i];
tem[++cnt] = l[i]; tem[++cnt] = r[i];
if(!s_f(r[i])) tem[++cnt] = nex(r[i]);
}
else if(op[i] == 2) {
cin >> s[i];
tem[++cnt] = s[i];
}
else {
cin >> l[i] >> r[i];
tem[++cnt] = l[i]; tem[++cnt] = r[i];
if(!s_f(r[i])) tem[++cnt] = nex(r[i]);
}
}
sort(tem + 1, tem + cnt + 1);
int k = unique(tem + 1, tem + cnt + 1) - tem - 1;
build(1, 1, k);
for(int i = 1; i <= q; i++) {
if(op[i] == 1) {
L[i] = lower_bound(tem + 1, tem + k + 1, l[i]) - tem;
R[i] = lower_bound(tem + 1, tem + k + 1, r[i]) - tem;
int cnt = qry(1, 1, k, L[i], R[i]), mn = qry_min(1, 1, k, L[i], R[i]), mx = qry_max(1, 1, k, L[i], R[i]);
if(cnt == 0 || mn == mx && mn == id[i] && cnt < R[i] - L[i] + 1) {
cout << "YES\n";
upd(1, 1, k, L[i], R[i], id[i]);
}
else cout << "NO\n";
}
else if(op[i] == 2) {
L[i] = lower_bound(tem + 1, tem + k + 1, s[i]) - tem;
int ans = qry_max(1, 1, k, L[i], L[i]);
cout << ((ans > 0 && ans <= k) ? ans : 0) << endl;
}
else {
L[i] = lower_bound(tem + 1, tem + k + 1, l[i]) - tem;
R[i] = lower_bound(tem + 1, tem + k + 1, r[i]) - tem;
int cnt = qry(1, 1, k, L[i], R[i]), mn = qry_min(1, 1, k, L[i], R[i]), mx = qry_max(1, 1, k, L[i], R[i]);
if(mn == mx && cnt == R[i] - L[i] + 1 && mn > 0) cout << mn << endl;
else cout << 0 << endl;
}
}
这样就把范围很大的地址映射到1e5量级了。
因为操作涉及到区间，区间查询、区间修改、单点查询，很容易想到线段树这一数据结构。
用t[rt]代表一个树上结点，v表示这个结点内被申请了的地址个数，mn mx代表申请了这块地址范围的申请人编号的最小值、最大值，lazy就是懒标记
操作一：
区间查询
YES的情况：v == 0 || (v < r - l + 1 && mn == mx && mn == id)，然后还要upd这个区间的值为id
否则是NO
操作二:
单点查询p位置的编号
操作三：
区间查询
有答案的情况：mn == mx && mn > 0 && v == r - l + 1
否则是0
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, q, op[N], id[N], cnt, L[N], R[N];
string l[N], r[N], s[N], tem[N << 1];
struct SegTree{
int v; // 区间内被用过的值的个数
int lazy;
int mn, mx; // 区间内最小 最大id
}t[N << 2];
void push_up(int rt) {
t[rt].v = t[rt * 2].v + t[rt * 2 + 1].v;
t[rt].mn = min(t[rt * 2].mn, t[rt * 2 + 1].mn);
t[rt].mx = max(t[rt * 2].mx, t[rt * 2 + 1].mx);
}
void build(int rt, int l, int r) {
t[rt].lazy = 0;
if(l == r) {
t[rt].v = 0;
t[rt].mn = 1e9; t[rt].mx = -1e9;
return;
}
int mid = (l + r) >> 1;
build(rt * 2, l, mid);
build(rt * 2 + 1, mid + 1, r);
push_up(rt);
}
void push_down(int rt, int lenl, int lenr) {
if(t[rt].lazy) {
t[rt * 2].v = lenl;
t[rt * 2 + 1].v = lenr;
t[rt * 2].lazy = t[rt].lazy;
t[rt * 2 + 1].lazy = t[rt].lazy;
t[rt * 2].mn = t[rt * 2].mx = t[rt].lazy;
t[rt * 2 + 1].mn = t[rt * 2 + 1].mx = t[rt].lazy;
t[rt].lazy = 0;
}
}
void upd(int rt, int l, int r, int L, int R, int v) {
if(l > r || l > R || L > r) return;
if(L <= l && r <= R) {
t[rt].v = r - l + 1;
t[rt].mn = t[rt].mx = v;
t[rt].lazy = v;
return;
}
int mid = (l + r) >> 1;
push_down(rt, mid - l + 1, r - mid);
upd(rt * 2, l, mid, L, R, v);
upd(rt * 2 + 1, mid + 1, r, L, R, v);
push_up(rt);
}
int qry_min(int rt, int l, int r, int L, int R) {
if(l > r || l > R || L > r) return 1e9;
if(L <= l && r <= R) return t[rt].mn;
int mid = (l + r) >> 1;
push_down(rt, mid - l + 1, r - mid);
return min(qry_min(rt * 2, l, mid, L, R), qry_min(rt * 2 + 1, mid + 1, r, L, R));
}
int qry_max(int rt, int l, int r, int L, int R) {
if(l > r || l > R || L > r) return -1e9;
if(L <= l && r <= R) return t[rt].mx;
int mid = (l + r) >> 1;
push_down(rt, mid - l + 1, r - mid);
return max(qry_max(rt * 2, l, mid, L, R), qry_max(rt * 2 + 1, mid + 1, r, L, R));
}
int qry(int rt, int l, int r, int L, int R) {
if(l > r || l > R || L > r) return 0;
if(L <= l && r <= R) return t[rt].v;
int mid = (l + r) >> 1;
push_down(rt, mid - l + 1, r - mid);
return qry(rt * 2, l, mid, L, R) + qry(rt * 2 + 1, mid + 1, r, L, R);
}
inline bool s_f(string s) {
for(auto ch : s) {
if(ch == ':') continue;
if(ch != 'f') return 0;
}
return 1;
}
inline string nex(string s) {
bool f = 0;
for(int i = s.length() - 1; i >= 0; i--) {
if(s[i] == ':') continue;
if(s[i] == 'f') s[i] = '0';
else if(s[i] >= 'a') s[i] += 1, f = 1;
else if(s[i] == '9') s[i] = 'a', f = 1;
else s[i] += 1, f = 1;
if(f) break;
}
return s;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> q;
for(int i = 1; i <= q; i++) {
cin >> op[i];
if(op[i] == 1) {
cin >> id[i] >> l[i] >> r[i];
tem[++cnt] = l[i]; tem[++cnt] = r[i];
if(!s_f(r[i])) tem[++cnt] = nex(r[i]);
}
else if(op[i] == 2) {
cin >> s[i];
tem[++cnt] = s[i];
}
else {
cin >> l[i] >> r[i];
tem[++cnt] = l[i]; tem[++cnt] = r[i];
if(!s_f(r[i])) tem[++cnt] = nex(r[i]);
}
}
sort(tem + 1, tem + cnt + 1);
int k = unique(tem + 1, tem + cnt + 1) - tem - 1;
// cout << "K: " << k << endl; ////
build(1, 1, k);
for(int i = 1; i <= q; i++) {
if(op[i] == 1) {
L[i] = lower_bound(tem + 1, tem + k + 1, l[i]) - tem;
R[i] = lower_bound(tem + 1, tem + k + 1, r[i]) - tem;
// cout << L[i] << ' ' << R[i] << endl; //////
int cnt = qry(1, 1, k, L[i], R[i]), mn = qry_min(1, 1, k, L[i], R[i]), mx = qry_max(1, 1, k, L[i], R[i]);
// cout << cnt << ' ' << mn << ' ' << mx << endl; ///
if(cnt == 0 || mn == mx && mn == id[i] && cnt < R[i] - L[i] + 1) {
// cout << ans.size() << ' ';
cout << "YES\n";
upd(1, 1, k, L[i], R[i], id[i]);
}
else cout << "NO\n";
}
else if(op[i] == 2) {
L[i] = lower_bound(tem + 1, tem + k + 1, s[i]) - tem;
// cout << L[i] << endl; //////
int ans = qry_max(1, 1, k, L[i], L[i]);
cout << ((ans > 0 && ans <= k) ? ans : 0) << endl;
}
else {
L[i] = lower_bound(tem + 1, tem + k + 1, l[i]) - tem;
R[i] = lower_bound(tem + 1, tem + k + 1, r[i]) - tem;
// cout << L[i] << ' ' << R[i] << endl; ////
int cnt = qry(1, 1, k, L[i], R[i]), mn = qry_min(1, 1, k, L[i], R[i]), mx = qry_max(1, 1, k, L[i], R[i]);
// cout << cnt << ' ' << mn << ' ' << mx << endl; ///
if(mn == mx && cnt == R[i] - L[i] + 1 && mn > 0) cout << mn << endl;
else cout << 0 << endl;
}
}
return 0;
}