题目描述
维护序列
支持单点修改,查询序列第一个前缀和大于等于x的下标
保证元素非负
书上做法用树状数组+倍增
对于我这种不怎么会写倍增的很不友好,所以第二遍写的时候采用线段树上二分的写法
复杂度仍是nlogn,类似后面可持久化线段树上利用线段树对下标的划分信息,代替了在外面套二分
线段树的划分信息适合二分,树状数组的划分信息适合倍增
分块什么都不适合
算法1
(暴力枚举) $O(n^2)$
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define rint register int
#define lint long long
#define putint(x) printf("%d\n", (x))
#define isnum(x) ('0' <= (x) && (x) <= '9')
template<typename tint>
inline void readint(tint& x) {
int f = 1; char ch = getchar(); x = 0;
for(; !isnum(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isnum(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
}
using namespace std;
const int maxn = 100000 + 10;
const int maxnode = 2 * maxn;
const int inf = 1e9;
int n;
int arr[maxn], ans[maxn];
struct Smt{
int sum[maxnode], lson[maxnode], rson[maxnode];
int totnode, root;
void pushup(int p) {
if(p == 0) return;
sum[p] = sum[lson[p]] + sum[rson[p]];
}
void build(int& p, int l, int r) {
if(p == 0) p = ++totnode;
if(l == r) { sum[p] = 1; return; }
int mid = (l + r) >> 1;
build(lson[p], l, mid), build(rson[p], mid+1, r);
pushup(p);
}
void add(int& p, int l, int r, int pos, int x) {
if(p == 0) p = ++totnode;
if(l == r) { sum[p] += x; return; }
int mid = (l + r) >> 1;
if(pos <= mid) add(lson[p], l, mid, pos, x);
if(pos > mid) add(rson[p], mid+1, r, pos, x);
pushup(p);
}
// 查询区间前缀和至少为x的最小下标
int ask(int& p, int l, int r, int x) {
if(p == 0) return -1;
if(l == r) return l;
int mid = (l + r) >> 1;
if(x <= sum[lson[p]]) return ask(lson[p], l, mid, x);
return ask(rson[p], mid+1, r, x - sum[lson[p]]);
}
}smt;
int main() {
readint(n);
for(rint i=2; i<=n; i++) readint(arr[i]), arr[i]++;
arr[1]++;
smt.build(smt.root, 1, n);
for(rint i=n; i>=1; i--) {
ans[i] = smt.ask(smt.root, 1, n, arr[i]);
smt.add(smt.root, 1, n, ans[i], -1);
}
for(rint i=1; i<=n; i++) printf("%d\n", ans[i]);
return 0;
}
分块大法好!!!(传教中)