# biweekly-contest-88

## A

### Statement

• 字母 `x` 的 频率 是这个字母在字符串中出现的次数。
• 必须 恰好删除一个字母，不能一个字母都不删除。

``````输入：word = "abcc"

``````

``````输入：word = "aazz"

``````

• `2 <= word.length <= 100`
• `word` 只包含小写英文字母。

You are given a 0-indexed string `word`, consisting of lowercase English letters. You need to select one index and remove the letter at that index from `word` so that the frequency of every letter present in `word` is equal.

Return `true` if it is possible to remove one letter so that the frequency of all letters in `word` are equal, and `false` otherwise.

Note:

• The frequency of a letter `x` is the number of times it occurs in the string.
• You must remove exactly one letter and cannot chose to do nothing.

Example 1:

``````Input: word = "abcc"
Output: true
Explanation: Select index 3 and delete it: word becomes "abc" and each character has a frequency of 1.
``````

Example 2:

``````Input: word = "aazz"
Output: false
Explanation: We must delete a character, so either the frequency of "a" is 1 and the frequency of "z" is 2, or vice versa. It is impossible to make all present letters have equal frequency.
``````

Constraints:

• `2 <= word.length <= 100`
• `word` consists of lowercase English letters only.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
bool equalFrequency(string word) {
auto f = vector<int>(30, 0);
for (const auto &c : word) {
++f[c - 'a'];
}

sort(all(f));
reverse(all(f));

while (!f.empty() && f.back() == 0) {
f.pop_back();
}

--f[0];

auto ok = [&]() {
int num = 0;
for (const auto &a : f) {
if (num == 0) {
num = a;
} else if (a) {
if (a != num) {
return false;
}
}
}

return true;
};

if (ok()) {
return true;
}

++f[0];
--f[f.size() - 1];

if (ok()) {
return true;
}

return false;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• `LUPrefix(int n)` 初始化一个 `n` 个视频的流对象。
• `void upload(int video)` 上传 `video` 到服务器。
• `int longest()` 返回上述定义的 最长上传前缀 的长度。

``````输入：
[[4], [3], [], [1], [], [2], []]

[null, null, 0, null, 1, null, 3]

LUPrefix server = new LUPrefix(4);   // 初始化 4个视频的上传流
server.longest();                    // 由于视频 1 还没有被上传，最长上传前缀是 0 。
server.longest();                    // 前缀 [1] 是最长上传前缀，所以我们返回 1 。
server.longest();                    // 前缀 [1,2,3] 是最长上传前缀，所以我们返回 3 。
``````

• `1 <= n <= 105`
• `1 <= video <= 105`
• `video` 中所有值 互不相同 。
• `upload` 和 `longest` 总调用 次数至多不超过 `2 * 105` 次。
• 至少会调用 `longest` 一次。

You are given a stream of `n` videos, each represented by a distinct number from `1` to `n` that you need to "upload" to a server. You need to implement a data structure that calculates the length of the longest uploaded prefix at various points in the upload process.

We consider `i` to be an uploaded prefix if all videos in the range `1` to `i` (inclusive) have been uploaded to the server. The longest uploaded prefix is the maximum value of `i` that satisfies this definition.

Implement the `LUPrefix `class:

• `LUPrefix(int n)` Initializes the object for a stream of `n` videos.
• `void upload(int video)` Uploads `video` to the server.
• `int longest()` Returns the length of the longest uploaded prefix defined above.

Example 1:

``````Input
[[4], [3], [], [1], [], [2], []]
Output
[null, null, 0, null, 1, null, 3]
Explanation
LUPrefix server = new LUPrefix(4);   // Initialize a stream of 4 videos.
server.longest();                    // Since video 1 has not been uploaded yet, there is no prefix.
// So, we return 0.
server.longest();                    // The prefix [1] is the longest uploaded prefix, so we return 1.
server.longest();                    // The prefix [1,2,3] is the longest uploaded prefix, so we return 3.
``````

Constraints:

• `1 <= n <= 105`
• `1 <= video <= 105`
• All values of `video` are distinct.
• At most `2 * 105` calls in total will be made to `upload` and `longest`.
• At least one call will be made to `longest`.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class LUPrefix {
public:
vector<int> vis;
int ix, n;

LUPrefix(int n) {
vis = vector<int>(n + 5, 0);
this->n = n;
ix = 0;
}

vis[video] = 1;
}

int longest() {
while (ix < n && vis[ix + 1] == 1) {
++ix;
}

return ix;
}
};

