本文共 1323 字，大约阅读时间需要 4 分钟。
有N个人排队，每一个人都有一个val来对应，每一个后来人都会插入当前队伍的某一个位置pos。要求把队伍最后的状态输出。
刚开始想不到线段树，看了题解之后还是有点懵。
就是线段树的单点更新。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 2e5 + 10;int segment[MAXN*4];int a[MAXN], b[MAXN];int res[MAXN];void Push_up(int root){ segment[root] = segment[root<<1] + segment[root<<1|1];}void Build(int root, int l, int r){ if (l == r) { segment[root] = 1; return; } int mid = (l+r)/2; Build(root<<1, l, mid); Build(root<<1|1, mid+1, r); Push_up(root);}void Update(int root, int l, int r, int pos, int val){ if (l == r) { res[l] = val; segment[root] = 0; return; } int mid = (l+r)/2; if (segment[root<<1] >= pos) Update(root<<1, l, mid, pos, val); else Update(root<<1|1, mid+1, r, pos-segment[root<<1], val); Push_up(root);}int main(){ int n; while (~scanf("%d", &n)) { Build(1, 1, n); for (int i = 1;i <= n;i++) scanf("%d%d", &a[i], &b[i]); for (int i = n;i >= 1;i--) Update(1, 1, n, a[i]+1, b[i]); for (int i = 1;i <= n;i++) cout << res[i] << ' ' ; cout << endl; } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10676528.html