지속 가능 한 선분 트 리 노트

지속 가능 한 데이터 구 조 는 주로 역사 버 전 을 조회 하거나 역사 버 전 으로 돌아 가 는 작업 을 해결 합 니 다.지속 가능 한 라인 트 리 는 지속 가능 한 데이터 구조 이다.가장 간단 한 지속 가능 한 선분 나 무 를 만 드 는 방법 은 서로 다른 시간 에 새 선분 나 무 를 만 드 는 것 입 니 다. 현재 시간의 선분 나 무 는 이전 시간 에 복사 한 다음 에 현재 시간의 선분 나무 위 에서 수정 할 수 있 습 니 다.그러나 이러한 지속 가능 한 선분 트 리 는 메모 리 를 많이 소모 하고 감성 적 인 생각 이 있 습 니 다. 만약 에 현재 시간의 선분 트 리 와 이전 시간의 선분 트 리 가 공유 하 는 노드 가 있다 면 이런 노드 는 복사 하지 않 고 수정 할 노드 를 이전 시간의 선분 트 리 에 추가 로 연결 할 수 있 습 니 다.이렇게 하면 비교적 작은 메모리 사용량 을 소모 하여 매 시간의 선분 트 리 를 저장 할 수 있다.수정 할 노드 가 뿌리 부터 나무의 내부 까지 발 견 됩 니 다.대략 logn 개 입 니 다.이때 이 선분 나 무 는 이 진 트 리 의 노드 번호 성질 을 가지 지 않 고 좌우 아들 의 지침 을 추가 로 저장 해 야 한다.메모 리 를 절약 하기 위해 서 는 일반적으로 l, r, len 등 정 보 를 저장 하지 않 고 직접 계산한다.그리고 모든 시간의 선분 트 리 에 뿌리 를 저장 해 야 합 니 다.그 다음 에 예전 의 선분 나무의 조작 을 살 펴 보 겠 습 니 다. 1. 한 번 에 root [now] 라 는 뿌리 를 수정 한 다음 에 일반 선분 나무 와 차이 가 많 지 않 습 니 다.2. 루트 [now] 뿌리 에서 한 번 조회 한 다음 에 일반 라인 트 리 와 차이 가 많 지 않 습 니 다.3. 구간 수정 은 root [now] 이 뿌리 에서 들 어가 고 아래로 내 려 가 려 면 pushdown 이 필요 합 니 다. 구간 을 찾 아 표 시 를 하고 위로 돌아 갈 때 pushup 이 두 동작 은 새로 연 노드 를 기억 해 야 합 니 다.4. 구간 조 회 는 루트 [now] 뿌리 에서 들 어가 서 아래로 내 려 가 려 면 pushdown 이 필요 합 니 다. 새 노드 를 기억 하 세 요.그 다음 에 새로운 노드 는 일부 카드 메모리 의 문제 에서 매우 구 덩이 를 열 고 pushup, pushdown 해결 구간 수정 + 구간 조 회 를 하지 않 아 도 됩 니 다.대응 구간 에 표 시 를 하고 내 려 오지 마 세 요.아래로 내 려 갈 때 구간 마다 sum 조회 가 내 려 갈 때 지나 가 는 구간 마다 지나 가 는 구간 의 표 시 를 즉시 수정 해 야 합 니 다.

void add(int &now,int l,int r,int val,int L,int R)
{
    rec[++cnt]=rec[now];
    now=cnt;
    rec[now].sum+=1ll*val*(r-l+1);
    if(l==L&&r==R)
    {
        rec[now].lazy+=val;
        return;
    }
    if(r<=(L+R)/2)add(rec[now].lc,l,r,val,L,(L+R)/2);
    else if(l>(L+R)/2)add(rec[now].rc,l,r,val,(L+R)/2+1,R);
    else
    {
        add(rec[now].lc,l,(L+R)/2,val,L,(L+R)/2);
        add(rec[now].rc,(L+R)/2+1,r,val,(L+R)/2+1,R);
    }
}
ll query(int now,int l,int r,int L,int R)
{
    if(l==L&&r==R)return rec[now].sum;
    ll tmp=1ll*(r-l+1)*rec[now].lazy;
    if(r<=(L+R)/2)return tmp+query(rec[now].lc,l,r,L,(L+R)/2);
    if(l>(L+R)/2)return tmp+query(rec[now].rc,l,r,(L+R)/2+1,R);
    return tmp+query(rec[now].lc,l,(L+R)/2,L,(L+R)/2)+query(rec[now].rc,(L+R)/2+1,r,(L+R)/2+1,R);
}

