Codeforces Round #424 Div2 E. Cards Sorting

时间:2021-07-01 16:55:45

我只能说真的看不懂题解的做法
我的做法就是线段树维护,毕竟每个数的顺序不变嘛
那么单点维护 区间剩余卡片和最小值

每次知道最小值之后,怎么知道需要修改的位置呢
直接从每种数维护的set找到现在需要修改的数的在初始卡片的位置

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
#define MP(x, y) make_pair(x, y)
#define lson l,m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
int MOD;
int A[N];
int Min[N << 2];
int Sum[N << 2];
void Build(int l, int r, int rt) {
if(l == r) {
Min[rt] = A[l]; Sum[rt] = 1;
return;
}
int m = (l + r) >> 1;
Build(lson); Build(rson);
Sum[rt] = Sum[rt << 1] + Sum[rt << 1|1];
Min[rt] = min(Min[rt <<1] , Min[rt << 1|1]);
}
void Update(int pos, int l, int r, int rt) {
if(l == r) {
Min[rt] = INF; Sum[rt] = 0;
return;
}
int m = (l + r) >> 1;
if(pos <= m) Update(pos, lson);
else Update(pos, rson);
Sum[rt] = Sum[rt<<1] + Sum[rt<<1|1];
Min[rt] = min(Min[rt<<1], Min[rt<<1|1]);
}
int Total(int pos, int l, int r, int rt) {
if(pos == 0) return 0;
if(pos == r) {
return Sum[rt];
}
int m = (l + r) >> 1;
if(pos <= m) return Total(pos, lson);
else return Sum[rt<<1] + Total(pos, rson);
} map<int, set<int> > mp;
set<int> ::iterator it; int main() {
int n;
while(~scanf("%d", &n)) {
ll ans = 0;
mp.clear();
for(int i = 1; i <= n; ++i) {
scanf("%d",&A[i]);
mp[A[i]].insert(i);
}
Build(1, n, 1); int pos = 1;
for(int i = 1; i <= n; ++i) {
int tar = Min[1]; int nwpos;
it = mp[tar].lower_bound(pos); if(it == mp[tar].end()) {
it = mp[tar].begin();
}
nwpos = *it;
mp[tar].erase(it); // printf("%d %d\n", tar, nwpos); Update(nwpos, 1, n, 1);
int t1 = Total(nwpos, 1,n,1); int t2 = Total(pos - 1, 1,n,1);
// printf("%d %d\n", t1, t2);
if(pos <= nwpos) {
ans += t1 - t2 + 1;
}else {
ans += Sum[1] - t2 + t1 + 1;
}
pos = nwpos;
} printf("%d\n", ans);
}
return 0;
}