test/aoj/DSL_3_D.cartesiantree.test.cpp

View this file on GitHub
Last update: 2020-10-27 16:52:37+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../datastructure/cartesiantree.cpp"
#include "../../tree/lca.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,l;
  cin>>n>>l;

  vector<int> vs(n);
  for(int i=0;i<n;i++) cin>>vs[i];

  auto ps=cartesian_tree(vs);

  LCA lca(n);
  int rt;
  for(int i=0;i<n;i++){
    if(~ps[i]) lca.add_edge(i,ps[i]);
    else rt=i;
  }
  lca.build(rt);

  for(int i=0;i+l<=n;i++){
    if(i) cout<<" ";
    cout<<vs[lca.lca(i,i+l-1)];
  }
  cout<<endl;
  return 0;
}

#line 1 "test/aoj/DSL_3_D.cartesiantree.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "datastructure/cartesiantree.cpp"

#line 3 "datastructure/cartesiantree.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T>
vector<int> cartesian_tree(const vector<T> &vs){
  int n=vs.size();
  vector<int> ps(n,-1),ls(n,-1),rs(n,-1);
  int cur=0;
  for(int i=1;i<n;i++){
    if(vs[cur]<=vs[i]){
      rs[cur]=i;
      ps[i]=cur;
      cur=i;
      continue;
    }
    while(~ps[cur] and vs[i]<vs[ps[cur]]) cur=ps[cur];
    ps[i]=ps[cur];
    if(~ps[i]) rs[ps[i]]=i;
    ls[i]=cur;
    ps[cur]=i;
    cur=i;
  }
  return ps;
}
//END CUT HERE

#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tree/lca.cpp"

#line 3 "tree/lca.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct LCA{
  const int lg = 12;
  const int sz = 1<<lg;
  const int ms = sz-1;
  int n;
  vector<int> P,D,E,A,B,T,ht;
  vector<vector<int> > G,dat;
  LCA(int n):
    n(n),P(n,-1),D(n),E(n*2,0),A(n*2,-1),B(n*2/lg+1),T(sz,0),G(n){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(int v,int p,int d){
    int k=0,u;
    vector<int> iter(n,0);

    using T = tuple<int, int, int>;
    stack<T> st;

  START:
    D[v]=k;
    A[k]=P[v]=p;
    E[k++]=d;
    for(;iter[v]<(int)G[v].size();iter[v]++){
      u=G[v][iter[v]];
      if(u==p) continue;
      st.emplace(v,p,d);
      p=v;v=u;d=d+1;
      goto START;
    END:
      tie(v,p,d)=st.top();st.pop();
    }

    A[k]=P[v];
    E[k++]=d-1;

    if(!st.empty()) goto END;
  }

  // if it need leftmost, then add: if(E[i]==E[j]) return i<j?i:j;
  inline int comp(int i,int j){return E[i]<E[j]?i:j;};
  inline int comp(int i,int j,int k){return comp(comp(i,j),k);};

  void build(int r=0){
    dfs(r,-1,1);

    B[0]=1;
    for(int i=1;i<n*2;i++) B[i/lg]|=(E[i-1]<E[i])<<(i%lg);

    for(int b=0;b<sz;b++){
      int e=0,w=1,&x=T[b];
      for(int i=0;i<lg;i++){
        if((b>>i)&1) e++;
        else e--;
        if(e<w) e=w,x=i;
      }
    }

    int m=(n*2+lg-1)/lg;
    int h=1;
    while((1<<h)<m) h++;
    dat.assign(h,vector<int>(m,-1));
    ht.assign(m+1,0);
    for(int j=2;j<=m;j++) ht[j]=ht[j>>1]+1;

    for(int j=0;j<n*2;j++){
      if(dat[0][j/lg]<0) dat[0][j/lg]=j;
      dat[0][j/lg]=comp(dat[0][j/lg],j);
    }

    for(int i=1,p=1;i<h;i++,p<<=1)
      for(int j=0;j<m;j++)
        dat[i][j]=comp(dat[i-1][j],dat[i-1][min(j+p,m-1)]);
  }

  inline int cs(int a,int b){
    int l=b-a;
    return comp(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]);
  }

  inline int es(int i,int l,int r){
    int x=r-i*lg+1,y=l-i*lg;
    int b=(((B[i]|(ms<<x))>>y)|(ms<<(lg-y)))&ms;
    return l+T[b];
  }

  inline int ls(int i,int l){
    int k=l-i*lg;
    int b=((B[i]>>k)|(ms<<(lg-k)))&ms;
    return l+T[b];
  }

  inline int rs(int j,int r){
    int k=r-j*lg+1;
    int b=(B[j]|(ms<<k))&ms;
    return j*lg+T[b];
  }

  inline int rmq(int l,int r){
    int i=l/lg,j=r/lg;
    if(i==j) return es(i,l,r);
    if(i+1==j) return comp(ls(i,l),rs(j,r));
    return comp(ls(i,l),cs(i+1,j),rs(j,r));
  }

  int lca(int l,int r){
    if(l==r) return l;
    if(D[l]>D[r]) swap(l,r);
    int x=D[l],y=D[r];
    int m=rmq(x,y);
    return m==x?l:A[m];
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/DSL_3_D.cartesiantree.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,l;
  cin>>n>>l;

  vector<int> vs(n);
  for(int i=0;i<n;i++) cin>>vs[i];

  auto ps=cartesian_tree(vs);

  LCA lca(n);
  int rt;
  for(int i=0;i<n;i++){
    if(~ps[i]) lca.add_edge(i,ps[i]);
    else rt=i;
  }
  lca.build(rt);

  for(int i=0;i+l<=n;i++){
    if(i) cout<<" ";
    cout<<vs[lca.lca(i,i+l-1)];
  }
  cout<<endl;
  return 0;
}