그리고 이전 버 전 으로 돌아 가면 루트 [pre] 를 사용 하면 됩 니 다.HDU 4348 의 지속 가능 한 선분 트 리 노트 를 붙 입 니 다.구간 수정 + 구간 조회 + 지속 가능, 메모리 시간 복잡 도 nlogn, 공간 복잡 도 nlogn 주의

#include
#include
#include
#define ll long long
using namespace std;
struct node{
    ll sum,lazy;
    int lc,rc;
}rec[3000010];
int n,m,cnt,x,y,z,now,a[100010],rt[100010];
char op[3];
void build(int &now,int l,int r)
{
    rec[++cnt]=rec[now];
    now=cnt;
    if(l==r)
    {
        rec[now].sum=a[l];
        return;
    }
    build(rec[now].lc,l,(l+r)/2);
    build(rec[now].rc,(l+r)/2+1,r);
    rec[now].sum=rec[rec[now].lc].sum+rec[rec[now].rc].sum;
}
void add(int &now,int l,int r,int val,int L,int R)
{
    rec[++cnt]=rec[now];
    now=cnt;
    rec[now].sum+=1ll*val*(r-l+1);
    if(l==L&&r==R)
    {
        rec[now].lazy+=val;
        return;
    }
    if(r<=(L+R)/2)add(rec[now].lc,l,r,val,L,(L+R)/2);
    else if(l>(L+R)/2)add(rec[now].rc,l,r,val,(L+R)/2+1,R);
    else
    {
        add(rec[now].lc,l,(L+R)/2,val,L,(L+R)/2);
        add(rec[now].rc,(L+R)/2+1,r,val,(L+R)/2+1,R);
    }
}
ll query(int now,int l,int r,int L,int R)
{
    if(l==L&&r==R)return rec[now].sum;
    ll tmp=1ll*(r-l+1)*rec[now].lazy;
    if(r<=(L+R)/2)return tmp+query(rec[now].lc,l,r,L,(L+R)/2);
    if(l>(L+R)/2)return tmp+query(rec[now].rc,l,r,(L+R)/2+1,R);
    return tmp+query(rec[now].lc,l,(L+R)/2,L,(L+R)/2)+query(rec[now].rc,(L+R)/2+1,r,(L+R)/2+1,R);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        now=cnt=0;
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        build(rt[0],1,n);
        for(int i=1;i<=m;++i)
        {
            scanf("%s",op);
            if(op[0]=='C')
            {
                scanf("%d%d%d",&x,&y,&z);
                ++now;
                add(rt[now]=rt[now-1],x,y,z,1,n);
            }
            else if(op[0]=='Q')
            {
                scanf("%d%d",&x,&y);
                printf("%I64d
",query(rt[now],x,y,1,n));
            }
            else if(op[0]=='H')
            {
                scanf("%d%d%d",&x,&y,&z);
                printf("%I64d
",query(rt[z],x,y,1,n));
            }
            else scanf("%d",&now);
        }
    }
}

그 다음 에 지속 적 인 라인 트 리 는 전형 적 인 문 제 를 해결 할 수 있다. 동적 구간 이 k 번 째 로 크다.먼저 수정 되 지 않 은 동적 구간 k 가 크다.구간 안의 모든 수 를 지구 화 가능 한 선분 트 리 에 순서대로 꽂 아 라.시간 버 전 을 삽입 할 때마다 변경 해 야 합 니 다.그러면 뿌리 가 root [r] 와 root [l - 1] 인 두 개의 선분 나무 에 대해 한 그루 는 l - 1 개의 수 를 삽입 한 선분 나무 이 고 하 나 는 r 개의 수 를 삽입 한 선분 나무 이다. 이 두 개의 선분 나무 에 대해 만약 에 두 개의 선분 나무의 왼쪽 나무의 size 차이 가 t 라면 [l, r] 사이 에 t 의 수가 mid 보다 작 다 는 것 을 의미한다.mid 는 당직 구역 의 절반 이다.이 성질 을 이용 하여 구간 k 가 크 면 할 수 있다.그리고 이와 유사 한 변형 도 있 습 니 다. 1. 조회 [l, r] 사이 에 x 와 같은 수의 개수 보다 작 습 니 다. 선분 나무 에서 2 분 에 x 를 찾 고 오른쪽 나무 로 가면 왼쪽 나무 두 그루 의 크기 차 이 를 더 해 야 합 니 다. 잎 에 가면 두 그루 의 나무 라 는 잎 sz 의 차 이 를 더 해 야 합 니 다.2. 트 리 에서 u 에서 v 까지 의 간단 한 경 로 를 조회 하 는 점 권 이 k 번 째 로 크다. 모든 점 에 대해 이 점 에서 뿌리 까지 의 지속 가능 한 라인 트 리 를 유지 합 니 다.아 날로 그 동적 구간 의 k 번 째 큰 안 에는 모든 수 에 대해 첫 번 째 수의 지속 가능 한 선분 수 를 유지 합 니 다.u 와 v 의 lca 를 t 로 설정 하면 뿌리 는 root [u], root [v], root [t], root [fa [t] 의 이 네 개의 선분 나 무 를 설정 하고 sum = size [lc [root [u]]] + size [lc [root [v]] - size [lc [root [t]]] - size [lc [root [t]]]]]]]] 를 설정 하면 sum 은 무엇 을 대표 합 니까?sum 은 u 에서 v 까지 의 간단 한 경 로 를 대표 하 는 sum 의 점 이 mid 보다 작 습 니 다.코드 를 붙 여 SPOJ COT 조회 트 리 에 u 에서 v 까지 의 간단 한 경로 의 점 권 k 번 째 시간 복잡 도 logn, 공간 복잡 도 logn

