FJUT3701 这也是一道数论题（线段树）题解

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

样例解释:如果小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<cmath>
#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
#include<bits/stdc++.h>
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
", 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))
*/