有 $n$ 本书，第 $i$ 本书中有 $a_i$ 个问题，均属于第 $t_i$ 类问题。
有 $q$ 次询问，每次询问给出一个区间 $[l_i,r_i]$ ，询问有多少个原序列的连续子区间是给出区间的子区间，且该子区间中所有书中问题的和满足第 $1$ 类的问题恰好比第 $2$ 类的问题恰好多 $k$ 个。
数据范围： $1 \le n \le 10^5$ , $-10^9 \le k \le 10^9$, $t_i \in {1,2}$ , $0 \le a_i \le 10^9$ , $1 \le q \le 10^5$ , $1 \le l_i \le r_i \le n$
链接
Codeforces
题解
看到离线的区间询问让我们想到莫队（其实是前几天THUWC没做出来签到题让我想到的），然后我们发现我们可以做到相邻的区间转移。这个问题事实上就是前缀和相差 $k$ ，我们用个什么东西（比如 map ）离散化一下所有的 sum 前缀和，预处理出来每个位置的前缀和减掉和加上 $k$ 之后的离散化后的数字。在莫队的过程中维护一个 $cnt$ 数组，就可以 $O(1)$ 转移了。
时间复杂度：$O(q \sqrt n + n \log n )$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 110000;
int n,q,Q;
int t[MAXN],a[MAXN];
ll k,sum[MAXN],A[MAXN],B[MAXN];// A -> -k / B -> +k
map<ll,int> S;int tmpcnt = 0;
struct Query{
int l,r,id;
}qu[MAXN];
bool cmp(Query a,Query b){
if(a.l/Q != b.l/Q)
return a.l / Q < b.l / Q;
else
return ((a.l/Q)&1)?a.r < b.r:a.r > b.r;
}
void init(){
scanf("%d %lld",&n,&k);
for(int i = 1;i<=n;i++) scanf("%d",&t[i]);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
for(int i = 1;i<=n;i++){
sum[i] = t[i] == 1?a[i]:-a[i];
sum[i] += sum[i-1];
S[sum[i]] = 0;
}
S[0] = 0;
for(auto it = S.begin();it != S.end();it++)
it->second = ++tmpcnt;
for(int i = 0;i<=n;i++){
if(S.count(sum[i]-k)) A[i] = S[sum[i]-k];
if(S.count(sum[i]+k)) B[i] = S[sum[i]+k];
sum[i] = S[sum[i]];
}
Q = sqrt(n);
scanf("%d",&q);
for(int i = 1;i<=q;i++)
scanf("%d %d",&qu[i].l,&qu[i].r),qu[i].id = i;
sort(qu+1,qu+q+1,cmp);
}
static int cnt[MAXN],L = 1,R = 0;// 维护 [L-1,R] 的前缀和
ll ans = 0;
void addL(int pos){
ans += cnt[B[pos-1]];cnt[sum[pos-1]]++;
}
void addR(int pos){
ans += cnt[A[pos]];cnt[sum[pos]]++;
}
void delL(int pos){
cnt[sum[pos-1]]--;ans -= cnt[B[pos-1]];
}
void delR(int pos){
cnt[sum[pos]]--;ans -= cnt[A[pos]];
}
ll ANS[MAXN];
void solve(){
cnt[S[0]] = 1;
for(int i = 1;i<=q;i++){
while(qu[i].l < L) addL(--L);
while(qu[i].r > R) addR(++R);
while(qu[i].l > L) delL(L++);
while(qu[i].r < R) delR(R--);
ANS[qu[i].id] = ans;
}
for(int i = 1;i<=q;i++){
printf("%lld\n",ANS[i]);
}
}
int main(){
init();
solve();
return 0;
}
|
