搜狗面试题——密码生成 100分 离散化+线段树区间赋值
密码生成
http://www.nowcoder.com/questionTerminal/96bf0c548a094de7a05919e0b32b1a5a
C++100分代码通过，真的太不容易了
题面
链接：https://www.nowcoder.com/questionTerminal/96bf0c548a094de7a05919e0b32b1a5a
来源：牛客网
小汪作为一个有数学天分的程序猿，设计了一套密码生成器来搞定自己的密码问题。
密码生成器由N个槽位组成，槽位的下标为0~N-1，每个槽位存储一个数。起初每个槽位都是0。
密码生成器会进行M轮计算，每轮计算，小汪会输入两个数L,R(L<=R),密码生成器会将这两个数作为下标，将两个下标之间（包含）的所有槽位赋值为i（i为当前的轮次，i∈[1,M]）。
M轮计算完成后，密码生成器会根据槽位的最终值生成一条密码，密码的生成规则为：
（0*a[0] + 1*a[1] + 2*a[2] + ... + (N-1)*a[N-1]) mod 100000009
其中a[i]表示第i个槽位的最终值。
请帮助小汪把他的密码生成器实现为代码。
输入描述:
第一行为两个整数N,M,表示槽位个数和计算轮数。
接下来M行，每行两个整数Li,Ri，表示第i轮计算的输入。
输出描述:
输出一行，一个整数A,表示小汪的开机密码。
示例1
输入
5 3 2 3 1 2 1 1
输出
10
说明
对于输入样例，密码生成过程如下：
初始： 0 0 0 0 0 第1轮：0 0 1 1 0 第2轮：0 2 2 1 0 第3轮：0 3 2 1 0
密码生成器最终生成 0 3 2 1 0，则密码为(0*0 + 3*1 + 2*2 + 1*3 + 0*4) mod 100000009 = 10
备注:
mod 表示取余操作，a mod b表示a,b相除得到的余数
对于前30%的测试数据，保证 N,M<=10000
对于前50%的测试数据，保证 N,M<=200000
对于100%的测试数据，保证 N<=1.5*10^7,M<=200000
思路
那么本题的正解是采用离散化+线段树
首先区间赋值很容易想到的是线段树，而纯线段树会爆空间，只能拿到50分，如果写动态开点线段树没准会过，先上一个50分代码...
50分代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Lchild(x) ((x) << 1)
#define Rchild(x) (((x) << 1) + 1)
using namespace std;
typedef long long ll;
const ll MOD = 100000009;
const int maxn = 15000010;
inline void write(ll x) {
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
inline int read() {
int k = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') {
if (c == '-')f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
k = (k << 1) + (k << 3) + c - 48;
c = getchar();
}
return k * f;
}
struct op {
int l, r, c;
}a[maxn];
//[l, r]的区间和
inline ll sum(ll l, ll r) { return (l + r) * (r - l + 1) / 2; }
int n, m;
int x[maxn << 1], x_size, realx_size, c[maxn << 1];
int L, R;
ll ans;
struct SegmentTree {
struct Node {
int value, tag_Set;
}nodes[maxn << 2];
SegmentTree() {
memset(nodes, 0, sizeof(nodes));
}
inline void pushup(int root) {
nodes[root].value = nodes[Lchild(root)].value + nodes[Rchild(root)].value;
}
inline void build(int root, int l, int r) {
nodes[root].tag_Set = 0;
if (l == r)nodes[root].value = 0;
else {
int m = (l + r) >> 1;
build(Lchild(root), l, m);
build(Rchild(root), m + 1, r);
pushup(root);
}
}
inline void pushdown(int root, int l, int r) {
int m = (l + r) >> 1;
if (nodes[root].tag_Set) {
nodes[Lchild(root)].tag_Set = nodes[Rchild(root)].tag_Set = nodes[root].tag_Set;
nodes[Lchild(root)].value = (m - l + 1) * nodes[root].tag_Set;
nodes[Rchild(root)].value = (r - m) * nodes[root].tag_Set;
nodes[root].tag_Set = 0;
}
}
inline void updateSet(int root, int curl, int curr, int tarl, int tarr, int k) {
if (tarr < curl || curr < tarl)return;
if (tarl <= curl && curr <= tarr) {
nodes[root].tag_Set = k;
nodes[root].value = (curr - curl + 1) * k;
return;
}
pushdown(root, curl, curr);
int m = (curl + curr) >> 1;
if (tarl <= m) updateSet(Lchild(root), curl, m, tarl, tarr, k);
if (tarr > m) updateSet(Rchild(root), m + 1, curr, tarl, tarr, k);
pushup(root);
}
inline int query(int root, int curl, int curr, int tarl, int tarr) {
if (tarr < curl || curr < tarl)return 0;
if (tarl <= curl && curr <= tarr) {
return nodes[root].value;
}
pushdown(root, curl, curr);
int m = (curl + curr) >> 1;
int ret = 0;
if (tarl <= m) ret += query(Lchild(root), curl, m, tarl, tarr);
if (tarr > m) ret += query(Rchild(root), m + 1, curr, tarl, tarr);
return ret;
}
};
SegmentTree tree;
int main() {
n = read(), m = read();
tree.build(1, 1, n);
for (int i = 1; i <= m; ++i) {
L = read() + 1, R = read() + 1;
tree.updateSet(1, 1, n, L, R, i);
}
for (int i = 0; i < n; ++i)
ans = (ans + 1ll * tree.query(1, 1, n, i + 1, i + 1) * i) % MOD;
write(ans);
} 那么考虑到数据范围，我们需要对区间进行离散化，把所有的端点坐标罗列下来，排序去重
比如说一共4个坐标点
1 4 6 10000000000
我们就可以映射到
1 2 3 4
然后接下来，只需要在赋值的时候直接在离散化的点上操作就可以
但是这样只能拿到20分，还有一个小问题
就是当我们的赋值是在1到4和6到10000000000的时候，就会忽略掉5会怎么样
所以当相邻两个点x和y的差大于1的时候，我们需要将x+1和y-1同时加入离散化的坐标数组，再做一次排序去重
100分代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Lchild(x) ((x) << 1)
#define Rchild(x) (((x) << 1) + 1)
using namespace std;
typedef long long ll;
const ll MOD = 100000009;
const int maxn = 1000010;
inline void write(ll x) {
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
inline int read() {
int k = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') {
if (c == '-')f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
k = (k << 1) + (k << 3) + c - 48;
c = getchar();
}
return k * f;
}
struct op {
int l, r;
}a[maxn];
//[l, r]的区间和
inline ll sum(ll l, ll r) {return (l + r) * (r - l + 1) / 2;}
int n, m;
int x[maxn << 1], x_size, realx_size, c[maxn << 1];
int L, R;
ll ans;
struct SegmentTree {
struct Node {
int value, tag_Set;
}nodes[maxn << 3];
SegmentTree() {
memset(nodes, 0, sizeof(nodes));
}
inline void pushup(int root) {
nodes[root].value = nodes[Lchild(root)].value + nodes[Rchild(root)].value;
}
inline void build(int root, int l, int r) {
nodes[root].tag_Set = 0;
if (l == r)nodes[root].value = 0;
else {
int m = (l + r) >> 1;
build(Lchild(root), l, m);
build(Rchild(root), m + 1, r);
pushup(root);
}
}
inline void pushdown(int root, int l, int r) {
int m = (l + r) >> 1;
if(nodes[root].tag_Set) {
nodes[Lchild(root)].tag_Set = nodes[Rchild(root)].tag_Set = nodes[root].tag_Set;
nodes[Lchild(root)].value = (m - l + 1) * nodes[root].tag_Set;
nodes[Rchild(root)].value = (r - m) * nodes[root].tag_Set;
nodes[root].tag_Set = 0;
}
}
inline void updateSet(int root, int curl, int curr, int tarl, int tarr, int k) {
if (tarr < curl || curr < tarl)return;
if (tarl <= curl && curr <= tarr) {
nodes[root].tag_Set = k;
nodes[root].value = (curr - curl + 1) * k;
return;
}
pushdown(root, curl, curr);
int m = (curl + curr) >> 1;
if (tarl <= m) updateSet(Lchild(root), curl, m, tarl, tarr, k);
if (tarr > m) updateSet(Rchild(root), m + 1, curr, tarl, tarr, k);
pushup(root);
}
inline int query(int root, int curl, int curr, int tarl, int tarr) {
if (tarr < curl || curr < tarl)return 0;
if (tarl <= curl && curr <= tarr) {
return nodes[root].value;
}
pushdown(root, curl, curr);
int m = (curl + curr) >> 1;
int ret = 0;
if (tarl <= m) ret += query(Lchild(root), curl, m, tarl, tarr);
if (tarr > m) ret += query(Rchild(root), m + 1, curr, tarl, tarr);
return ret;
}
};
SegmentTree tree;
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
x[++x_size] = a[i].l = read();
x[++x_size] = a[i].r = read();
}
sort(x + 1, x + x_size + 1);
realx_size = unique(x + 1, x + x_size + 1) - x - 1;
x_size = realx_size;
for(int i = 2; i <= x_size; ++i)
if(x[i] - x[i - 1] > 1) x[++realx_size] = x[i] - 1, x[++realx_size] = x[i - 1] + 1;
x_size = realx_size;
sort(x + 1, x + x_size + 1);
realx_size = unique(x + 1, x + x_size + 1) - x - 1;
tree.build(1, 1, realx_size);
for(int i = 1; i <= m; ++i) {
L = lower_bound(x + 1, x + realx_size + 1, a[i].l) - x;
R = lower_bound(x + 1, x + realx_size + 1, a[i].r) - x;
tree.updateSet(1, 1, realx_size, L, R, i);
}
for(int i = 1; i <= realx_size; ++i)
c[i] = tree.query(1, 1, realx_size, i, i);
for(int i = 1; i < realx_size; ++i)
ans = (ans + sum(x[i], x[i + 1] - 1) * (1ll * c[i])) % MOD;
ans = (ans + x[realx_size] * (1ll * c[realx_size])) % MOD;
write(ans);
} 
查看26道真题和解析
投递中国农业发展银行等公司10个岗位 >
拼多多集团-PDD公司氛围 517人发布