HLOJ-DAY 6

Posted on By 张, 高畅 HLOJ-DAY 6无评论

什么已经第六天了！

什么今天还是数据结构！

[C]

原题

首先在这之前我们要了解笛卡尔树

（光速吟唱）

笛卡尔树是每一个节点由二元组组成的一棵树，其中前一维满足BST的性质，后一维满足Heap的性质。

而神奇的Treap其实就是前一维随机的一种笛卡尔树。

（吟唱完毕）

这一题就只需要 O(n) 的把笛卡尔树建出来，然后 dfs 访问就可以了。

#include
using namespace std;
const int N=1e5+5;
int n,p[N],stk[N],top;
int ls[N],rs[N];
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch57)
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>=48&&ch<=57)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
void dfs(int u)
{
    if(!u)return;
    printf("%d ",u);
    dfs(ls[u]);
    dfs(rs[u]);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        p[x]=i;
    }
    for(int i=1;i0&&p[stk[k]]>p[i])k--;
        if(k)rs[stk[k]]=i;
        if(k<top)ls[i]=stk[k+1];
        stk[top=++k]=i;
    }
    dfs(stk[1]);
    return 0;
}

[F]

原题

使用可持久化线段树维护区间的和/左边最大子段和/右边最大子段和。
注意合并时的细节。

#include
using namespace std;
const int N=20005;
int n;
paira[N];
struct node
{
    int sum,lmax,rmax;
    int ls,rs;
}tr[N<>1;
    build(tr[u].ls,l,mid);
    build(tr[u].rs,mid+1,r);
    pushup(u);
}
void modify(int root,int &u,int l,int r,int p)
{
    tr[u=++tot]=tr[root];
    if(l==r)
    {
        tr[u]={-1,-1,-1};
        return; 
    }
    int mid=l+r>>1;
    if(p<=mid)modify(tr[root].ls,tr[u].ls,l,mid,p);
    else modify(tr[root].rs,tr[u].rs,mid+1,r,p);
    pushup(u);
}
int query_sum(int u,int l,int r,int L,int R)
{
    if(L<=l&&r>1;
    if(Rmid)return query_sum(tr[u].rs,mid+1,r,L,R);
    else return query_sum(tr[u].ls,l,mid,L,mid)+query_sum(tr[u].rs,mid+1,r,mid+1,R);
}
int query_lmax(int u,int l,int r,int L,int R)
{
    if(L<=l&&r>1;
    if(Rmid)return query_lmax(tr[u].rs,mid+1,r,L,R);
    else return max(query_lmax(tr[u].ls,l,mid,L,mid),query_lmax(tr[u].rs,mid+1,r,mid+1,R)+query_sum(tr[u].ls,l,mid,L,mid));
}
int query_rmax(int u,int l,int r,int L,int R)
{
    if(L<=l&&r>1;
    if(Rmid)return query_rmax(tr[u].rs,mid+1,r,L,R);
    else return max(query_rmax(tr[u].rs,mid+1,r,mid+1,R),query_rmax(tr[u].ls,l,mid,L,mid)+query_sum(tr[u].rs,mid+1,r,mid+1,R));
}
int check(int a,int b,int c,int d,int x)
{
    int res=0;
    if(b+1=0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].first);
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    build(root[1],1,n);
    for(int i=2;i<=n+1;i++)modify(root[i-1],root[i],1,n,a[i-1].second);
    int q;
    scanf("%d",&q);
    int x=0;
    while(q--)
    {
        int b[4];
        for(int i=0;i<4;i++)
        {
            scanf("%d",&b[i]);
            b[i]=(b[i]+x)%n+1;
        }
        sort(b,b+4);
        int l=1,r=n;
        while(l>1;
            if(check(b[0],b[1],b[2],b[3],mid))l=mid;
            else r=mid-1;
        }
        printf("%d\n",x=a[l].first);
    }
    return 0;
}

[H]

原题
太有意思了。
其实可以不用离散化的。
首先判断出现次数为奇数次，我们考虑将每一个数附一个unsigned long long 内的一个随机的权值
因为unsigned long long的范围是 [0,2^{64}-1] 的，所以使用异或hash冲突的概率是足够小的。
然后考虑把这个东西拖到主席树内维护。
每一次询问实际上就是询问$root{l-1}与root{r}$的版本，我们只需要在主席树上二分就可以了。

#include<bits/stdc++.h>
#include<random>
using namespace std;
const int N=2e5+5,INF=2e9+5;
typedef long long LL;
typedef unsigned long long ULL;
LL n,m,tot,root[N];
mt19937 rd(random_device{}());
unordered_map<LL,ULL>mp;
struct node
{
    LL ls,rs;
    ULL w;
}tr[N<<5];
void pushup(int u){tr[u].w=tr[tr[u].ls].w^tr[tr[u].rs].w;}
void modify(LL root,LL &u,LL l,LL r,LL x,ULL v)
{
    tr[u=++tot]=tr[root];
    if(l==r)
    {
        tr[u].w^=v;
        return;
    }
    LL mid=l+r>>1;
    if(x<=mid)modify(tr[root].ls,tr[u].ls,l,mid,x,v);
    else modify(tr[root].rs,tr[u].rs,mid+1,r,x,v);
    pushup(u);
}
LL query(LL u1,LL u2,LL l,LL r)
{
    if(l==r)return l;
    ULL x=tr[tr[u1].ls].w^tr[tr[u2].ls].w;
    LL mid=l+r>>1;
    if(x)return query(tr[u1].ls,tr[u2].ls,l,mid);
    else return query(tr[u1].rs,tr[u2].rs,mid+1,r);
}
int main()
{
    scanf("%lld",&n);
    for(LL i=1,x;i<=n;i++)
    {
        scanf("%lld",&x);
        if(!mp[x])mp[x]=rd();
        modify(root[i-1],root[i],0,INF,x,mp[x]);
    }
    LL lastans=0;
    scanf("%lld",&m);
    while(m--)
    {
        LL l,r;
        scanf("%lld%lld",&l,&r);
        l^=lastans;
        r^=lastans;
        lastans=query(root[l-1],root[r],0,INF);
        if(lastans==INF)lastans=0;
        printf("%lld\n",lastans);
    }
    return 0;
}
训练日志

发表回复