#include
#include
#include
#include
using namespace std;
struct node{
    int v,next;
}edge[200010];
int lc[2000010],rc[2000010],cnt[2000010],sorted[100010],a[100010],rt[100010],fa[100010],son[100010],sz[100010],top[100010],dep[100010],head[100010],n,m,u,v,k,len,tot,ecnt;
void addedge(int u,int v)
{
    edge[ecnt].v=v;
    edge[ecnt].next=head[u];
    head[u]=ecnt++;
}
void insert(int &now,int pos,int l,int r)
{
    ++tot;
    lc[tot]=lc[now];
    rc[tot]=rc[now];
    cnt[tot]=cnt[now]+1;
    now=tot;
    if(l==r)return;
    if(pos<=(l+r)/2)insert(lc[now],pos,l,(l+r)/2);
    else insert(rc[now],pos,(l+r)/2+1,r);
}
void dfs1(int u,int f)
{
    sz[u]=1;
    int maxch=0;
    for(int i=head[u];~i;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v!=f)
        {
            dep[v]=dep[u]+1;
            fa[v]=u;
            dfs1(v,u);
            sz[u]+=sz[v];
            if(maxchint u,int t)
{
    int pos=lower_bound(sorted+1,sorted+len+1,a[u])-sorted;
    insert(rt[u]=rt[fa[u]],pos,1,len);
    top[u]=t;
    if(son[u]==0)return;
    dfs2(son[u],t);
    for(int i=head[u];~i;i=edge[i].next)
        if(edge[i].v!=son[u]&&edge[i].v!=fa[u])
            dfs2(edge[i].v,edge[i].v);
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]return dep[u]int find(int u,int v,int t,int fat,int l,int r,int k)
{
    if(l==r)return l;
    int sum=cnt[lc[u]]+cnt[lc[v]]-cnt[lc[t]]-cnt[lc[fat]];
    if(k<=sum)return find(lc[u],lc[v],lc[t],lc[fat],l,(l+r)/2,k);
    else return find(rc[u],rc[v],rc[t],rc[fat],(l+r)/2+1,r,k-sum);
}
int main()
{
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),sorted[i]=a[i];
    sort(sorted+1,sorted+n+1);
    len=unique(sorted+1,sorted+n+1)-sorted-1;
    for(int i=1;i"%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    fa[1]=0;
    dep[1]=1;
    dfs1(1,-1);
    dfs2(1,1);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&k);
        int t=lca(u,v);
        printf("%d
",sorted[find(rt[u],rt[v],rt[t],rt[fa[t]],1,len,k)]);
    }
}

그리고 한 점 으로 수정 할 수 있 는 동적 구간 k 가 크다.이 때 는 지속 가능 한 선분 트 리 만 사용 하면 안 됩 니 다. 한 노드 를 수정 하면 앞으로 많은 역사 버 전이 수 정 될 것 입 니 다.예전 에 우리 가 동적 구간 k 가 컸 을 때 지구 화 선분 수 는 매번 이전 시간 에 수정 되 었 는데 마치 접 두 사 를 구 하 는 것 과 같 았 다.따라서 한 그루 의 선분 나무 가 수정 되 었 을 때 약 n 개의 선분 나무 가 누적 되 어 올 라 온 선분 나무 가 수정 되 어야 한다.그래서 우 리 는 나무 모양 의 배열 을 사용 할 생각 이다.예전 에 트 리 배열 에서 접 두 사 를 구 했 던 것 처럼 이번 에는 접두사 와 대상 을 지속 가능 한 선분 트 리 로 바 꾸 었 습 니 다. 그러면 시간 이 logn 의 시간 을 더 소모 하 게 되 었 습 니 다.하지만 이후 의 수정 도 logn 만 필요 합 니 다.

#include
#include
#include
#include
using namespace std;
int lc[10000010],rc[10000010],cnt[10000010],data[10010][4],rt[50010],a[50010],lseg[510],rseg[510],sorted[60010],n,m,tot,len;
char op[3];
int lowbit(int x)
{
    return x&-x;
}
int newnode(int c,int l,int r)
{
    ++tot;
    lc[tot]=l;
    rc[tot]=r;
    cnt[tot]=c;
    return tot;
}
void build(int &x,int l,int r)
{
    x=newnode(0,0,0);
    if(l==r)return;
    build(lc[x],l,(l+r)/2);
    build(rc[x],(l+r)/2+1,r);
}
int find(int l,int r,int k)
{
    if(l==r)return l;
    int sum=0;
    for(int i=1;i<=rseg[0];++i)
        sum+=cnt[lc[rseg[i]]];
    for(int i=1;i<=lseg[0];++i)
        sum-=cnt[lc[lseg[i]]];
    if(k<=sum)
    {
        for(int i=1;i<=rseg[0];++i)
            rseg[i]=lc[rseg[i]];
        for(int i=1;i<=lseg[0];++i)
            lseg[i]=lc[lseg[i]];
        return find(l,(l+r)/2,k);
    }
    else
    {
        for(int i=1;i<=rseg[0];++i)
            rseg[i]=rc[rseg[i]];
        for(int i=1;i<=lseg[0];++i)
            lseg[i]=rc[lseg[i]];
        return find((l+r)/2+1,r,k-sum);
    }
}
void insert(int pre,int &now,int pos,int val,int l,int r)
{
    now=newnode(cnt[pre]+val,lc[pre],rc[pre]);
    if(l==r)return;
    if(pos<=(l+r)/2)insert(lc[pre],lc[now],pos,val,l,(l+r)/2);
    else insert(rc[pre],rc[now],pos,val,(l+r)/2+1,r);
}
void modify(int now,int pos,int val)
{
    int tmp;
    while(now<=n)
    {
        insert(rt[now],tmp,pos,val,1,len);
        rt[now]=tmp;
        now+=lowbit(now);
    }
}
int query(int l,int r,int k)
{
    lseg[0]=rseg[0]=0;
    while(l)
    {
        lseg[++lseg[0]]=rt[l];
        l-=lowbit(l);
    }
    while(r)
    {
        rseg[++rseg[0]]=rt[r];
        r-=lowbit(r);
    }
    return find(1,len,k);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),sorted[++sorted[0]]=a[i];
    for(int i=1;i<=m;++i)
    {
        scanf("%s",op);
        if(op[0]=='Q')
        {
            data[i][0]=0;
            scanf("%d%d%d",&data[i][1],&data[i][2],&data[i][3]);
        }
        else
        {
            data[i][0]=1;
            scanf("%d%d",&data[i][1],&data[i][2]);
            sorted[++sorted[0]]=data[i][2];
        }
    }
    sort(sorted+1,sorted+sorted[0]+1);
    len=unique(sorted+1,sorted+sorted[0]+1)-sorted-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(sorted+1,sorted+len+1,a[i])-sorted;
    build(rt[0],1,len);
    for(int i=1;i<=n;++i)
        modify(i,a[i],1);
    for(int i=1;i<=m;++i)
    {
        if(!data[i][0])printf("%d
",sorted[query(data[i][1]-1,data[i][2],data[i][3])]);
        else
        {
            modify(data[i][1],a[data[i][1]],-1);
            a[data[i][1]]=lower_bound(sorted+1,sorted+len+1,data[i][2])-sorted;
            modify(data[i][1],a[data[i][1]],1);
        }
    }
}