我只能说真的看不懂题解的做法 我的做法就是线段树维护,毕竟每个数的顺序不变嘛 那么单点维护 区间剩余卡片和最小值
每次知道最小值之后,怎么知道需要修改的位置呢 直接从每种数维护的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; }转载于:https://www.cnblogs.com/Basasuya/p/8433692.html