思路:区间容斥计算

数据范围？

首先，据考生反应，这个题目并没有给数据范围，但是$O(n^2)$的复杂度并过不去。那么我们就假设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。