Problem Description
好久没出数据结构题，现在赶紧来做道数据结构题热热身
小q现在要去银行，他有个很厉害的bug能看到前面排队的人。假如当前有人正在办理业务，那么肯定要等待前一个人完成。现在有m个事件，分为3种。第一种是第x时刻有客人到银行办理业务，用时t。第二种是第i个事件中的客人取消去银行。第三种是小q想询问他第x分钟去银行需要等多久。小q是个礼貌的人如果有人跟他同一时刻到达，他会让别人先。
Input
单组数就
第一行输入一个整数m,代表m个事件。
接下来m行输入3种操作之一。
+ x t代表第x时刻有客人到银行办理业务，用时t(1<=x,t<=10^6)
- i 代表第i个事件中的客人取消业务办理（1<=i<=m)
？x代表小q想知道如果他在时刻x去，要等多久(1<=x<=10^6)
30%数据:m<=1000
100%数据 m<=300000
Output
对于每个?事件输出一行，只包含一个整数，代表答案
SampleInput
19? 3+ 2 2? 3? 4+ 5 2? 5? 6+ 1 2? 2? 3? 4? 5? 6? 7? 9- 8? 2? 3? 6
SampleOutput
010213212100211
样例解释:如果小q第3时刻来，前面没有人所以等待0.如果第3时刻来，前面有个客人为(2,2)第4时刻才结束，那么小q则需要等待1...
思路：
假设从j时刻开始，后面到的所有人都要开始排队，我们假设每个时刻总用时a[j]（也就是题目中的t）
a[j]前缀和设为sum[j]所以i时刻的排队时间为 sum[i] - sum[j] - (i - (j + 1))那么怎么快速找到这个j呢？显然如果sum[i] - sum[j] < (i - (j + 1))，那就是不用排队，我们取0；如果sum[i] - sum[j] > (i - (j + 1))，那我们就找出 max（sum[i] - sum[j] - (i - (j + 1))）
综上，结果应是max（sum[i] - sum[j] - (i - (j + 1))，0） 1<=j<i，由于i确定，所以可以转化为 sum[i] - i + 1 + max(j - sum[j])，用线段树维护j - sum[j]的最大值和sum[i]
代码：
#include#include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 1e6 + 10;const ull seed = 131;const int INF = 0x3f3f3f3f;const int MOD = 1000000007;ll sum[maxn << 2], Max[maxn << 2], lazy[maxn << 2];int t[maxn], p[maxn], v[maxn];void pushDown(int rt){ if(lazy[rt]){ lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; sum[rt << 1] += lazy[rt]; sum[rt << 1 | 1] += lazy[rt]; Max[rt << 1] -= lazy[rt]; Max[rt << 1 | 1] -= lazy[rt]; lazy[rt] = 0; }}void build(int l, int r, int rt){ if(l == r){ Max[rt] = l; return; } int m = (l + r) >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);}void update(int L, int R, int l, int r, int rt, ll v){ if(L <= l && R >= r){ lazy[rt] += v; sum[rt] += v; Max[rt] -= v; return; } pushDown(rt); int m = (l + r) >> 1; if(L <= m) update(L, R, l, m, rt << 1, v); if(R > m) update(L, R, m + 1, r, rt << 1 | 1, v); Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);}ll queryMax(int L, int R, int l, int r, int rt){ if(R <= 0) return 0; if(L <= l && R >= r){ return Max[rt]; } pushDown(rt); int m = (l + r) >> 1; ll MAX = -INF; if(L <= m) MAX = max(MAX, queryMax(L, R, l, m, rt << 1)); if(R > m) MAX = max(MAX, queryMax(L, R, m + 1, r, rt << 1 | 1)); Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]); return MAX;}ll querySum(int pos, int l, int r, int rt){ if(pos == 0) return 0; if(l == r){ return sum[rt]; } pushDown(rt); int m = (l + r) >> 1; ll ans; if(pos <= m) ans = querySum(pos, l, m, rt << 1); else ans = querySum(pos, m + 1, r, rt << 1 | 1); Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]); return ans;}int main(){ int n, m; int e = 1000000; build(1, e, 1); scanf("%d", &m); for(int i = 1; i <= m; i++){ char o[2]; int x, tt; scanf("%s", o); if(o[0] == '+'){ scanf("%d%d", &p[i], &v[i]); update(p[i], e, 1, e, 1, v[i]); } else if(o[0] == '-'){ scanf("%d", &x); update(p[x], e, 1, e, 1, -v[x]); } else{ scanf("%d", &x); ll SumI = querySum(x, 1, e, 1); ll MaxJ = max(queryMax(1, x - 1, 1 ,e, 1), 0LL); printf("%lld\n", SumI - x + 1 + MaxJ); //sum[i] - sum[j] - (i - (j + 1)) //sum[i] - i + 1 + (j - sum[j]) } } return 0;}/*假设从j位置开始，后面所有人都要开始排队，每个位置用时a[j]a[j]前缀和sum[j]所以i位置排队 = sum[i] - sum[j] - (i - (j + 1))*/