[지속 가능 한 데이터 구조] 함수 식 선분 트 리

clj 논문 좋 네요.
전체적인 사상 은 값 만 부여 하고 수정 하지 않 는 동시에 역사 버 전 을 충분히 활용 하 는 것 이다. 바로 이 특성 때문에 온라인 으로 역사 버 전 을 문의 하 는 기능 을 완성 할 수 있다.
이 물건 은 접미사 자동 동기 와 달리 기본적으로 기 존의 지식 을 바탕 으로 직관 적 인 이 해 를 할 수 있다. 흔히 문 제 를 생각 할 때 어떤 사고 가 실현 되 지 못 한다 고 생각 되면 바로 총살 한다. 그러나 이런 것들 은 함수 식 프로 그래 밍 으로 쉽게 풀 릴 수 있다. 만약 에 예전 의 사고방식 으로 직접 걸 러 낼 수 있다 면 열 쇠 를 들 고 있 는데 하필 이면 그 문 이 열 리 지 않 는 다 고 생각 하 는 것 이다.그래서 이런 문제 에 있어 서 관건 은 함수 식 프로 그래 밍 의 장점 에 맞 추 는 것 이다.
poj 2104 구간 k 대 값
우 리 는 값 영역 을 제어 하 는 선분 나 무 를 유지 합 니 다. 만약 에 우리 가 필요 한 구간 의 값 영역 을 얻 었 다 고 가정 하면 조세 프 링 과 유사 한 검색 방식 (주로 내 가 처음으로 이런 검색 으로 만 든 것 은 조세 프 링 입 니 다. 사실은 왼쪽 구간 이 오른쪽 구간 인지 적시에 판단 하 는 것 입 니 다) 을 사용 하면 k 번 째 값 을 찾 을 수 있 습 니 다. 관건 은 이 선분 나 무 를 어떻게 얻 느 냐 하 는 것 입 니 다.
각각 요 소 를 삽입 하 는 것 을 고려 하여 i 번 째 로 저 장 된 선분 트 리 는 [1, i] 의 값 선분 트 리 입 니 다. 각 수의 존재 로 인해 구간 감법 을 만족 시 킵 니 다. [l, r] 에 대해 물 어보 면 그의 값 선분 트 리 의 각 노드 의 값 은 바로 역사 버 전 r 대응 노드 에서 l - 1 의 값 을 뺀 것 입 니 다. 그러면 logn 의 시간 에 질문 에 대답 하 는 데 편리 합 니 다.

