solution-code3935

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
int n,siz[100005],L[100005],R[100005],rnd[100005],v[100005],ans[100005],mn[100005],rt,cnt;
7
inline void pushup(int x)
8
{
9
  siz[x]=siz[L[x]]+siz[R[x]]+1;
10
  return;
11
}
12
inline void Rturn(int& k)
13
{
14
  int tmp=L[k];
15
  L[k]=R[tmp];
16
  R[tmp]=k;
17
  pushup(k);
18
  pushup(tmp);
19
  k=tmp;
20
  return;
21
}
22
inline void Lturn(int& k)
23
{
24
  int tmp=R[k];
25
  R[k]=L[tmp];
26
  L[tmp]=k;
27
  pushup(k);
28
  pushup(tmp);
29
  k=tmp;
30
  return;
31
}
32
inline void Insert(int& x,int rank)
33
{
34
  if(!x)
35
  {
36
    x=++cnt;
37
    rnd[x]=rand();siz[x]=1;
38
    return;
39
  }
40
  ++siz[x];
41
  if(siz[L[x]]<rank)
42
  {
43
    Insert(R[x],rank-siz[L[x]]-1);
44
    if(rnd[R[x]]<rnd[x])Lturn(x);
45
  }
46
  else
47
  {
48
    Insert(L[x],rank);
49
    if(rnd[L[x]]<rnd[x])Rturn(x);
50
  }
51
  return;
52
}
53
inline void dfs(int x)
54
{
55
  if(!x)return;
56
  dfs(L[x]);
57
  v[++v[0]]=x;
58
  dfs(R[x]);
59
  return;
60
}
61
inline void Solve()
62
{
63
  int i,maxx=0,tmp;
64
  memset(mn,0x3F,sizeof(mn));
65
  mn[0]=-0x3F3F3F3F;
66
  for(i=1;i<=n;++i)
67
  {
68
    tmp=upper_bound(mn,mn+maxx+1,v[i])-mn;
69
    if(mn[tmp-1]<=v[i])
70
    {
71
      mn[tmp]=min(mn[tmp],v[i]);
72
      ans[v[i]]=tmp;
73
      maxx=max(maxx,tmp);
74
    }
75
  }
76
  for(i=1;i<=n;++i)printf("%d\n",ans[i]=max(ans[i],ans[i-1]));
77
  return;
78
}
79
int main(void)
80
{
81
  int i,x;
82
  scanf("%d",&n);
83
  for(i=1;i<=n;++i)
84
  {
85
    scanf("%d",&x);
86
    Insert(rt,x);
87
  }
88
  dfs(rt);
89
  Solve();
90
  return 0;
91
}

1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<algorithm>
5
using namespace std;
6
int val[100005],ch[100005][2],fa[100005],siz[100005],maxx[100005],rt,cnt;
7
inline void pushup(int x)
8
{
9
  int L=ch[x][0],R=ch[x][1];
10
  siz[x]=siz[L]+siz[R]+1;
11
  maxx[x]=max(val[x],max(maxx[L],maxx[R]));
12
  return;
13
}
14
inline void Rot(int x,int& f)
15
{
16
  int y=fa[x],z=fa[y],L=(ch[y][0]!=x),R=(L^1);
17
  if(y==f)f=x;
18
  else
19
  {
20
    if(ch[z][0]==y)ch[z][0]=x;
21
    else ch[z][1]=x;
22
  }
23
  fa[x]=z;fa[y]=x;
24
  fa[ch[x][R]]=y;
25
  ch[y][L]=ch[x][R];
26
  ch[x][R]=y;
27
  pushup(y);
28
  pushup(x);
29
  return;
30
}
31
inline void Splay(int x,int& f)
32
{
33
  while(x!=f)
34
  {
35
    int y=fa[x],z=fa[y];
36
    if(y!=f)
37
    {
38
      if(ch[z][0]==y^ch[y][0]==x)Rot(x,f);
39
      else Rot(y,f);
40
    }
41
    Rot(x,f);
42
  }
43
  return;
44
}
45
inline int Find(int x,int k)
46
{
47
  int L=ch[x][0],R=ch[x][1];
48
  if(siz[L]+1==k)return x;
49
  if(siz[L]+1>k)return Find(L,k);
50
  return Find(R,k-siz[L]-1);
51
}
52
inline void Insert(int x,int value)
53
{
54
  int L=Find(rt,x),R=Find(rt,x+1);
55
  Splay(L,rt);
56
  Splay(R,ch[L][1]);
57
  fa[++cnt]=R;
58
  val[cnt]=maxx[cnt]=value;
59
  siz[cnt]=1;
60
  ch[R][0]=cnt;
61
  pushup(R);
62
  pushup(L);
63
  return;
64
}
65
inline int Getmax(int x,int y)
66
{
67
  int L=Find(rt,x-1),R=Find(rt,y+1);
68
  Splay(L,rt);
69
  Splay(R,ch[L][1]);
70
  return maxx[ch[R][0]];
71
}
72
inline void Init(void)
73
{
74
  rt=1;cnt=2;
75
  val[1]=val[2]=-0x3FFFFFFF;
76
  ch[1][0]=2;fa[2]=1;
77
  siz[1]=2;siz[2]=1;
78
  return;
79
}
80
int main(void)
81
{
82
  Init();
83
  int i,n,x,ans,Ans=0;
84
  scanf("%d",&n);
85
  for(i=1;i<=n;++i)
86
  {
87
    scanf("%d",&x);
88
    ans=Getmax(2,x+1)+1;
89
    printf("%d\n",Ans=max(Ans,ans));
90
    Insert(x+1,ans);
91
  }
92
  return 0;
93
}

