链接：https://www.nowcoder.com/acm/contest/136/G
来源：牛客网
题目描述
HA实验有一套非常严密的安全保障体系，在HA实验基地的大门，有一个指纹锁。
该指纹锁的加密算法会把一个指纹转化为一个不超过1e7的数字，两个指纹数值之差越小，就说明两个指纹越相似，当两个指纹的数值差≤k时，这两个指纹的持有者会被系统判定为同一个人。
现在有3种操作，共m个，
操作1：add x，表示为指纹锁录入一个指纹，该指纹对应的数字为x，如果系统内有一个与x相差≤k的指纹，则系统会忽略这次添加操作
操作2：del x，表示删除指纹锁中的指纹x，若指纹锁中多个与x相差≤k的指纹，则全部删除，若指纹锁中没有指纹x，则可以忽略该操作，
操作3：query x，表示有一个持有指纹x的人试图打开指纹锁，你需要设计一个判断程序，返回该人是否可以打开指纹锁（只要x与存入的任何一个指纹相差≤k即可打开锁）。
初始状态，指纹锁中没有任何指纹。
现在有3种操作，共m个，
操作1：add x，表示为指纹锁录入一个指纹，该指纹对应的数字为x，如果系统内有一个与x相差≤k的指纹，则系统会忽略这次添加操作
操作2：del x，表示删除指纹锁中的指纹x，若指纹锁中多个与x相差≤k的指纹，则全部删除，若指纹锁中没有指纹x，则可以忽略该操作，
操作3：query x，表示有一个持有指纹x的人试图打开指纹锁，你需要设计一个判断程序，返回该人是否可以打开指纹锁（只要x与存入的任何一个指纹相差≤k即可打开锁）。
初始状态，指纹锁中没有任何指纹。
输入描述:
第一行有2个正整数m，k。
接下来m行，每行描述一种操作：add x，del x或query x。
输出描述:
对于每个query操作，输出一行，包含一个单词“Yes”或“No”，表示该人是否可以打开指纹锁。 法一： set集合的运用：重要---erqase 的使用 不知道问什么c++11超时，c++14就ok了。
#include <bits/stdc++.h>
using namespace std;
set <int> e;
set <int>::iterator it,t;
int n, k;
int main ()
{
scanf ("%d %d", &n,&k);
char str[]; int x;
for (int i = ; i <= n; i++) {
scanf (" %s %d", str, &x);
if (str[] == 'a') {
it = e.lower_bound(x - k);
if (it == e.end() || x + k < *it)
e.insert(x);
}
else if (str[] == 'q') {
it = e.lower_bound(x - k);
if (it == e.end() || x + k < *it) puts("No");
else puts("Yes");
}
else {
it = e.lower_bound(x - k);
t=it;
while (it != e.end() && (*it <= x + k)) it++;
e.erase(t,it);
}
}
return ;
}
法二： 动态线段树超时（95%通过率）
#include <bits/stdc++.h>
using namespace std;
#define ln t[rt].lson
#define rn t[rt].rson
#define ls l,m,ln
#define rs m+1,r,rn
const int N = 1e6 + ;
const int M = 1e7 + ;
struct node {
int sum;
int lson, rson;
int tag;
};
node t[N * ]; int cnt;
int n, k;
inline void newnode (int &rt) {
rt = ++cnt;
t[rt].sum = t[rt].tag = ;
ln = rn = -;
}
inline void pushup (int rt) {
t[rt].sum = t[ln].sum + t[rn].sum;
}
void pushdown (int rt) {
if (t[rt].tag) {
t[ln].tag = t[rn].tag = ;
t[ln].sum = t[rn].sum = ;
t[rt].tag = ;
}
}
void update (int L, int R, int x, int l, int r, int rt ) {
if (l > R || r < L) return ;
if (l >= L && r <= R) {
t[rt].sum = x;
t[rt].tag = (x + ) % ;
return ;
}
if (ln < ) {
newnode(ln);
newnode(rn);
}
pushdown(rt);
int m = (l + r) / ;
update (L, R, x, ls);
update (L, R, x, rs);
pushup(rt);
return ;
}
bool query (int L, int R, int l, int r, int rt) {
if (t[rt].sum == || l > R || r < L) return ;
if (l >= L && r <= R) return t[rt].sum > ;
if (ln < ) {
newnode(ln);
newnode(rn);
}
pushdown(rt);
int m = (l + r) / ;
return query(L, R, ls) || query(L, R, rs); }
int main ()
{
scanf ("%d %d", &n, &k) ;
char str[]; int x;
int rt; newnode (rt);
for (int i = ; i <= n; i++) {
scanf (" %s %d", str, &x);
x += M;
int t1 = max (, x - k);
int t2 = min (x + k, * M);
if (str[] == 'a') {
if ( !query (t1, t2, , * M, ) )
update (x, x, , , * M, );
}
else if (str[] == 'q') {
if ( query (t1, t2, , * M, ) ) puts("Yes");
else puts("No");
}
else update (t1, t2, , , * M, );
}
return ;
}
法三：因为连续k个元素且（x/k)值相同的数同一时间只存在一个。。。
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+;
int isok[*N];
int n,k;
bool ask (int x) {
int t=x/k;
if (isok[t]) return ;
if (isok[t-]&&abs(x-isok[t-])<=k) return ;
if (isok[t+]&&abs(x-isok[t+])<=k) return ;
return ;
}
int main ()
{
scanf ("%d %d",&n,&k);
char str[]; int x;
for (int i=;i<=n;i++) {
scanf (" %s %d",str,&x);
x+=N;
if (str[]=='a') {
if (!ask(x)) isok[x/k]=x;
}
else if (str[]=='q') {
if (ask(x)) puts("Yes");
else puts("No");
}
else {
int t=x/k;
if (isok[t]) isok[t]=;
if (isok[t-]&&abs(x-isok[t-])<=k) isok[t-]=;
if (isok[t+]&&abs(x-isok[t+])<=k) isok[t+]=;
}
}
return ;
}