力扣第 387 场周赛第四题 将元素分配到两个数组中 II 二分查找，离散化，线段树

Problem: 100246. 将元素分配到两个数组中 II

在力扣的题解

赛时没做出来，想了个排序，其实排序总假设最坏的情况即倒序，那肯定超时。当时想到线段树了，但是好久没练没搞出来QAQ，我的板子的线段树下标是从1开始的。
(新题题解力扣审的挺严，我随便写的被截了，所以乖乖算了次复杂度嘤嘤嘤~)

思路

我们可以开数组arr1,arr2来统计其中数字出现的数目（下标 i 代表数值，值arr[i]代表出现的次数），然后就可以通过区间和快速得到数组中大于某个数的数目。

因为数据是不断变化的，所以我们得使用树状数组或者线段树。

解题方法

1.离散化

由于数据范围是1~1e9，太大了，不能开1e9的数组。
但是数据量只有1e5，所以我们可以离散化来处理。

离散化后我们要再找这个数的位置，使用二分查找。

复制一个数组tmp = nums，我们对tmp进行排序，即完成的离散化。
（由于要使用线段树，所以下标从1开始。）

2.线段树

然后就是通过线段树获取区间和，我们要的是严格大于当前数的数目，找到这个数的下标，下一个位置到数组末尾这段区间的和就是数目。（可能是最后一个数，下一个位置就越界了，特殊处理一下即可）

参考线段树板子：线段树板子

复杂度

时间复杂度:

$O(nlo{g}_{2}n)$

二分$lo{g}_{2}n$,建树$nlo{g}_{2}n$,区间加$lo{g}_{2}n$，区间修改$lo{g}_{2}n$，遍历数组n，各算法间互补干扰，取最大$nlo{g}_{2}n$

空间复杂度:

$O(2^n+n)$

对于线段树数组的计算：$$1\ast 2\ast ...\ast n$$，公比为2的等比数列，$$1\ast \frac{2^n-1}{1}$$ 即 2^n
再加上原数组大小n

Code

类ST是板子；
getmid是二分找下标；
tmp是离散化后下标对应的值的数组。

#define ll long long
class Solution {
public:
	template
	class ST//segment tree
	{
		struct node
		{
			T val;
			T t;//懒标记//服务后代
			node(T v = 0) :val(v), t(0)
			{}
		};
		int n = a.size();
		vectora;
		vectord;
	public:
		void build_tree(int i, int l, int r)
		{
			if (l == r)
			{
				d[i].val = a[l];
				return;
			}
			int mid = l + (r - l) / 2;
			build_tree(i * 2, l, mid);
			build_tree(i * 2 + 1, mid + 1, r);
			d[i].val = d[i * 2].val + d[i * 2 + 1].val;
		}
		void spread(int i, int l, int r, int aiml, int aimr)
		{
			int mid = l + (r - l) / 2;
			if (d[i].t != 0 && l != r)
			{
				d[i * 2].val += d[i].t * (mid - l + 1);
				d[i * 2 + 1].val += d[i].t * (r - mid);
				d[i * 2].t += d[i].t;//可能上上次也没改
				d[i * 2 + 1].t += d[i].t;
				d[i].t = 0;
			}
		}
		T getsum(int l, int r)
		{
			return _getsum(1, 1, n, l, r);
		}
		T _getsum(int i, int l, int r, int aiml, int aimr)
		{
			if (aiml <= l && r <= aimr)//查询区间的子集全部加起来
				return d[i].val;

			//访问
			int mid = l + (r - l) / 2;
			spread(i, l, r, aiml, aimr);

			T ret = 0;
			if (aiml <= mid)
				ret += _getsum(i * 2, l, mid, aiml, aimr);
			if (aimr >= mid + 1)
				ret += _getsum(i * 2 + 1, mid + 1, r, aiml, aimr);
			return ret;

		}
		void update(int l, int r, ll val)
		{
			_update(1, 1, n, l, r, val);//加并挂标记
		}
		void _update(int i, int l, int r, int aiml, int aimr, ll val)
		{
			if (aiml <= l && r <= aimr)
			{
				d[i].val += val * (r - l + 1);
				d[i].t += val;
				return;
			}


			int mid = l + (r - l) / 2;
			spread(i, l, r, aiml, aimr);

			if (aiml <= mid)
				_update(i * 2, l, mid, aiml, aimr, val);
			if (aimr >= mid + 1)
				_update(i * 2 + 1, mid + 1, r, aiml, aimr, val);
			//我们只对叶子更新了，（别多想懒标记）
			d[i].val = d[i * 2].val + d[i * 2 + 1].val;
		}
		ST(vectorarr)
		{
			a = arr;
			n = a.size() - 1;
			d = vector((ll)pow((ll)2, (ll)log2(n) + 1 + 1) + 10);
			build_tree(1, 1, n);
		}
	};
	//
	vectortmp;
	int n;
	int getmid(int aim)
	{
		int l = 0, r = n;
		while (l < r)
		{
			int m = (l + r + 1) / 2;
			if (tmp[m] <= aim)l = m;
			else r = m - 1;
		}
		return l;
	}

	vector resultArray(vector& nums)
	{
		n = nums.size();
		//tmp = nums;
		tmp = vector(n + 1);
		for (int i = 1; i <= n; i++)
		{
			tmp[i] = nums[i - 1];
		}
		sort(tmp.begin() + 1, tmp.end());

		vectorarr1, arr2, ret;
		vectorsarr1(n+1), sarr2(n+1);
		STdemo1(sarr1), demo2(sarr2);

		arr1.push_back(nums[0]);
		arr2.push_back(nums[1]);
		int t = getmid(nums[0]);
		demo1.update(t, t, 1);
		t = getmid(nums[1]);
		demo2.update(t, t, 1);

		for (int i = 2; i < nums.size(); i++)
		{
			t = getmid(nums[i]);//这个值的下标，我们求右边数目       
			if (t == n)
			{
				if (arr1.size() <= arr2.size())
					arr1.push_back(nums[i]), demo1.update(t, t, 1);
				else
					arr2.push_back(nums[i]), demo2.update(t, t, 1);
				continue;
			}
			int r1 = demo1.getsum(t + 1, n), r2 = demo2.getsum(t + 1, n);
			if (r1 == r2)
			{
				if (arr1.size() <= arr2.size())
					arr1.push_back(nums[i]), demo1.update(t, t, 1);
				else
					arr2.push_back(nums[i]), demo2.update(t, t, 1);
			}
			else if (r1 > r2)
				arr1.push_back(nums[i]), demo1.update(t, t, 1);
			else
				arr2.push_back(nums[i]), demo2.update(t, t, 1);
		}
		ret = arr1;
		for (auto x : arr2)
			ret.push_back(x);
		return ret;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161