【出行计划 / 2】
题目
思路
暴力 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;
}