C. Monsters (hard version)
思路
最终肯定是一个阶梯的数组,思考怎么维护阶梯,那些数加进来是无用的。
用线段树来维护每个数出现的次数。
代码
/*
最后形成的一定是一个阶梯状的数组
如果新加进来一个数,判断他是否是有用的,就是是不是有没有他都无所谓。
也就是不需要他去顶替谁的位置,这样子的话他也就是没有用的
直接删除就可以了。
用线段树来进行维护前缀和,每个点的值设置为-i,这样子容易判断是否有无用的
无用的就进行删除
*/
#include <bits/stdc++.h>
using namespace std;
#define ul (u << 1)
#define ur (u << 1 | 1)
const int M = 2e5 + 5;
struct Tree {
int l, r, mx, la;
}tr[M << 2];
void pu(int u) {
tr[u].mx = max(tr[ul].mx, tr[ur].mx);
}
void pd(int u) {
if(!tr[u].la)return ;
tr[ul].la += tr[u].la;
tr[ur].la += tr[u].la;
tr[ul].mx += tr[u].la;
tr[ur].mx += tr[u].la;
tr[u].la = 0;
}
void build(int u, int l, int r) {
tr[u] = {l, r, -l , 0};
if(l == r)return ;
int mid = (l + r) / 2;
build(ul, l, mid);
build(ur, mid + 1, r);
pu(u);
}
void up(int u, int l, int r, int v) {
if(tr[u].l >= l && tr[u].r <= r) {
tr[u].la += v;
tr[u].mx += v;
return ;
}
if(tr[u].l > r || tr[u].r < l)return ;
pd(u);
up(ul, l, r, v);
up(ur, l, r, v);
pu(u);
}
int query(int u) {
if(tr[u].l == tr[u].r)return tr[u].l;
pd(u);
if(tr[ul].mx > 0)return query(ul);
return query(ur);
}
int a[M];
int main() {
int TT; cin >> TT;
while(TT--) {
int n; cin >> n;
build(1, 1, n);
for(int i = 1; i <= n; i++)cin >> a[i];
long long cnt = 0, sum = 0;
for(int i = 1; i <= n; i++) {
cnt++;
sum += a[i];
up(1, a[i], n, 1);
if(tr[1].mx > 0) {
int p = query(1);
up(1, p, n, -1);
cnt--;
sum -= p;
}
cout << (sum - cnt * (cnt + 1) / 2) << ' ';
}
cout << '\n';
}
return 0;
}
标签:return,int,hard,tr,ul,version,query,Monsters
From: https://www.cnblogs.com/basicecho/p/17178970.html