线段树csdn-金沙1005

#include #define ll long long #define ld long double #define ull unsigned long long #define fi first #define se second #define mk make_pair #define pll pair #define pli pair #define pii pair #define sz(x) ((int)x.size()) #define all(x) (x).begin(), (x).end() #define fio ios::sync_with_stdio(false); cin.tie(0); using namespace std; const int n = 1e5   7; const int inf = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; const double eps = 1e-8; const double pi = acos(-1); template<class t, class s> inline void add(t& a, s b) {a  = b; if(a >= mod) a -= mod;} template<class t, class s> inline void sub(t& a, s b) {a -= b; if(a < 0) a  = mod;} template<class t, class s> inline bool chkmax(t& a, s b) {return a < b ? a = b, true : false;} template<class t, class s> inline bool chkmin(t& a, s b) {return a > b ? a = b, true : false;} int n, a[n]; int nex[n]; int map[n]; int ans[n]; bool vis[n]; namespace sgt { #define lson l, mid, rt << 1 #define rson mid   1, r, rt << 1 | 1 int a[n << 2]; void update(int p, int val, int l, int r, int rt) { if(l == r) { a[rt]  = val; return; } int mid = l   r >> 1; if(p <= mid) update(p, val, lson); else update(p, val, rson); a[rt] = a[rt << 1]   a[rt << 1 | 1]; } int query(int res, int l, int r, int rt) { if(l == r) return l; int mid = l   r >> 1; if(a[rt << 1] > res) return query(res, lson); else return query(res - a[rt << 1], rson); } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i  ) scanf("%d", &a[i]); for(int i = n; i >= 1; i--) { nex[i] = map[a[i]]; vis[nex[i]] = true; map[a[i]] = i; } priority_queue, greater > que; for(int i = 1; i <= n; i  ) que.push(mk(1, i)); for(int i = 1; i <= n; i  ) if(!vis[i]) sgt::update(i, 1, 1, n   1, 1); for(int i = 1; i <= n; i  ) { while(!que.empty() && que.top().fi == i) { int qid = que.top().se; que.pop(); ans[qid]  ; int nexpos = sgt::query(qid, 1, n   1, 1); que.push(mk(nexpos, qid)); } sgt::update(i, -1, 1, n   1, 1); if(nex[i]) sgt::update(nex[i], 1, 1, n   1, 1); } for(int i = 1; i <= n; i  ) printf("%d%c", ans[i], " \n"[i == n]); return 0; } /* */

希望我今天分享的这篇文章可以帮到您。