开源展示型网站,wordpress顶部栏插件,格朗图手表网站,云南工程建设总承包公司网站Written with StackEdit. Description 给定一个序列#xff0c;初始为空。现在我们将\(1\)到\(N\)的数字插入到序列中#xff0c;每次将一个数字插入到一个特定的位置。每插入一个数字#xff0c;我们都想知道此时最长上升子序列长度是多少#xff1f; Input 第一行一个整数… Written with StackEdit. Description 给定一个序列初始为空。现在我们将\(1\)到\(N\)的数字插入到序列中每次将一个数字插入到一个特定的位置。每插入一个数字我们都想知道此时最长上升子序列长度是多少 Input 第一行一个整数\(N\)表示我们要将\(1\)到\(N\)插入序列中接下是\(N\)个数字第\(k\)个数字\(X_k\)表示我们将\(k\)插入到位置\(X_k0\leq X_k\leq k-1,1\leq k\leq N\), Output \(N\)行第\(i\)行表示\(i\)插入\(X_i\)位置后序列的最长上升子序列的长度是多少。 Sample Input 3 0 0 2 Sample Output 1 1 2 HINT \(100\%\)的数据 \(n\leq100000\). Solution 如果我们已经得到了最后的序列,我们可以用\(O(nlogn)\)的算法计算出\(LIS\),同时维护\(ans[i]\),表示以\(i\)作为结尾的上升子序列的最大长度.再令\(g[i]\)表示最终要输出的答案,即插入\(i\)后的\(LIS\)长度.因为整个序列是从小到大插入的,所以\(g[i]max_{j1}^{i}ans[j].\)使用前缀和优化一下即可.维护元素的插入可以写一颗平衡树.#includebits/stdc.h
using namespace std;
typedef long long LoveLive;
inline int read()
{int out0,fh1;char jpgetchar();while ((jp9||jp0)jp!-)jpgetchar();if (jp-){fh-1;jpgetchar();}while (jp0jp9){outout*10jp-0;jpgetchar();}return out*fh;
}
const int MAXN1e510;
int a[MAXN],qlen0;
int n;
struct FhqTreap
{int x,y;struct node{int lson,rson,siz,weight,key;} treap[MAXN];int idx,root;FhqTreap(){x0,y0;idx0;root0;treap[0].key0;treap[0].lsontreap[0].rson0;treap[0].weight0;treap[0].siz0;}#define rt treap[o]#define ls treap[treap[o].lson]#define rs treap[treap[o].rson]inline int newnode(int key){int oidx;rt.lsonrt.rson0;rt.siz1;rt.weightrand();rt.keykey;return o;}inline void pushup(int o){rt.sizls.sizrs.siz1;}int merge(int x,int y){if(!x || !y)return xy;if(treap[x].weighttreap[y].weight){treap[x].rsonmerge(treap[x].rson,y);pushup(x);return x;}else{treap[y].lsonmerge(x,treap[y].lson);pushup(y);return y;}}void split(int x,int y,int k,int o){if(!o)xy0;else{if(kls.siz){yo;split(x,rt.lson,k,rt.lson);}else{xo;split(rt.rson,y,k-ls.siz-1,rt.rson);}pushup(o);}}void ins(int key,int pos){split(x,y,pos,root);ymerge(newnode(key),y);rootmerge(x,y);}void dfs(int o){if(!o)return;dfs(rt.lson);a[qlen]rt.key;dfs(rt.rson);}void getseq(){dfs(root);}
}T;
#define inf 0x7fffffff
int f[MAXN],ans[MAXN];
int main()
{srand(19260817);nread();for(int i1;in;i){int posread();T.ins(i,pos);}T.getseq();memset(f,0x7f,sizeof f);f[0]-inf;for(int i1;in;i){int tupper_bound(f,fn1,a[i])-f;f[t]a[i];ans[a[i]]t;}for(int i1;in;i)printf(%d\n,ans[i]max(ans[i-1],ans[i]));puts();return 0;
}转载于:https://www.cnblogs.com/jklover/p/10163705.html
