请用C++写一个单点定位差分乘序
时间: 2023-12-27 22:21:00 浏览: 41
以下是使用C++编写的单点定位差分乘序的代码:
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int n;
int c[maxn], d[maxn], f[maxn], g[maxn];
int ans[maxn], tree[maxn];
int lowbit(int x) {
return x & (-x);
}
void update(int x, int val) {
while (x <= n) {
tree[x] += val;
x += lowbit(x);
}
}
int query(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x -= lowbit(x);
}
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
d[i] = c[i] - c[i - 1];
f[i] = f[i - 1] + d[i];
g[i] = g[i - 1] + f[i];
}
for (int i = n; i >= 1; i--) {
ans[i] = query(n) - query(g[i]);
update(g[i] + 1, 1);
}
for (int i = 1; i <= n; i++) {
printf("%d ", ans[i]);
}
printf("\n");
return 0;
}
```
其中`lowbit`函数用于求出一个整数的二进制表示中最低位1所对应的值,`update`函数用于更新树状数组,`query`函数用于查询树状数组中某个区间的和。
代码中首先读入数组`c`,然后计算出数组`d`、`f`和`g`。其中,数组`d`表示相邻两个数之间的差值,数组`f`表示前缀和数组,数组`g`表示前缀和数组的前缀和。
接下来,从`n`到1依次遍历数组`g`,用树状数组求出数组`ans`的值。最后输出数组`ans`即为所求的结果。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)