#P1896. 2024.8.17-第三题-数组
-
1000ms
Tried: 70
Accepted: 10
Difficulty: 8
所属公司 :
米哈游
时间 :2024年8月17日
2024.8.17-第三题-数组
思路:区间容斥计算
数据范围?
首先,据考生反应,这个题目并没有给数据范围,但是O(n2)的复杂度并过不去。那么我们就假设n , q <= 100000。
区间差分?
考虑这种区间问题一般都能用前缀和或者差分来解决。回忆求区间和,我们可以用前缀和 + 差分的方式来解决。
那么这种区间计数的问题,我们可以用前缀和 + 差分的方式来解决吗?
1.考虑如果r = n + 1 , 那么问题就是求区间[l , n]中有多少个子数组包含x。直接计算包含x不好做,反而先求不包含x的。然后用总的减去不包含的即可。所以接下来考虑区间不包含x的个数:
例如序列是...pos...x...x...x , 我们用函数query_suf(pos , x)来表示从pos开始到n中有多少个子数组不包含x。
那么我们可以先求出l到第一个x之间有多少个子数组,然后求出第一个x到第二个x之间有多少个子数组,以此类推。
这里我们用一个数组suf_no来存储,suf_no[i]表示从i到n - 1中有多少个子数组不包含arr[i]。然后我们可以用递推的方式求出suf_no。
那么query_suf可以用二分找到下一个x的位置然后加上suf_no[next_x_from_pos]即可。
特殊情况:跨区间
直接query_suf(l , x) - query_suf(r + 1 , x)就可以吗?
上面这个式子只是减去了L > r 的情况,但是没考虑L <= r 但是 R > r的情况,也就是区间跨过r的这部分答案。
乘法原理:那么就需要针对r的位置进行特殊处理。如果r位置不是x,那么我们可以考虑左边的最后一个x的位置和右边的第一个x的位置。 跨过r的子数组个数就是左边的x的位置到r的位置的长度乘以右边的x的位置到r + 1的位置的长度。
复杂度分析
预处理O(n) , 查询O(logn) , 总的O(mlogn)。
代码
python
from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
m = int(input())
# 用一个defaultdict来存储每个数字出现的位置
mp = defaultdict(list)
for i in range(n):
mp[arr[i]].append(i)
# 预处理suf_no数组,suf_no[i]表示从i到n-1中有多少个子数组不包含arr[i]
suf_no = [0] * (n + 1)
def calc (x):
# 计算等差数列前n项和的公式
return x * (x + 1) // 2
for val in mp:
g = len(mp[val])
# 对于最后一个val出现的位置,子数组数量为从该位置到结尾的等差数列项数
suf_no[mp[val][g - 1]] = calc(n - 1 - mp[val][g - 1])
for i in range(g - 2, -1, -1):
idx = mp[val][i]
nxt = mp[val][i + 1]
# 递推计算suf_no数组
suf_no[idx] = suf_no[nxt] + calc(nxt - idx - 1)
# 解决二分中的边界问题,使得二分一定能找到位置
for val in mp:
mp[val] = [-1] + mp[val] + [n]
def find_next (pos , x):
# 在mp[x]中找到pos的下一个x的位置,搜索区间pos包括本身
l , r = 0 , len(mp[x]) - 1
while l <= r:
mid = (l + r) // 2
if mp[x][mid] < pos:
l = mid + 1
else:
r = mid - 1
return mp[x][l]
def find_last (pos , x):
# 在mp[x]中找到pos的上一个x的位置,搜索区间pos包括本身
l , r = 0 , len(mp[x]) - 1
while l <= r:
mid = (l + r) // 2
if mp[x][mid] <= pos:
l = mid + 1
else:
r = mid - 1
return mp[x][r]
def query_suf (pos , x):
# 计算从pos开始到结尾的不包含x的子数组数量
if pos == n:
return 0
if arr[pos] == x:
return suf_no[pos]
idx = find_next(pos , x)
mid_len = idx - pos
return suf_no[idx] + calc(mid_len)
for _ in range(m):
l , r , x = map(int, input().split())
if x not in mp:
print(0)
continue
l -= 1
r -= 1
ans = query_suf(l , x) - query_suf(r + 1, x)
# 进而考虑区间跨过x的情况
if arr[r] != x:
left = max(l - 1, find_last(r , x))
right = find_next(r + 1, x)
ans -= (r - left) * (right - r - 1)
print(calc(r - l + 1) - ans)
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int t;
/*void bf() {
vector<int> a = {5, 1, 1, 1,5};
int ans = 0;
int x = 1;
for (int i = 0; i < a.size(); i++) {
set<int> st;
for (int j = i; j < a.size(); j++) {
st.insert(a[j]);
if(st.count(x)) {
ans++;
}
}
}
cout << ans << endl;
}*/
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
map<int, vector<int>> mp;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp[a[i]].push_back(i);
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int l, r, x;
cin >> l >> r >> x;
int id = lower_bound(mp[x].begin(), mp[x].end(), l) - mp[x].begin();
int id2 = upper_bound(mp[x].begin(), mp[x].end(), r) - mp[x].begin() - 1;
ll ans = 0;
if (id < mp[x].size()) {
for (int i = id; i <= id2; i++) {
if (i == id) {
ans = ans + 1ll * (mp[x][i] - l + 1) * (r - mp[x][i] + 1);
} else {
//cout << mp[x][i] << " " << mp[x][i - 1] << endl;
ans = ans + 1ll * (mp[x][i] - mp[x][i - 1]) * (r - mp[x][i] + 1);
}
}
}
cout << ans << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
srand(time(NULL));
t = 1;
while (t--) {
solve();
}
}
OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。
题目描述
米小游有一个长度为n的数组a,她会询问q次,每次会问你区间[l,r]中有多少个连续子数组包含x。
如果数组a可以通过从数组b的开头删除若干(可能为零或全部)无素以及从结尾删除若干(可能为零或全部)元素得到,则数组a是数组b的子数组。
输入描述
第一行输入一个整数 n 表示数组长度。
第二行输入 n 个整数 表示数组。
第三行输入一个整数 q 表示询问次数。
接下来 q 行,每行输入三个整数 l,r,x 表示一次询问。
输出描述
对于每一个询问,在一行上输出一个整数,代表答案。
3
1 2 1000
3
1 2 1
1 3 1
1 3 40
2
3
0
说明
对于第一次询问,子数组 [1,1] 和 [1,2] 包含1。