HDU 5919 Sequence II [主席树]【数据结构】

然后他说在询问区间,不相同元素第一次出现的位置的中间那个,
如果是从正序挂到主席树上的话确实不好维护,
考虑倒叙插入到主席树上,那么每次都只会记录最左边的数,更新的时候如过当前数出现过就删去之前的那个,
就不需要排序过程了,只需要在区间内找第中间的那个就行了
查询的时候我们只要对rt[l]进行查找就行了
于是就变成了找区间内不同数的个数,
然后找区间内第k大的问题,

这样的话就是主席树的基本操作了,

总体复杂度

附本题代码
——————————————————————————————————————————————

#include <bits/stdc++.h>@H_404_11@

using namespace std;

/**********************************/@H_404_11@

const int@H_404_11@ N = 2@H_404_11@e5+7@H_404_11@;

int@H_404_11@ n,m@H_404_11@,ans;
int@H_404_11@ a[N],vis[N];

void so(int@H_404_11@ &l,int@H_404_11@ &r){
    int@H_404_11@ tem=(l+ans)%n@H_404_11@+1@H_404_11@;
    int@H_404_11@ tmp=(r+ans)%n@H_404_11@+1@H_404_11@;
    l=(tem<tmp)?tem:tmp;
    r=(tem>tmp)?tem:tmp;
}

int@H_404_11@ rt[N],ls[N*40@H_404_11@],rs[N*40@H_404_11@],sum[N*40@H_404_11@],tot;
void build(int@H_404_11@& rt,int@H_404_11@ l,int@H_404_11@ r){
    rt=++tot;
    sum[rt]=0@H_404_11@;
    if@H_404_11@(l>=r)return@H_404_11@;
    int@H_404_11@ m@H_404_11@=((r-l)>>1@H_404_11@)+l;
    build(ls[rt],l,m@H_404_11@);
    build(rs[rt],m@H_404_11@+1@H_404_11@,r);
}

void update(int@H_404_11@& rt,int@H_404_11@ r,int@H_404_11@ last@H_404_11@,int@H_404_11@ pos@H_404_11@,int@H_404_11@ v){
    rt=++tot;
    ls[rt]=ls[last@H_404_11@];
    rs[rt]=rs[last@H_404_11@];
    sum[rt]=sum[last@H_404_11@]+v;
    if@H_404_11@(l>=r)return@H_404_11@;
    int@H_404_11@ m@H_404_11@=((r-l)>>1@H_404_11@)+l;
    if@H_404_11@(pos@H_404_11@<=m@H_404_11@) update(ls[rt],ls[last@H_404_11@],pos@H_404_11@,v);
    else@H_404_11@       update(rs[rt],r,rs[last@H_404_11@],v);
}

int@H_404_11@ query_num(int@H_404_11@ rt,int@H_404_11@ L,int@H_404_11@ R){
    if@H_404_11@(L<=l&&r<=R) return@H_404_11@ sum[rt];
    int@H_404_11@ m@H_404_11@=((r-l)>>1@H_404_11@)+l;
    int@H_404_11@ ans=0@H_404_11@;
    if@H_404_11@(L<=m@H_404_11@) ans+=query_num(ls[rt],L,R);
    if@H_404_11@(R> m@H_404_11@) ans+=query_num(rs[rt],R);
    return@H_404_11@ ans;
}

int@H_404_11@ query_id(int@H_404_11@ rt,int@H_404_11@ k){
    if@H_404_11@(l>=r)return@H_404_11@ l;
    int@H_404_11@ m@H_404_11@=((r-l)>>1@H_404_11@)+l;
    int@H_404_11@ cnt = sum[ls[rt]];
    if@H_404_11@(k<=cnt) return@H_404_11@ query_id(ls[rt],k);
    else@H_404_11@       return@H_404_11@ query_id(rs[rt],k-cnt);
}

int@H_404_11@ main(){
    int@H_404_11@ _@H_404_11@=1@H_404_11@,kcase=0@H_404_11@;
    scanf("%d@H_404_11@"@H_404_11@,&_@H_404_11@);
    while@H_404_11@(_@H_404_11@--){
        memset(vis,0@H_404_11@,sizeof(vis));

        ans = 0@H_404_11@;
        scanf("%d@H_404_11@%d@H_404_11@"@H_404_11@,&n,&m@H_404_11@);
        for@H_404_11@(int@H_404_11@ i=1@H_404_11@;i<=n;i++) scanf("%d@H_404_11@"@H_404_11@,&a[i]);

        tot = 0@H_404_11@;
        build(rt[n+1@H_404_11@],1@H_404_11@,n);

        for@H_404_11@(int@H_404_11@ i=n,tem;i;i--){
            tem=rt[i+1@H_404_11@];
            if@H_404_11@(vis[a[i]])update(tem,n,rt[i+1@H_404_11@],vis[a[i]],-1@H_404_11@);
            update(rt[i],tem,i,1@H_404_11@);
            vis[a[i]]=i;
        }
        printf@H_404_11@("Case #%d@H_404_11@:"@H_404_11@,++kcase);
        for@H_404_11@(int@H_404_11@ i=1@H_404_11@,id;i<=m@H_404_11@;i++){
            scanf("%d@H_404_11@%d@H_404_11@"@H_404_11@,&l,&r);
            so(l,r);
//@H_404_11@            printf@H_404_11@("[%d@H_404_11@,%d@H_404_11@]"@H_404_11@,r);
            id = query_num(rt[l],r);
//@H_404_11@            printf@H_404_11@(" %d@H_404_11@<="@H_404_11@,id);
            id =(id+1@H_404_11@)>>1@H_404_11@;
            ans=query_id(rt[l],id);
            printf@H_404_11@(" %d@H_404_11@"@H_404_11@,ans);
        }
        puts(""@H_404_11@);
    }
    return@H_404_11@ 0@H_404_11@;
}

原文链接：https://www.f2er.com/datastructure/382329.html

HDU 5919 Sequence II [主席树]【数据结构】

猜你在找的数据结构相关文章