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;}
};
)
