100309. 求出出现两次数字的 XOR 值
原题链接
求出出现两次数字的 XOR 值 - 力扣 (LeetCode) 竞赛
思路分析
签到题，一次遍历
AC代码
class Solution:def duplicateNumbersXOR(self, nums: List[int]) -> int:cnt = Counter(nums)res = 0st = set(nums)for x in st:if cnt[x] == 2:res ^= xreturn res100303. 查询数组中元素的出现位置
原题链接
查询数组中元素的出现位置 - 力扣 (LeetCode) 竞赛
思路分析
记录下每个次数的位置，然后遍历一下查询就行
时间复杂度O(n)
AC代码
class Solution:def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:mp = defaultdict()s = 0for i, v in enumerate(nums):if v == x:s += 1mp[s] = ireturn [mp[v] if v in mp else -1 for v in queries]100313. 所有球里面不同颜色的数目
原题链接
所有球里面不同颜色的数目 - 力扣 (LeetCode) 竞赛
思路分析
一开始敲了个莫队的板子，又看了下题看错题了。。。没那么复杂
边遍历边执行操作，边维护每个元素出现次数，然后记录下集合中的元素就行
时间复杂度O(n)
AC代码
class Solution:def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:cnt = Counter()mp = defaultdict(int)ret = []st = set()for x, y in queries:cnt[mp[x]] -= 1if cnt[mp[x]] == 0:st.remove(mp[x])mp[x] = ycnt[y] += 1st.add(y)ret.append(len(st))return ret100314. 物块放置查询
原题链接
物块放置查询 - 力扣 (LeetCode) 竞赛
思路分析
思路就是线段树维护区间和，但是会卡常。
对原数轴重新编号
原数轴上的点i变为2 * i + 1，点与点之间的空隙也依次编号
然后空隙的权值为1，原数轴点的权值为0
在原数轴放障碍相当于将其赋值为负无穷
对于每个查询[0, x]等价于查询[1, 2 * x + 1]的最大连续子段和是否大于等于sz
我们只需要用线段树维护最大连续子段和即可
只涉及单点修改和区间查询，时间复杂度为O(nlogn)
由于拆点，区间长度为1e5量级，但是竟然被卡常了？
加个快读和吸氧才过
掉大分！！！
AC代码
#pragma GCC optimize(2)
const int N = 1e5 + 10;
#define lc p << 1
#define rc p << 1 | 1
struct node{int l, r;long long sum, lma, rma, ma;
}tr[N << 2];int n, m, a[N];void pushup(node& p, node& l, node& r){p.sum = l.sum + r.sum;p.lma = max(l.lma, l.sum + r.lma);p.rma = max(r.rma, r.sum + l.rma);p.ma = max(l.rma + r.lma, max(l.ma, r.ma));
}void build(int p, int l, int r){tr[p] = { l, r, 0, 0, 0, 0 };if(l == r){if (l % 2 == 0) tr[p] = { l, l, 1, 1, 1, 1 };return;}int mid = l + r >> 1;build(lc, l, mid), build(rc, mid + 1, r);pushup(tr[p], tr[lc], tr[rc]);
}node query(int p, int l, int r){if(l <= tr[p].l && tr[p].r <= r)return tr[p];int mid = tr[p].l + tr[p].r >> 1;if(r <= mid) return query(lc, l, r);else if(l > mid) return query(rc, l, r);node left = query(lc, l, r);node right = query(rc, l, r);node ret = { 0 };pushup(ret, left, right);return ret;
}void update(int p, int x, int k){ //点修if(tr[p].l == x && tr[p].r == x){tr[p] = { x, x, k, k, k, k };return;}int mid = tr[p].l + tr[p].r >> 1;if(x <= mid) update(lc, x, k);else update(rc, x, k);pushup(tr[p], tr[lc], tr[rc]);
}class Solution {
public:Solution() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);}vector<bool> getResults(vector<vector<int>>& queries) {memset(tr, 0, sizeof tr);build(1, 1, N);vector<bool> ret;for (auto& v : queries) {int op = v[0];if (op == 1) {update(1, v[1] * 2 + 1, -1e8);}else {auto t = query(1, 1, v[1] * 2 + 1);ret.push_back(t.ma >= v[2]);}}return ret;}
};
