求且力c++是页目（恶心的标题限制

Question

在一个数轴上有n个格子存在金币。小信可以选择一个位子作为他的起点。假设小信正站在x位置，他可以花费1秒时间移动到x−1或者x+1。他还有一个魔法，可以传送到任意位置，传送不需要时间，但全程只能使用一次传送。

现在地图会变化q次：

0 x：位置x的金币消失，保证在这之前位置x上有金币。

1 x：在位置x出现金币，保证在这之前位置x上没有金币。

你需要告诉小信，在初始地图，以及每一次变化后，小信至少需要多少秒才能拿走所有金币。

样例输入：
5 13
6 1 2 10 8
1 4
1 9
0 6
0 10
1 100
1 50
0 2
0 9
0 1
0 50
0 4
0 100
0 8

样例输出：
5
7
7
5
4
8
49
49
49
46
4
0
0
0
约定：
有10%的数据，1≤n≤105,q=0。

另有30%的数据，1≤n,q≤5000。

对于100%的数据：

1≤n,q≤105，

1≤pi≤109，

0≤op≤1，

1≤x≤109。

this题我写了一个，却全TLE了

```c++
#include<bits/stdc++.h>
using namespace std;
long long p[2000010];
int main()
{
    long long n,q,i,op,x;
    while(scanf("%d %d",&n,&q))
    {
        for(int ii=1;ii<=n;ii++)
        {
            scanf("%d",&p[ii]);
        }
        sort(p+1,p+n+1);
        set<long long> s;
        multiset<long long> res;
        for(i=1;i<n;i++)
        {
            res.insert(p[i]-p[i+1]);
            s.insert(p[i]);
        }
        s.insert(p[n]);
        printf("%d\n",*res.begin()-*s.begin()+*s.rbegin());
        while(q--)
        {
            scanf("%d%d",&op,&x);
            if(op==0)
            {
                auto it=s.lower_bound(x);
                if(it==s.begin())
                {
                    auto nex=it;
                    nex++;
                    if(nex!=s.end()) res.erase(res.find(x-*nex));
                    s.erase(it);
                }
                else
                {
                    auto pre=it;
                    auto nex=it;
                    pre--;
                    nex++;
                    res.erase(res.find(*pre-x));
                    if(nex!=s.end())
                    {
                        res.erase(res.find(x-*nex));
                        res.insert(*pre-*nex);
                    }
                    s.erase(it);
                }
            }
            else
            {
                s.insert(x);
                auto it=s.lower_bound(x);
                if(it==s.begin())
                {
                    auto nex=it;
                    nex++;
                    if(nex!=s.end()) res.insert(x-*nex);
                }
                else
                {
                    auto pre=it;
                    auto nex=it;
                    pre--;
                    nex++;
                    res.insert(*pre-x);
                    if(nex!=s.end())
                    {
                        res.insert(x-*nex);
                        res.erase(res.find(*pre-*nex));
                    }
                }
                if(s.size()<=2) puts("0");
                else printf("%d\n",*res.begin()-*s.begin()+*s.rbegin());
            }
        }
    }
    return 0;
}

Answer 1

该回答引用GPTᴼᴾᴱᴺᴬᴵ
看起来你的代码时间复杂度应该是 $O(qn\log n)$ 的，可能会超时。可以尝试用其他数据结构来优化时间复杂度。

比如，我们可以维护一个数组 $sum$，其中 $sum_i$ 表示前 $i$ 个位置的金币总数。那么初始状态下，答案就是 $2\sum_n-np_n$。

考虑到每次修改操作只涉及一个位置，我们可以用一个变量 $d$ 来记录这个位置变化前后金币数量的差值，然后更新 $sum$ 数组和答案。具体地，如果删除一个位置 $x$ 上的金币，则 $d=-1$；如果增加一个位置 $x$ 上的金币，则 $d=1$。接着，我们可以用 $O(\log n)$ 的时间找到 $x$ 在 $sum$ 数组中的位置 $p$，并更新 $sum$ 数组。由于修改操作只涉及一个位置，所以数组 $sum$ 的更新只需要 $O(\log n)$ 的时间。最后，我们可以用 $O(1)$ 的时间计算出新的答案，即 $2\sum_n-np_n+2\max(p_1+\sum_{i=2}^{n-1}|p_i-p_1|,p_n+\sum_{i=2}^{n-1}|p_i-p_n|)$。

综上，我们可以用 $O(q\log n)$ 的时间复杂度解决这个问题，具体代码实现可以参考下面的示例代码：

#include<bits/stdc++.h>
using namespace std;
long long p[2000010];
int main()
{
    long long n,q,i,op,x;
    while(scanf("%d %d",&n,&q)!=EOF)
    {
        for(int ii=1;ii<=n;ii++)
        {
            scanf("%d",&p[ii]);
        }
        sort(p+1,p+n+1);
        set<long long> s;
        multiset<long long> res;
        for(i=1;i<n;i++)
        {
            res.insert(p[i]-p[i+1]);
            s.insert(p[i]);
        }
        s.insert(p[n]);
        printf("%d\n",*res.begin()-*s.begin()+*s.rbegin());
        while(q--)
        {
            scanf("%d%d",&op,&x);
            if(op==0)
            {
                auto it=s.lower_bound(x);
                if(it==s.begin())
                {
                    auto nex=it;
                    nex++;
                    if(nex!=s.end()) res.erase(res.find(x-*nex));
                    s.erase(it);
                }
                else
                {
                    auto pre=it;
                    auto nex=it;
                    pre--;
                    nex++;
                    res.erase(res.find(*pre-x));
                    if(nex!=s.end())
                    {
                        res.erase(res.find(x-*nex));
                        res.insert(*pre-*nex);
                    }
                    s.erase(it);
                }
            }
            else
            {
                s.insert(x);
                auto it=s.lower_bound(x);
                if(it==s.begin())
                {
                    auto nex=it;
                    nex++;
                    if(nex!=s.end()) res.insert(x-*nex);
                }
                else
                {
                    auto pre=it;
                    auto nex=it;
                    pre--;
                    nex++;
                    res.insert(*pre-x);
                    if(nex!=s.end())
                    {
                        res.insert(x-*nex);
                        res.erase(res.find(*pre-*nex));
                    }
                }
                if(s.size()<=2) puts("0");
                else printf("%d\n",*res.begin()-*s.begin()+*s.rbegin());
            }
        }
    }
    return 0;
}