题目
思路
暴力
O
(
m
⋅
n
)
O(m \cdot n)
O(m⋅n)
\;\;\;\;\;
不可行
树状数组+差分
O
(
m
⋅
l
o
g
(
5
e
5
)
)
O(m \cdot log(5e^{5}))
O(m⋅log(5e5))
\;\;\;\;\;
可行
具体思路：
-
t
[
i
]
∈
[
q
+
k
−
c
[
i
]
+
1
,
q
+
k
]
t[i] \in [q+k-c[i]+1, \;q+k]
t[i]∈[q+k−c[i]+1,q+k]
转换为q + k ∈ [ t [ i ] − c [ i ] + 1 , t [ i ] ] q + k \in [t[i]-c[i]+1, \;t[i]] q+k∈[t[i]−c[i]+1,t[i]] 为了使得范围不存在负数:q + k + 2 e 5 ∈ [ t [ i ] − c [ i ] + 1 + 2 e 5 , t [ i ] + 2 e 5 ] q+k+2e^{5}\in [t[i]-c[i]+1+2e^{5}, \;t[i]+2e^{5}] q+k+2e5∈[t[i]−c[i]+1+2e5,t[i]+2e5]预处理：对于每个出行计划，将映射到的范围的值通过 O ( 1 ) 时间 O(1)\;时间 O(1)时间 的差分操作 + 1 +1 +1区间求和：最后对于每次询问，直接用树状数组的 q u e r y 函数 query函数 query函数 在 O ( l o g n ) 时间 O(logn)\;时间 O(logn)时间 求出该点处的实际值确定树状数组大小：存在操作 q u e r y ( q + k + 2 e 5 ) ， M = 5 e 5 query(q + k + 2e^{5})， M = 5e^{5} query(q+k+2e5)，M=5e5
TLE代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int t[N], c[N];
int n, m, k;
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) cin >> t[i] >> c[i];
while (m -- ){
int q;
cin >> q;
q += k;
int cnt = 0;
int l = q;
for(int i = 1; i <= n; i++)
{
int r = l + c[i] - 1;
if(t[i] >= l && t[i] <= r) cnt++;
}
cout << cnt << endl;
}
return 0;
}
正确代码
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = 5e5+10;
int t[N], c[N];
int n, m, k;
int b[M];
int lowbit(int x)
{
return x & -x;
}
void update(int x, int d)
{
for(; x < M; x += lowbit(x)) b[x] += d;
}
int query(int x)
{
int retval = 0;
for(; x; x -= lowbit(x)) retval += b[x];
return retval;
}
void add(int l, int r, int d)
{
update(l, d);
update(r+1, -d);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
{
cin >> t[i] >> c[i];
add(t[i]-k-c[i]+1+3e5, t[i]-k+3e5, 1);
}
while(m--)
{
int q;
cin >> q;
cout << query(q+3e5) << endl;
}
return 0;
}