这不是代码复杂度不是 o(Tnlogn) 吗?为啥只有70分?(剩下的全T)
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int x, u, t;
};
struct cm1
{
bool operator()(Node a, Node b)
{
if (a.x != b.x) return a.x < b.x;
else return a.u < b.u;
}
};
struct cm2
{
bool operator()(Node a, Node b) {
if (a.x != b.x) return a.x > b.x;
else return a.u > b.u;
}
};
priority_queue <Node, vector <Node>, cm1> qx; //大根堆
priority_queue <Node, vector <Node>, cm2> qi; //小根堆
int n, m, a[1000100], f[1000100][3], ch[1000100], num, las, T, id, x, nm;
bool del[2000100];
void cln ()
{
while (!qx.empty ()) qx.pop ();
while (!qi.empty ()) qi.pop ();
memset (ch, 0, sizeof (ch));
memset (del, 0, sizeof (del));
}
int main ()
{
cin >> T;
for (int l = 1; l <= T; l++)
{
if (l == 1)
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
} else
{
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> id >> x;
a[id] = x;
}
}
cln ();
for (int i = 1; i <= n; i++)
{
Node p = {a[i], i, i};
qx.push (p), qi.push (p);
}
for (int i = 1; i < n; i++)
{
while (!qx.empty () && del[qx.top ().t]) qx.pop ();
del[qx.top ().t] = 1; f[i][1] = qx.top ().u;
while (!qi.empty () && del[qi.top ().t]) qi.pop ();
del[qi.top ().t] = 1; f[i][2] = qi.top ().u;
Node p = {qx.top ().x - qi.top ().x, qx.top ().u, i + n};
qx.push (p); qi.push (p);
}
num = 1, las = n - 1;
for (int i = n - 1; i >= 1; i--)
{
if (ch[f[i][1]] == num)
{
las = i - 1; num++;
} else ch[f[i][2]] = num;
}
cout << n - las << endl;
}
return 0;
}