品牌建设英文,google seo 优化招聘,网站建设行业现状,企业网站ui题解: 考虑按照元素升序加入 所以对位置在其后的元素LIS无影响 然后从前面位置的最大值转移过来就行 ,,,,平衡树无脑模拟 #include algorithm
#include iostream
#include cstring
#include cstdio
#include vector
#include s… 题解: 考虑按照元素升序加入 所以对位置在其后的元素LIS无影响 然后从前面位置的最大值转移过来就行 ,,,,平衡树无脑模拟 #include algorithm
#include iostream
#include cstring
#include cstdio
#include vector
#include stack
#include queue
#include cmath
#include set
#include map
#define mp make_pair
#define pb push_back
#define pii pairint,int
#define link(x) for(edge *jh[x];j;jj-next)
#define inc(i,l,r) for(int il;ir;i)
#define dec(i,r,l) for(int ir;il;i--)
const int MAXN3e510;
const double eps1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN1],*h[MAXN],*oe;
void add(int x,int y,int vul){o-ty;o-vvul;o-nexth[x];h[x]o;}
ll read(){ll x0,f1;char chgetchar();while(!isdigit(ch)){if(ch-)f-1;chgetchar();}while(isdigit(ch))xx*10ch-0,chgetchar();return x*f;
}int key[MAXN],maxx[MAXN],pre[MAXN],ch[MAXN][2],sz[MAXN];
int rt,n;void newnode(int x,int t){key[x]maxx[x]t;pre[x]ch[x][0]ch[x][1]0;sz[x]1;
}void up(int x){sz[x]sz[ch[x][0]]sz[ch[x][1]]1;maxx[x]max(key[x],max(maxx[ch[x][0]],maxx[ch[x][1]]));
}void rotate(int x,int kind){int ypre[x];ch[y][!kind]ch[x][kind];pre[ch[x][kind]]y;if(pre[y])ch[pre[y]][ch[pre[y]][1]y]x;pre[x]pre[y];ch[x][kind]y;pre[y]x;up(y);
}void splay(int x,int goal){while(pre[x]!goal){if(pre[pre[x]]goal)rotate(x,ch[pre[x]][0]x);else{int ypre[x];int kindch[pre[y]][0]y;if(ch[y][kind]x)rotate(x,!kind),rotate(x,kind);else rotate(y,kind),rotate(x,kind);}}if(goal0)rtx;up(x);
}int find1(int x,int k){if(ksz[ch[x][0]]1)return x;else if(ksz[ch[x][0]])return find1(ch[x][0],k);else return find1(ch[x][1],k-sz[ch[x][0]]-1);
}void inte(){newnode(n1,0);newnode(n2,0);rtn1;ch[rt][1]n2;pre[n2]rt;up(rt);
}int query(int id,int x){//coutfind1(rt,x)endl;splay(find1(rt,x),0);splay(find1(rt,x1),rt);int tmax(maxx[ch[rt][0]],key[rt]);tmax(t1,1);newnode(id,t);pre[id]ch[rt][1];ch[ch[rt][1]][0]id;up(ch[rt][1]);up(rt);return maxx[rt];
}int main(){nread();inte();inc(i,1,n){int tread();printf(%d\n,query(i,t1));}return 0;
}3173: [Tjoi2013]最长上升子序列 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2770 Solved: 1398[Submit][Status][Discuss] Description 给定一个序列初始为空。现在我们将1到N的数字插入到序列中每次将一个数字插入到一个特定的位置。每插入一个数字我们都想知道此时最长上升子序列长度是多少 Input 第一行一个整数N表示我们要将1到N插入序列中接下是N个数字第k个数字Xk表示我们将k插入到位置Xk0Xkk-1,1kN Output N行第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。 Sample Input 3 0 0 2 Sample Output 1 1 2 HINT 100%的数据 n100000 转载于:https://www.cnblogs.com/wang9897/p/10363749.html
