摘要
Title: 1242. 修改数组
Tag: 并查集、树状数组、二分
Memory Limit: 64 MB
Time Limit: 1000 ms

1242. 修改数组

题意

见原题
思路
- 并查集单链表用法
  将前面枚举过的元素用一个集合来表示，集合的根元素是集合所有元素的最大值
- 树状数组+二分
  可以观察到，定义 $f(x)$ 函数，为该数减去前面被标记的数， $f(x) = x - s[x]$ 的值是单调递增的
  我们需要找出最靠左的，且严格大于 $f(x)$ 的数
  比如现在是2, 4被标记了，那么 $f(x)$ 的状态为： $x: 1, 2, 3, 4, 5, 6, 7, 8 \\ f: 1, 1, 2, 2, 3, 4, 5 ,6$ 如果此时问2，而2已经被标记了，那么就找严格大于 $f(2-1)$ 的数，即3

代码

并查集

'''
Author: NEFU AB-IN
Date: 2022-04-05 16:45:40
FilePath: \ACM\Acwing\1242.py
LastEditTime: 2022-04-05 16:45:40
'''
import sys

sys.setrecursionlimit(int(2e9))

N = int(1e6 + 10)
fa = [i for i in range(N)]


def find(x):
    if x != fa[x]:
        fa[x] = find(fa[x])
    return fa[x]


n = int(input())
a = list(map(int, input().split()))

for i in range(n):
    x = find(a[i])
    a[i] = x
    fa[x] = x + 1

for i in a:
    print(i, end=" ")

树状数组+二分

'''
Author: NEFU AB-IN
Date: 2022-04-05 18:21:40
FilePath: \ACM\Acwing\1242.1.py
LastEditTime: 2022-04-05 18:37:26
'''
N = int(1e6 + 10)
Matrix = lambda: [0] * N
lowbit = lambda x: x & -x
tr, a = Matrix(), Matrix()


def add(x, d):
    i = x
    while i < N:
        tr[i] += d
        i += lowbit(i)


def query(x):
    i, ans = x, 0
    while i:
        ans += tr[i]
        i -= lowbit(i)
    return ans


def check(l, r):
    return r - query(r) > (l - 1) - query(l - 1)


n = int(input())
a = list(map(int, input().split()))
a = [0, *a]

for i in range(1, n + 1):
    l, r = a[i], N
    while l < r:
        mid = l + r >> 1
        if check(a[i], mid):
            r = mid
        else:
            l = mid + 1
    print(r, end=" ")
    add(r, 1)

1242. 修改数组

题意

思路

代码