#include 
#include 
#include 
int ans,n,m,a[100001],p[100001],u[100001],q[100001],ss,ne,mid,root[100001],lim;
int l[2000000],r[2000000],ls[2000000],rs[2000000],size[2000000];
inline void updata(int lson,int rson,int x)
{
  size[++ss]=size[x]+1;
  l[ss]=lson,r[ss]=rson,ls[ss]=ls[x],rs[ss]=rs[x];
}
inline void news(int x)
{
  l[x]=++ss,ls[ss]=ls[x],rs[ss]=(ls[x]+rs[x])/2;
  r[x]=++ss,ls[ss]=rs[ss-1]+1,rs[ss]=rs[x];
}
inline int change(int x,int w)
{
  if (ls[x]==rs[x]) {size[++ss]=size[x]+1,ls[ss]=rs[ss]=ls[x];return ss;}
  mid=(ls[x]+rs[x])/2;
  if (!l[x]) news(x);
  if (w<=mid) ne=change(l[x],w),updata(ne,r[x],x);
  else ne=change(r[x],w),updata(l[x],ne,x);
  return ss;
}
inline int ask(int i,int j,int k)
{
  for (int sum;ls[j]!=rs[j];) {
    if (!l[i]) news(i);
    if (!l[j]) news(j);
    sum=size[l[j]]-size[l[i]];
    if (sum

rank: 수 정 된 구간 k 대 값
마찬가지 로 값 영역 선분 트 리 를 유지 하지만 하나의 요소 의 수정 은 o (n) 의 선분 트 리 에 영향 을 줄 수 있 습 니 다. 그러면 우 리 는 나무 모양 배열 의 사상 으로 각 선분 트 리 에 i - lowbit (i) + 1 ~ i 의 구간 값 을 저장 합 니 다. 그러나 이렇게 하면 수정 없 이 i - 1 로 전달 할 수 없고 모든 선분 트 리 가 다시 열 립 니 다. o (nlogn * logn) 공간 만 소모 되 지만그러나 만약 에 함수 식 과 제 가 사전에 분 산 된 적 이 없다 면 (함수 식 은 온라인 문 제 를 해결 하 는 이기 이기 이기 때문에) 무려 170 + M 공간 을 사 용 했 습 니 다. 소박 한 선분 트 리 로 바 꾸 려 면 100 + M 공간 이 어야 합 니 다. 제 가 잘못 이해 한 것 이 라 고 의심 합 니 다.
함수 식

#include 
#include 
#include 
const int maxc=1000000000,max=15000000;
int size[max],l[max],r[max],root[100000],ss,mid,ne,ans,n,m,st[2][100000],t[2],a[100000];
void origin()
{
  for (int i=1;i<=n+1;i++) root[i]=i;
  ss=n+1;
}
inline void updata(int lson,int rson,int x,int w) {size[++ss]=size[x]+w;l[ss]=lson,r[ss]=rson;}
inline int change(int x,int ls,int rs,int y,int w)
{
  if (ls==rs) {updata(0,0,x,w);return ss;}
  mid=(ls+rs)>>1;
  if (y<=mid) ne=change(l[x],ls,mid,y,w),updata(ne,r[x],x,w);
  else ne=change(r[x],mid+1,rs,y,w),updata(l[x],ne,x,w);
  return ss;
}
inline int need(int e)
{
  int sum=0;
  for (int i=1;i<=t[e];i++) sum+=size[l[st[e][i]]];
  return sum;
}
inline void left(int e) {for (int i=1;i<=t[e];i++) st[e][i]=l[st[e][i]];}
inline void right(int e){for (int i=1;i<=t[e];i++) st[e][i]=r[st[e][i]];}
inline int ask(int ll,int rr,int k)
{
  t[0]=t[1]=0;
  int ls=1,rs=maxc;
  for (;ll;ll-=ll & -ll) st[0][++t[0]]=root[ll];
  for (;rr;rr-=rr & -rr) st[1][++t[1]]=root[rr];
  for (int sum1,sum2;ls!=rs;) {
    sum1=need(0),sum2=need(1);
    if (sum2-sum1>1)+1;
    else left(0),left(1),rs=(ls+rs)>>1;
  }
  return ls;
}
void init()
{
  int i,j,x,l,r,k;
  char ch;
  scanf("%d%d
",&n,&m);
  origin();
  for (i=1;i<=n;i++) {
    scanf("%d",&x);
    for (a[j=i+1]=x;j<=n+1;j+=j & -j) root[j]=change(root[j],1,maxc,x,1);
  }
  scanf("
");
  for (i=1;i<=m;i++) {
    scanf("%c",&ch);
    if ('Q'==ch) {
      scanf("%d%d%d
",&l,&r,&k);l++,r++;
      ans=ask(l-1,r,k);
      printf("%d
",ans);
    }
    else {
      scanf("%d%d
",&l,&x);l++;
      for (r=l;l<=n+1;l+=l & -l) root[l]=change(root[l],1,maxc,a[r],-1);a[r]=x;
      for (l=r;l<=n+1;l+=l & -l) root[l]=change(root[l],1,maxc,x,1);
    }
  }
}
int main()
{
  freopen("rank.in","r",stdin);
  freopen("rank.out","w",stdout);
   init();
  return 0;
}

검소 하 다

#include 
#include 
#include 
const int maxc=1000000000,max=8780000;
int size[max],l[max],r[max],root[100000],ss,mid,ne,ans,n,m,st[2][100000],t[2],a[100000];
void origin()
{
  for (int i=1;i<=n+1;i++) root[i]=i;
  ss=n+1;
}
inline void change(int x,int ls,int rs,int y,int w)
{
    size[x]+=w;
    if (ls==rs) return ;
    mid=(ls+rs)>>1;
    if (y<=mid) {
	if (!l[x]) l[x]=++ss;
	change(l[x],ls,mid,y,w);
    }
    else {
	if (!r[x]) r[x]=++ss;
	change(r[x],mid+1,rs,y,w);
    }
}
inline int need(int e)
{
  int sum=0;
  for (int i=1;i<=t[e];i++) sum+=size[l[st[e][i]]];
  return sum;
}
inline void left(int e) {for (int i=1;i<=t[e];i++) st[e][i]=l[st[e][i]];}
inline void right(int e){for (int i=1;i<=t[e];i++) st[e][i]=r[st[e][i]];}
inline int ask(int ll,int rr,int k)
{
  t[0]=t[1]=0;
  int ls=1,rs=maxc;
  for (;ll;ll-=ll & -ll) st[0][++t[0]]=root[ll];
  for (;rr;rr-=rr & -rr) st[1][++t[1]]=root[rr];
  for (int sum1,sum2;ls!=rs;) {
    sum1=need(0),sum2=need(1);
    if (sum2-sum1>1)+1;
    else left(0),left(1),rs=(ls+rs)>>1;
  }
  return ls;
}
void init()
{
  int i,j,x,l,r,k;
  char ch;
  scanf("%d%d
",&n,&m);
  origin();
  for (i=1;i<=n;i++) {
    scanf("%d",&x);
    for (a[j=i+1]=x;j<=n+1;j+=j & -j) change(root[j],1,maxc,x,1);
  }
  scanf("
");
  for (i=1;i<=m;i++) {
    scanf("%c",&ch);
    if ('Q'==ch) {
      scanf("%d%d%d
",&l,&r,&k);l++,r++;
      ans=ask(l-1,r,k);
      printf("%d
",ans);
    }
    else {
      scanf("%d%d
",&l,&x);l++;
      for (r=l;l<=n+1;l+=l & -l) change(root[l],1,maxc,a[r],-1);a[r]=x;
      for (l=r;l<=n+1;l+=l & -l) change(root[l],1,maxc,x,1);
    }
  }
}
int main()
{
  freopen("rank.in","r",stdin);
  freopen("rank.out","w",stdout);
   init();
  return 0;
}

spoj cot1
트 리 에 k 대 가 를 묻 기
유사 구간 k 대 치 사상 으로 i 번 째 요소 삽입 은 root [i] 라인 트 리 에서 수정 되 었 습 니 다. 물 어 볼 때 2 * lca 라인 트 리 의 값 을 뺀 것 입 니 다. 이런 문 제 는 모두 이 렇 습 니 다.

#include 
#include 
#include 
#include 
const int oo=1073741819;
int b,e,ne,mid,n,m,ans;
int root[100001],tail[100001],next[500000],sora[500000],f[100001][18],a[100001];
int l[2000000],r[2000000],size[2000000],ss,s1,d[100001],q[100001],u[100001],p[100001],st[100001];
void origin() {for (int i=1;i<=n;i++) tail[i]=i;s1=n;}
inline void updata(int lson,int rson,int x)
{
  size[++ss]=size[x]+1,l[ss]=lson,r[ss]=rson;
}
inline int change(int x,int ls,int rs,int y)
{
  if (ls==rs) {updata(0,0,x);return ss;}
  mid=(ls+rs)>>1;
  if (y<=mid) ne=change(l[x],ls,mid,y),updata(ne,r[x],x);
  else ne=change(r[x],mid+1,rs,y),updata(l[x],ne,x);
  return ss;
}
void bfs(int s)
{
  int h,r,i,ne,na,j,k;
  memset(d,127,sizeof(d));
  h=r=0;
  st[r=1]=s,d[s]=0;
  root[s]=change(0,1,n,p[s]);
  for (;hoo) d[na]=d[ne]+1,st[++r]=na,root[na]=change(root[ne],1,n,p[na]),f[na][0]=ne;
    }
  }
  k=(int)log2(d[st[r]]);
  for (j=1;j<=k;j++)
    for (i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
}
inline int ask(int i,int j,int v,int k)
{
  int ls=1,rs=n,sum;
  for (;ls!=rs;) {
    sum=size[l[i]]-(size[l[j]]<<1)+size[l[v]];
    if (p[ne]<=(ls+rs)>>1 && p[ne]>=ls) sum++;
    if (sum>1)+1;
    else i=l[i],j=l[j],v=l[v],rs=(ls+rs)>>1;
  }
  return q[ls];
}
inline int lca(int x,int y)
{
  if (d[x]>=1,b++) if (e&1) x=f[x][b];
  if (x==y) return x;
  for (e=1;;) {
    if (f[x][e]==f[y][e]) 
      if (e) e--;else break;
    else x=f[x][e],y=f[y][e],e++;
  }
  return f[x][e];
}
inline void link(int x,int y) 
{
  s1++,next[tail[x]]=s1,tail[x]=s1,sora[s1]=y;
  s1++,next[tail[y]]=s1,tail[y]=s1,sora[s1]=x;
}
inline int cmp(const void *i,const void *j) {return a[*(int *)i]-a[*(int *)j];}
void init()
{
  int i,x,y,k,l,r;
  scanf("%d%d
",&n,&m);
  origin();
  for (i=1;i<=n;i++) scanf("%d",&a[i]),u[i]=i;
  qsort(u+1,n,sizeof(u[1]),cmp);
  for (p[u[1]]=1,q[1]=a[u[1]],i=2;i<=n;i++) 
    if (a[u[i]]!=a[u[i-1]]) p[u[i]]=i,q[i]=a[u[i]];else p[u[i]]=p[u[i-1]];
  for (i=1;i<=n-1;i++) {
    scanf("%d%d
",&x,&y);
    link(x,y);
  }
  bfs(1);
  for (i=1;i<=m;i++) {
    scanf("%d%d%d
",&l,&r,&k);
    if (r==l) {printf("%d
",a[l]);continue;}
    ne=mid=lca(l,r);
    ans=ask(root[l],root[mid],root[r],k);
    printf("%d
",ans);
  }
}
int main()
{
  freopen("spojcot1.in","r",stdin);
  freopen("spojcot1.out","w",stdout);
   init();
  return 0;
}

clj middle
길이 가 n 인 서열 a 는 순 서 를 설정 한 후에 b 이 고 그 중에서 자릿수 는 b [n / 2] 로 정의 되 며 그 중에서 a, b 는 0 부터 레이 블 을 시작 하고 나 누 기 는 정 리 됩 니 다.n 길이 의 시퀀스 s 를 드 리 겠 습 니 다.Q 개의 이러한 질문 에 대답 합 니 다. s 의 왼쪽 점 은 [a, b] 사이 에 있 고 오른쪽 점 은 [c, d] 사이 의 하위 서열 에서 가장 큰 중위 입 니 다.그 중에서 a 위치 도 0 부터 레이 블 을 시작한다.나 는 몇 가지 방식 을 써 서 너 를 온라인 으로 강제 할 것 이다.
이 문 제 는 함수 식 프로 그래 밍 문제 풀이 에 대해 아직 완전히 익숙 하지 않다 는 것 을 나타 낸다. 한참 을 생각 했 지만 전통 적 인 해법 을 빙빙 돌 았 다. 마지막 으로 solution 의 힌트 를 보고 나 서 야 해법 을 생각해 냈 다.
우선 최대 중위 수 를 해결 하 는 데 자주 사용 되 는 방법 이다.(logn) 의 시간 완성 판단

#include 
#include 
#include 
int n,m,a[50000],u[50000],p[50000],q[50000],as[5],st[500000],tail[500000],next[500000],sora[500000],root[500000];
int sum[3000000],lsum[3000000],rsum[3000000],s1,ss,l[3000000],r[3000000],mid,ne,t,ans,e;
void origin() {for (int i=1;i<=n;i++) tail[i]=i;s1=n;}
inline int max(int x,int y) {return (x>y) ? x : y;}
inline void link(int x,int y) {s1++,next[tail[x]]=s1,tail[x]=s1,sora[s1]=y;}
inline void updata(int lson,int rson,int ls,int rs)
{
  int mid=(ls+rs)>>1;
  ss++,l[ss]=lson,r[ss]=rson;
  if (!l[ss] && !r[ss]) lsum[ss]=rsum[ss]=sum[ss]=-1;
  else if (!l[ss]) {
    sum[ss]=mid-ls+1+sum[r[ss]];
    lsum[ss]=mid-ls+1+max(0,lsum[r[ss]]);
    rsum[ss]=max(rsum[r[ss]],sum[ss]);
  }
  else if (!r[ss]) {
    sum[ss]=sum[l[ss]]+rs-mid;
    lsum[ss]=max(lsum[l[ss]],sum[ss]);
    rsum[ss]=rs-mid+max(0,rsum[l[ss]]);
  }
  else {
    sum[ss]=sum[l[ss]]+sum[r[ss]];
    lsum[ss]=max(lsum[l[ss]],sum[l[ss]]+lsum[r[ss]]);
    rsum[ss]=max(rsum[r[ss]],sum[r[ss]]+rsum[l[ss]]);
  }
}
inline int change(int x,int ls,int rs,int y)
{
  mid=(ls+rs)>>1;
  if (ls==rs) {updata(0,0,ls,rs);return ss;}
  if (y<=mid) ne=change(l[x],ls,mid,y),updata(ne,r[x],ls,rs);
  else ne=change(r[x],mid+1,rs,y),updata(l[x],ne,ls,rs);
  return ss;
}
inline void newsl(int x,int ls,int rs)
{
  int mid=(ls+rs)>>1;
  l[x]=++ss,sum[ss]=lsum[ss]=rsum[ss]=mid-ls+1;
}
inline void newsr(int x,int ls,int rs)
{
  int mid=(ls+rs)>>1;
   r[x]=++ss,sum[ss]=lsum[ss]=rsum[ss]=rs-mid;
}
inline void find(int x,int ls,int rs,int ll,int rr)
{
  if (ls==ll && rr==rs) {st[++t]=x;return ;}
  int mid=(ls+rs)>>1;
  if (rr<=mid) {
    if (!l[x]) newsl(x,ls,rs);
    find(l[x],ls,mid,ll,rr);
  }
  else if (ll>=mid+1) {
    if (!r[x]) newsr(x,ls,rs);
    find(r[x],mid+1,rs,ll,rr);
  }
  else {
    if (!l[x]) newsl(x,ls,rs);find(l[x],ls,mid,ll,mid);
    if (!r[x]) newsr(x,ls,rs);find(r[x],mid+1,rs,mid+1,rr);
  }
}
inline int check(int x)
{
  int ans=0,lans=0,rans=0,i;
  t=0,find(x,1,n,as[1],as[2]);
  for (i=t,ans=-1;i>=1;i--) {
    ans=max(ans,rsum[st[i]]+rans);
    rans+=sum[st[i]];
  }
  t=0;
  if (as[2]+1<=as[3]-1) find(x,1,n,as[2]+1,as[3]-1);
  for (i=1;i<=t;i++) ans+=sum[st[i]];
  t=0,find(x,1,n,as[3],as[4]);
  for (i=1,rans=-1;i<=t;i++) {
    rans=max(rans,lsum[st[i]]+lans);
    lans+=sum[st[i]];
  }
  ans+=rans;
  return ans;
}
inline int cmp(const void *i,const void *j) {return a[*(int *)i]-a[*(int *)j];}
void init()
{
  int i,j,k,l,r,mid,ne,maxc,h;
  scanf("%d
",&n);
  origin();
  for (i=1;i<=n;i++) scanf("%d
",&a[i]),u[i]=i;
  qsort(u+1,n,sizeof(u[1]),cmp);
  p[u[1]]=1;q[1]=a[u[1]];
  link(1,u[1]);
  for (i=2,k=1;i<=n;i++)
    if (a[u[i]]!=a[u[i-1]]) p[u[i]]=++k,q[k]=a[u[i]],link(k,u[i]);
    else p[u[i]]=k,link(k,u[i]);
  maxc=k,sum[0]=lsum[0]=rsum[0]=n;
  for (i=1,h=0;i<=maxc;i++) {
    for (j=i;next[j]!=0;) {
      j=next[j],ne=sora[j];
      root[i]=change(h,1,n,ne);
      h=root[i];
    }
  }
  scanf("%d
",&m);
  for (ans=0,i=1;i<=m;i++) {
    scanf("%d%d%d%d
",&as[1],&as[2],&as[3],&as[4]);
    // for (j=1;j<=4;j++) as[j]=(as[j]+ans)%n;
    // for (j=1;j<=3;j++)
    //   for (k=j+1;k<=4;k++)
    // 	if (as[j]>as[k]) e=as[j],as[j]=as[k],as[k]=e;
    for (j=1;j<=4;j++) as[j]++;
    for (l=1,r=maxc;l<=r;) {
      mid=(l+r)>>1;
      if (check(root[mid])>=0) l=mid+1;else r=mid-1;
    }
    ans=q[l];
    printf("%d
",ans);
  }
}
int main()
{
  freopen("middle.in","r",stdin);
  freopen("middle.out","w",stdout);
   init();
  return 0;
}

2010 천진 J

#include 
#include 
#include 
#include 
#include 
const long long lim=(1LL<<31);
using namespace std;
int ss,n;
int l[6000000],r[6000000];
long long ls[6000000],rs[6000000];
int size[6000000];
int root[2000000];
char ch[2000];
int ori()
{
    ++ss;
    l[ss]=r[ss]=ls[ss]=rs[ss]=0;
    size[ss]=0;
    return ss;
}
void origin()
{
    ss=0;
    root[0]=ori(),ls[ss]=1,rs[ss]=lim;
}
int updata(int lson,int rson,int x)
{
    ori();
    size[ss]=size[x]+1;
    l[ss]=lson,r[ss]=rson,ls[ss]=ls[x],rs[ss]=rs[x];
    return ss;
}
void news(int x)
{
    l[x]=ori(),ls[ss]=ls[x],rs[ss]=(ls[x]+rs[x])>>1;
    r[x]=ori(),ls[ss]=rs[ss-1]+1,rs[ss]=rs[x];
}
int change(int x,int w)
{
    if (ls[x]==rs[x]) {
        ori();
        size[ss]=size[x]+1,ls[ss]=rs[ss]=ls[x];
        return ss;
    }
    long long mid=((ls[x]+rs[x])>>1);
    if (!l[x]) news(x);
    if (w<=mid) {
        int ne=change(l[x],w);
        return updata(ne,r[x],x);
    }
    else {
        int ne=change(r[x],w);
        return updata(l[x],ne,x);
    }
}
long long ask(int L,int R,int k)
{
    int sum=0;
    L--;
    L=root[L],R=root[R];
    for (;ls[R]!=rs[R];) {
        if (!l[L]) news(L);
        if (!l[R]) news(R);
        sum=size[l[R]]-size[l[L]];
//        cout<>1;
        if (w<=mid) x=l[x];
        else {
            sum+=size[l[x]];
            x=r[x];
        }
    }
    sum+=size[x];
    return sum;
}
int main()
{
    for (int test=1;scanf("%d",&n)==1;test++) {
        printf("Case %d:
",test);
        origin();
        int tot=0;
        long long sum1=0,sum2=0,sum3=0;
        for (int i=1;i<=n;i++) {
            scanf("%s",ch+1);
            if (ch[1]=='I') {
                int x;
                scanf("%d",&x);
                ++tot;
                root[tot]=change(root[tot-1],x);
            }
            else if (ch[1]=='Q' && ch[7]=='1') {
                int L,R,k;
                scanf("%d%d%d",&L,&R,&k);
                int ans=ask(L,R,k);
//                printf("%d
",ans);
                sum1+=ans;
            }
            else if (ch[1]=='Q' && ch[7]=='2') {
                int x;
                scanf("%d",&x);
                int ans=ask2(tot,x);
//                printf("%d
",ans);
                sum2+=ans;
            }
            else if (ch[1]=='Q' && ch[7]=='3') {
                int k;
                scanf("%d",&k);
                int ans=ask(1,tot,k);
//                printf("%d
",ans);
                sum3+=ans;
            }
        }
        cout<