1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<algorithm>
5
using namespace std;
6
int n,a[100005],ans[100005],c[100005];
7
inline int lowbit(int x){return x&(-x);}
8
inline int getsum(int x,int y){return x+y;}
9
inline int getmax(int x,int y){return x>y?x:y;}
10
inline void Insert(int x,int val,int oper(int,int))
11
{
12
  while(x<=n)c[x]=oper(c[x],val),x+=lowbit(x);
13
  return;
14
}
15
inline int Query(int x,int oper(int,int))
16
{
17
  int sum=0;
18
  while(x>=1)sum=oper(sum,c[x]),x-=lowbit(x);
19
  return sum;
20
}
21
inline int Query(int x)
22
{
23
  int L=1,R=n-x,mid;
24
  while(L<=R)
25
  {
26
    mid=(L+R)>>1;
27
    if(Query(a[x]+mid,getsum)>mid)L=mid+1;
28
    else R=mid-1;
29
  }
30
  return L;
31
}
32
int main(void)
33
{
34
  int i,x;
35
  scanf("%d",&n);
36
  for(i=1;i<=n;++i)
37
  {
38
    scanf("%d",&a[i]);++a[i];
39
  }
40
  for(i=n;i>=1;--i)Insert(a[i]+=Query(i),1,getsum);
41
  memset(c,0,sizeof(c));
42
  for(i=1;i<=n;++i)
43
  {
44
    Insert(a[i],ans[i]=Query(a[i]-1,getmax)+1,getmax);
45
  }
46
  for(i=1;i<=n;++i)printf("%d\n",ans[i]=max(ans[i],ans[i-1]));
47
  return 0;
48
}

1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<algorithm>
5
#include<vector>
6
using namespace std;
7
int b[100005],c[100005],ans[100005];
8
inline int lowbit(int x){return x&(-x);}
9
inline void Add(int x,int y)
10
{
11
  while(x<=100002)c[x]=max(c[x],y),x+=lowbit(x);
12
  return;
13
}
14
inline int Sum(int x)
15
{
16
  int sum=0;
17
  while(x>=1)sum=max(sum,c[x]),x-=lowbit(x);
18
  return sum;
19
}
20
vector<int>a;
21
int main(void)
22
{
23
  int i,x,n;
24
  scanf("%d",&n);
25
  for(i=1;i<=n;++i)
26
  {
27
    scanf("%d",&x);
28
    a.insert(a.begin()+x,i);
29
  }
30
  for(i=0;i<n;++i)b[a[i]]=i+1;
31
  for(i=1;i<=n;++i)
32
  {
33
    Add(b[i],ans[i]=Sum(b[i]-1)+1);
34
  }
35
  for(i=1;i<=n;++i)printf("%d\n",ans[i]=max(ans[i],ans[i-1]));
36
  return 0;
37
}