/**
* Your LUPrefix object will be instantiated and called as such:
* LUPrefix* obj = new LUPrefix(n);
* int param_2 = obj->longest();
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：nums1 = [2,1,3], nums2 = [10,2,5,0]

``````

``````输入：nums1 = [1,2], nums2 = [3,4]

2 ^ 5 ^ 1 ^ 6 = 0 ，所以我们返回 0 。
``````

• `1 <= nums1.length, nums2.length <= 105`
• `0 <= nums1[i], nums2[j] <= 109`

You are given two 0-indexed arrays, `nums1` and `nums2`, consisting of non-negative integers. There exists another array, `nums3`, which contains the bitwise XOR of all pairings of integers between `nums1` and `nums2` (every integer in `nums1` is paired with every integer in `nums2` exactly once).

Return the bitwise XOR of all integers in `nums3`.

Example 1:

``````Input: nums1 = [2,1,3], nums2 = [10,2,5,0]
Output: 13
Explanation:
A possible nums3 array is [8,0,7,2,11,3,4,1,9,1,6,3].
The bitwise XOR of all these numbers is 13, so we return 13.
``````

Example 2:

``````Input: nums1 = [1,2], nums2 = [3,4]
Output: 0
Explanation:
All possible pairs of bitwise XORs are nums1[0] ^ nums2[0], nums1[0] ^ nums2[1], nums1[1] ^ nums2[0],
and nums1[1] ^ nums2[1].
Thus, one possible nums3 array is [2,5,1,6].
2 ^ 5 ^ 1 ^ 6 = 0, so we return 0.
``````

Constraints:

• `1 <= nums1.length, nums2.length <= 105`
• `0 <= nums1[i], nums2[j] <= 109`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T& a, const S& b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T& a, const S& b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
int n = int(nums1.size());
int m = int(nums2.size());

int res = 0;

if (m & 1) {
for (const auto& a : nums1) {
res ^= a;
}
}

if (n & 1) {
for (const auto& b : nums2) {
res ^= b;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• `0 <= i < j <= n - 1`
• `nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff`.

``````输入：nums1 = [3,2,5], nums2 = [2,2,1], diff = 1

1. i = 0, j = 1：3 - 2 <= 2 - 2 + 1 。因为 i < j 且 1 <= 1 ，这个数对满足条件。
2. i = 0, j = 2：3 - 5 <= 2 - 1 + 1 。因为 i < j 且 -2 <= 2 ，这个数对满足条件。
3. i = 1, j = 2：2 - 5 <= 2 - 1 + 1 。因为 i < j 且 -3 <= 2 ，这个数对满足条件。

``````

``````输入：nums1 = [3,-1], nums2 = [-2,2], diff = -1

``````

• `n == nums1.length == nums2.length`
• `2 <= n <= 105`
• `-104 <= nums1[i], nums2[i] <= 104`
• `-104 <= diff <= 104`

You are given two 0-indexed integer arrays `nums1` and `nums2`, each of size `n`, and an integer `diff`. Find the number of pairs `(i, j)` such that:

• `0 <= i < j <= n - 1` and
• `nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff`.

Return the number of pairs that satisfy the conditions.

Example 1:

``````Input: nums1 = [3,2,5], nums2 = [2,2,1], diff = 1
Output: 3
Explanation:
There are 3 pairs that satisfy the conditions:
1. i = 0, j = 1: 3 - 2 <= 2 - 2 + 1. Since i < j and 1 <= 1, this pair satisfies the conditions.
2. i = 0, j = 2: 3 - 5 <= 2 - 1 + 1. Since i < j and -2 <= 2, this pair satisfies the conditions.
3. i = 1, j = 2: 2 - 5 <= 2 - 1 + 1. Since i < j and -3 <= 2, this pair satisfies the conditions.
Therefore, we return 3.
``````

Example 2:

``````Input: nums1 = [3,-1], nums2 = [-2,2], diff = -1
Output: 0
Explanation:
Since there does not exist any pair that satisfies the conditions, we return 0.
``````

Constraints:

• `n == nums1.length == nums2.length`
• `2 <= n <= 105`
• `-104 <= nums1[i], nums2[i] <= 104`
• `-104 <= diff <= 104`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

template <typename T = int>
class Hash {
public:
Hash() = default;
~Hash() {}

// You need to make sure the `x` passed in is valid,
// otherwise it will cause a runtime error.
T &operator[](int x) const {
return vec_[x - 1];
}

void Init() {
vec_.clear();
}

void Init(int n) {
Init();
vec_.reserve(n);
}

int Size() const {
return vec_.size();
}

vec_.push_back(x);
}

T Get(const T &x) const {
return lower_bound(vec_.begin(), vec_.end(), x) - vec_.begin() + 1;
}

const std::vector<T> &GetVec() const {
return vec_;
}

// After you have added all the <T> that need to be discretized,
// don't forget to call this function to deduplicate.
void Gao() {
sort(vec_.begin(), vec_.end());
vec_.erase(unique(vec_.begin(), vec_.end()), vec_.end());
}

private:
std::vector<T> vec_;
};

template <typename T>
class FenwickTree {
public:
FenwickTree() = default;

FenwickTree(const size_t n) {
arr_.reserve(n);
}

void Init(int n) {
n_ = n;
high_bit_n_ = highBit(n_);
arr_.assign(n_ + 1, 0);
}

void Add(int x, const T &v) {
for (int i = x; i <= n_; i += lowBit(i)) {
arr_[i] += v;
}
}

// query prefix sum
T Query(int x) const {
T ret = 0;

for (int i = x; i > 0; i -= lowBit(i)) {
ret += arr_[i];
}

return ret;
}

T Query(int l, int r) const {
if (l > r) {
return 0;
}

return Query(r) - Query(l - 1);
}

T QueryKth(int k) {
T p = 0;

for (int lim = 1 << (high_bit_n_); lim; lim >>= 1) {
if (p + lim <= n_ && arr_[p + lim] < k) {
p += lim;
k -= arr_[p];
}
}

return p + 1;
}

private:
int lowBit(int x) const {
return x & -x;
}

int highBit(int x) const {
int res = 0;

while (x) {
++res;
x >>= 1;
}

return res;
}

int n_, high_bit_n_;
std::vector<T> arr_;
};

Hash h;
FenwickTree<int> t;

// nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff
// nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff

class Solution {
public:
long long numberOfPairs(vector<int> &nums1, vector<int> &nums2, int diff) {
int n = int(nums1.size());

h.Init(n * 2 + 10);

ll res = 0;
auto f = vector<int>();

for (int i = 0; i < n; i++) {
f.push_back(nums1[i] - nums2[i]);
}

h.Gao();

t.Init(h.Size() + 5);

for (int i = 1; i < n; i++) {
res += t.Query(0, h.Get(f[i] + diff));
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````