深圳网站做的好的公司名称/广告关键词有哪些

注：

离散化是一种非常特殊的哈希方式，而哈希表是一般形式。
离散化想要使用时是需要保序的（即需要单调递增或者单调递减）。
↓
离散化是不改变数据相对大小的情况下对数据进行相应的缩小，而哈希表会产生哈希冲突。
哈希表是通过一个哈希函数把大的集合映射到小的集合中
离散化-排序=哈希
哈希时取模的数尽可能选择里2的整数次幂远且符合条件的质数，这样产生哈希冲突的可能性最小

拉链法

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;
const int N = 100003;
int h[N], e[N], ne[N], idx;void insert(int x)
{int k = (x % N + N) % N;e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}bool query(int x)
{int k = (x % N + N ) % N;for(int i = h[k]; ~i; i = ne[i])if(e[i] == x)return true;return false;
}int main()
{int n;scanf("%d", &n);memset(h, -1, sizeof h);while(n--){char op[2];int x;scanf("%s%d", op, &x);if(op[0] == 'I')insert(x);else{if(query(x)) puts("Yes");else puts("No");}}return 0;
}

开放寻址法

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N];int query(int x)
{int k = (x % N + N) % N;while(h[k] != null && h[k] != x){k ++;if(k == N) k = 0;}return k;
}int main()
{int n;scanf("%d", &n);memset(h, 0x3f, sizeof h);while(n--){char op[2];int x;scanf("%s%d", op, &x);if(op[0] == 'I'){int k = query(x);h[k] = x;}else{int k = query(x);if(h[k] != null) puts("Yes");else puts("No");}}return 0;
}

字符串哈希

#include <iostream>using namespace std;
typedef unsigned long long ULL;//可以免去Q=2的64次方这个麻烦的步骤//也避免了前缀值会爆的问题
const int N = 1e5 + 10, P = 131;//或者取P = 13331也可以
int n, m;
char str[N];
ULL h[N], p[N];//h为前i个字符的哈希值, p表示不同的二进制ULL get(int l, int r)
{return h[r] - h[l-1] * p[r - l + 1];
}int main()
{scanf("%d%d%s", &n, &m, str + 1);p[0] = 1;h[0] = 0;for(int i = 1; i <= n; ++i){p[i] = p[i-1] * P;h[i] = h[i-1] * P + str[i];//计算字符串前缀值,前i-1个数乘P向前移动一位//最新加入的数的权值为p的0次 所以直接加上//str[i]即可//字符和数字的计算都是最终转换成ASCII码计算//即转换成了二进制，最后得到的哈希值(或者//说h数组)还是一个数}while(m--){int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if(get(l1,r1) == get(l2, r2))  puts("Yes");else puts("No");}return 0;
}

离散化的方法（代码来源（ACWIing 802.））

#include <iostream>
#include <vector>
#include <algorithm>
//离散化的性质(标志):值域跨度很大，但是非常的稀疏，用到的数很少using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int a[N], s[N];//a是操作的值，s是前缀和
int n, m;
vector<int> alls;
vector<PII> add, query;int find(int x)//找离散化后的下标
{int l = 0, r = alls.size() - 1;while(l < r){int mid = (l + r) / 2;if(alls[mid] >= x) r = mid;else l = mid + 1;}return r + 1;//返回的是1, 2, 3, ... 不加1返回0, 1, 2, ...//这里要求前缀和，所以返回1，不然要特判的
}int main()
{//进行离散化的时候一定要记得alls数组记录的是原数组映射成了数组下标cin >> n >> m;while(n--){int x, c;cin >> x >> c;add.push_back({x, c});//先把要操作的下标和值加进add中alls.push_back(x);//往alls中加下标}while(m--){int l, r;cin >> l >> r;alls.push_back(l);//同理，把要询问的左右区间下标加上alls.push_back(r);query.push_back({l, r});//加到query中，这里要加一对了，因为是最重进行询问的数}sort(alls.begin(), alls.end());//排序alls.erase(unique(alls.begin(), alls.end()), alls.end());//去重for(auto item: add)//这里是遍历add进行操作{int x;x = find(item.first);//把下标x找到a[x] += item.second;//把对应的值加上}for(int i = 1; i <= alls.size(); ++i)s[i] = s[i-1] + a[i];//这里是遍历的数组a的下标求前缀和，因为我们上面只是对alls数组操作了x//所以数组内只有对应下标x的数组上操作了数值，剩下的l和r虽然也在alls内，但是//由于没有操作它们，所以该是啥还是啥，全局变量已经定义了，所以这些都是0，//如果恰好l或者r等于了之前的x也没关系，这说明这个区间内有的，仍然代表的是x，//只有查询的时候才会加起来，总的来说这里只有x影响了，l，r啥也没影响for(auto item: query)//开始查询{int l, r;l = find(item.first);r = find(item.second);cout << s[r] - s[l - 1] << endl;//输出前缀和就行了}return 0;
}