CODE

#include<bits/stdc++.h>

using namespace std;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

	char ch; int flg = 1; while(!isdigit(ch=getc()))if(ch=='-')flg=-flg;

	for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 100005;

int n, m, x[MAXN], rk[MAXN], ans, sz[MAXN<<2], T[MAXN];

inline void chkmax(int &x, int y) { if(y > x) x = y; }

inline void upd(int x, int val) { for(; x <= n; x += x&-x) chkmax(T[x], val); }

inline int qsum(int x) { int re = 0; for(; x; x -= x&-x) chkmax(re, T[x]); return re; }

inline void upd(int i) { sz[i] = sz[i<<1] + sz[i<<1|1]; }

void build(int i, int l, int r) {

	if(l == r) { sz[i] = 1; return; }

	int mid = (l + r) >> 1;

	build(i<<1, l, mid);

	build(i<<1|1, mid+1, r);

	upd(i);

}

int query(int i, int l, int r, int k) {

	if(l == r) { sz[i] = 0; return l; }

	int mid = (l + r) >> 1, re;

	if(k <= sz[i<<1]) re = query(i<<1, l, mid, k);

	else re = query(i<<1|1, mid+1, r, k-sz[i<<1]);

	upd(i); return re;

}

int main() {

	read(n); build(1, 1, n);

	for(int i = 1; i <= n; ++i) read(x[i]), ++x[i];

	for(int i = n; i >= 1; --i) rk[i] = query(1, 1, n, x[i]); //!

	for(int i = 1, f; i <= n; ++i) {

		chkmax(ans, f = qsum(rk[i]) + 1);

		printf("%d\n", ans);

		upd(rk[i], f);

	}

}

巴特西

BZOJ 3173: [Tjoi2013]最长上升子序列 (线段树+BIT)

CODE

最新文章

热门文章