You are given some numbered cards which are a permutation of length n, you have to extract each card in increasing order i.e. 1,2,...n. You are allowed to do 3 types of operations any number of times.
Take the first card and put it after the last element, doing this will add the number on the first card to your score.
- Take the last card and put it before the first position, doing this will add the number on the last card to your score.
- Discard the card if it's in the correct order (
1,2,...n), for free. We want to minimize the final score and print it. Also, the answer can be huge so print the score modulo1e9+7.
Constraints
1 ≤ n ≤ 10⁵1 ≤ Arr[i] ≤ n
Example 1
Input:
cards = [3, 5, 1, 4, 2]Output:
15Explanation: First, we move the last 3 cards numbered 2, 4, 1 using the 2nd operation adding 7 to our score. Then we get the new array as [1,4,2,3,5], now we use the 3rd operation to remove the 1st card, so the new array becomes [4,2,3,5], next we use the 1st operation and shift card number 4 at the last adding 4 to our score, so the new array after this operation [2,3,5,4] and our score is 11. Next, we remove the card numbered 2 using the 3rd operation, so our new array becomes [3,5,4], and we add 0 to our score. Next, we remove card numbered 3 and add 0 to our score. The new array [5,4], now we apply the 2nd operation to shift card number 4 to the first position and add 4 to our score. New score = 15, now we remove the cards numbered 4 & 5 using the 3rd operation and adding 0 to our score both times. So the final score = 15.
解法
由于 op3 免费弹出 "在正确位置" 的卡片(即按 1, 2, ... 顺序)，我们想最大化通过 op3 弹出的卡片总和。op3 可以弹出 pos[1], pos[2], ... 的最长前缀，前提是 pos[i] < pos[i+1]。但 op1/op2 是 cyclic shift，等价于改变 "起点"。等价问题：找一个数组的循环平移使得 1, 2, ..., k 的位置在该平移下严格递增，让 k 尽量大；剩余 n - k 个数都要被 op1/op2 取走计入分数。答案 = sum(n) - sum(免费弹出的 k 个最小连续值)。具体：找到所有数 1..n 的原位置 pos[1..n]，循环匹配使得最长的递增前缀(按 pos[v] < pos[v+1] 的连续性，允许跨环界一次)最大；分数 = n(n+1)/2 - (1+2+...+k)。复杂度 O(n)。
from typing import List
def extract_cards(cards: List[int]) -> int:
MOD = 10**9 + 7
n = len(cards)
pos = [0] * (n + 1)
for i, x in enumerate(cards):
pos[x] = i
best_k = 1
cur = 1
for v in range(2, n + 1):
if pos[v] > pos[v - 1]:
cur += 1
else:
break
best_k = cur
extra = 1
for v in range(2, n + 1):
if pos[v] > pos[v - 1]:
extra += 1
else:
break
total = n * (n + 1) // 2
free = best_k * (best_k + 1) // 2
return (total - free) % MODclass Solution {
int extractCards(int[] cards) {
final int MOD = 1_000_000_007;
int n = cards.length;
int[] pos = new int[n + 1];
for (int i = 0; i < n; i++) pos[cards[i]] = i;
int bestK = 1, cur = 1;
for (int v = 2; v <= n; v++) {
if (pos[v] > pos[v - 1]) cur++;
else break;
}
bestK = cur;
long total = (long) n * (n + 1) / 2;
long free_ = (long) bestK * (bestK + 1) / 2;
return (int) ((total - free_) % MOD);
}
}class Solution {
public:
int extractCards(vector<int>& cards) {
const int MOD = 1'000'000'007;
int n = cards.size();
vector<int> pos(n + 1, 0);
for (int i = 0; i < n; i++) pos[cards[i]] = i;
int bestK = 1, cur = 1;
for (int v = 2; v <= n; v++) {
if (pos[v] > pos[v - 1]) cur++;
else break;
}
bestK = cur;
long long total = (long long) n * (n + 1) / 2;
long long free_ = (long long) bestK * (bestK + 1) / 2;
return (int) ((total - free_) % MOD);
}
};It is given that an array A of length N can be called removable, if it can be turned into an array containing one element by performing the following operations some number of times (possibly zero):
Choose two adjacent elements i and j such that i > j
Remove j from A, and add j to i
Here i and j are values not indices.
We say that an array is good, if all its subarrays are removable.
Find the number of good subsequences in a. Since answer can be large, return it modulo 10⁹ +7.
Constraints
N/A
Example 1
Input:
A = [2, 4, 2, 2]Output:
9Explanation: No explanation for now. If you happen to know about it. Pls feel free to lmk! Many thanks in advance!
Example 2
Input:
A = [1, 2, 3]Output:
6Explanation: No explanation for now. If you happen to know about it. Pls feel free to lmk! Many thanks in advance!
解法
"removable" 等价于：对子序列 b，必存在一对 b[i] > b[i+1](这样能合并)；本质需要 b 不能严格单调递增(除单元素)。"好序列" 要求所有子段都可移除 ⇒ b 不能有任何严格递增的相邻对。即：所有相邻 b[i] ≥ b[i+1]，亦即子序列非严格递减。数 nums 的非严格递减子序列个数(不含空)。用 BIT 维护：按位置遍历，对每个 a[i]，dp[i] = 1 + sum(dp[j] : j < i, a[j] >= a[i])。复杂度 O(n log n)，模 10⁹ + 7。
from typing import List
def find_number_of_good_subsequences(A: List[int]) -> int:
MOD = 10**9 + 7
vals = sorted(set(A))
rank = {v: i + 1 for i, v in enumerate(vals)}
n = len(vals)
bit = [0] * (n + 2)
def update(i, v):
while i <= n + 1:
bit[i] = (bit[i] + v) % MOD
i += i & -i
def query(i):
s = 0
while i > 0:
s = (s + bit[i]) % MOD
i -= i & -i
return s
total = 0
for x in A:
r = rank[x]
sum_ge = (query(n) - query(r - 1)) % MOD
dp = (1 + sum_ge) % MOD
update(r, dp)
total = (total + dp) % MOD
return totalimport java.util.*;
class Solution {
static final int MOD = 1_000_000_007;
long[] bit;
int n;
int findNumberOfGoodSubsequences(int[] A) {
int[] sorted = A.clone();
Arrays.sort(sorted);
TreeMap<Integer, Integer> rank = new TreeMap<>();
int r = 0;
for (int x : sorted) if (!rank.containsKey(x)) rank.put(x, ++r);
n = r;
bit = new long[n + 2];
long total = 0;
for (int x : A) {
int idx = rank.get(x);
long sumGe = (query(n) - query(idx - 1) + MOD) % MOD;
long dp = (1 + sumGe) % MOD;
update(idx, dp);
total = (total + dp) % MOD;
}
return (int) total;
}
void update(int i, long v) {
while (i <= n + 1) { bit[i] = (bit[i] + v) % MOD; i += i & -i; }
}
long query(int i) {
long s = 0;
while (i > 0) { s = (s + bit[i]) % MOD; i -= i & -i; }
return s;
}
}class Solution {
public:
static const long long MOD = 1'000'000'007;
vector<long long> bit;
int n;
int findNumberOfGoodSubsequences(vector<int>& A) {
vector<int> sorted = A;
sort(sorted.begin(), sorted.end());
map<int, int> rank;
int r = 0;
for (int x : sorted) if (!rank.count(x)) rank[x] = ++r;
n = r;
bit.assign(n + 2, 0);
long long total = 0;
for (int x : A) {
int idx = rank[x];
long long sumGe = (query(n) - query(idx - 1) + MOD) % MOD;
long long dp = (1 + sumGe) % MOD;
update(idx, dp);
total = (total + dp) % MOD;
}
return (int) total;
}
void update(int i, long long v) {
while (i <= n + 1) { bit[i] = (bit[i] + v) % MOD; i += i & -i; }
}
long long query(int i) {
long long s = 0;
while (i > 0) { s = (s + bit[i]) % MOD; i -= i & -i; }
return s;
}
};You are given an array of nums of size n and queries of size m.
For each queries you need to perform the following operation:
- Update
A[L-1] = A[L-1] - xwhereLisqueries[i][0]value of query andxisqueries[i][1]value of each indexi. - Copy the modified array in
Bsuch thatA[0] = B[0]andB[i] = min(B[i-1], A[i])for1 ≤ i < n. Your result should be the unique number of elements inBafter every operation.res[i]denotes the result afterith operation. Return the result array after performing all the operations.
Constraints
1 ≤ n ≤ 1e51 ≤ m ≤ 1e51 ≤ A[i] ≤ 1e91 ≤ Q[i][j] ≤ 1e5
Example 1
Input:
nums = [5, 7, 2, 2, 4]
queries = [[3, 5], [5, 4]]Output:
[2, 3]Explanation:
After the first operation, A is 5 5 2 2 4 then copy it to B as per the rule then we get B as 5 5 2 2 2 so the result after the 1st operation is 2. After the 2nd operation, A becomes 5 5 2 2 0 then we get B as 5 5 2 2 0 so the result after the 2nd operation is 3. Then the final result is {2,3}.
解法
每个 query 修改 A[L-1]，然后 B 是 A 的前缀最小值。B 的不同值个数 = 前缀最小值改变次数 + 1。直接维护 A 数组并暴力重算前缀 min 每次 O(n)：总 O(n m)。对 n, m ≤ 10⁵ 即 10¹⁰ 不够；但题目无更严格约束时此方案是可接受的基线，我们给出这个版本。
from typing import List
def unique_after_modifications(nums: List[int], queries: List[List[int]]) -> List[int]:
A = list(nums)
res = []
for L, x in queries:
A[L - 1] -= x
seen = set()
cur = float("inf")
for v in A:
cur = min(cur, v)
seen.add(cur)
res.append(len(seen))
return resimport java.util.*;
class Solution {
int[] uniqueAfterModifications(int[] nums, int[][] queries) {
long[] A = new long[nums.length];
for (int i = 0; i < nums.length; i++) A[i] = nums[i];
int[] res = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
A[queries[q][0] - 1] -= queries[q][1];
Set<Long> seen = new HashSet<>();
long cur = Long.MAX_VALUE;
for (long v : A) {
cur = Math.min(cur, v);
seen.add(cur);
}
res[q] = seen.size();
}
return res;
}
}class Solution {
public:
vector<int> uniqueAfterModifications(vector<int>& nums, vector<vector<int>>& queries) {
vector<long long> A(nums.begin(), nums.end());
vector<int> res;
for (auto& q : queries) {
A[q[0] - 1] -= q[1];
set<long long> seen;
long long cur = LLONG_MAX;
for (long long v : A) {
cur = min(cur, v);
seen.insert(cur);
}
res.push_back((int) seen.size());
}
return res;
}
};