2019 CCPC 02题 主席树/线段树


HDU 6703 array

主席树做法

把一个数+1e7之后这个数在后面查询时就可以直接用了,我们把这个数放到$set$里,主席树先查询区间$(r+1,n)$中比$k$大的最小的数,这个区间指的是原数组区间。再在$set$里$lowerbound(k)$,取两者最小即可

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
const int N = 1e5 + 10;
int a[N], tot, n, m, q;
struct tree{
    int lc, rc, cnt;
}T[N * 32];
int root[N],vis[N];
set<int> s;
void build(int &rt, int l, int r)
{
    rt = ++tot;
    T[rt].cnt = 0;
    T[rt].lc = T[rt].rc = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(T[rt].lc, l, mid);
    build(T[rt].rc, mid + 1, r);
}
void update(int &cur, int pre, int l, int r, int pos, int val)
{
    cur = ++tot;
    T[cur] = T[pre];
    T[cur].cnt += val;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) update(T[cur].lc, T[pre].lc, l, mid, pos, val);
    else update(T[cur].rc, T[pre].rc, mid + 1, r, pos, val);
}
int query(int l,int r,int x,int y,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1,ans=n+1;
    if(k<=mid)
    {
        if(T[T[y].lc].cnt-T[T[x].lc].cnt) ans= query(l,mid,T[x].lc,T[y].lc,k);
        if(ans==n+1&&T[T[y].rc].cnt-T[T[x].rc].cnt ) ans=query(mid+1,r,T[x].rc,T[y].rc,k) ;
    }
    else
    {
        if(T[T[y].rc].cnt-T[T[x].rc].cnt )
            return query(mid+1,r,T[x].rc,T[y].rc,k);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        tot=0;
        s.clear();
        scanf("%d%d", &n, &q);
        root[0]=0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            update(root[i],root[i-1],1,n,a[i],1);
            vis[i]=0;
        }
        int lst=0,l,k,op,ans;
        for (int i = 1; i <= q; i++)
        {
            scanf("%d%d",&op,&l);
            if (op == 1)
            {
                l^=lst;
                if(!vis[l]) {
                    vis[l]=1;
                    s.insert(a[l]);
                }
            }
            else if(op==2)
            {
                scanf("%d",&k);
                l^=lst,k^=lst;
                auto it=s.lower_bound(k);
                if(l>=n) ans=n+1;
                else ans=query(1,n,root[l],root[n],k);
                if(it!=s.end()) ans=min(ans,*it);
                printf("%d\n",lst=ans);
            }
        }
    }

    return 0;
}

线段树做法

由于输入是$1-n$的一个全排列。$id[i]$代表$i$出现的位置(下标),我们根据$id$数组建立线段树,同时维护区间最大值(即区间内值出现的最大位置),因为答案必定在$(k,n+1)$内,查询即是查询区间$(k,n+1)$内,下标超过r的最小值是多少。修改操作即是把这个值的出现位置设为inf。查询的时候优先查询左区间,如果左区间在查询区间内并且左区间最值大于r,那就查询左区间,区间最值小于r就没有查询的必要了。否则右区间查询。

#include<bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
const int N = 1e5 + 10;
int id[N],MX[N<<2],a[N],n,q,tot;
void build(int rt,int l,int r)
{
    if(l==r){
        MX[rt]=id[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    MX[rt]=max(MX[ls],MX[rs]);
}
void update(int rt,int l,int r,int pos)
{
    if(l==r){
        MX[rt]=n+1;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(ls,l,mid,pos);
    else update(rs,mid+1,r,pos);
    MX[rt]=max(MX[ls],MX[rs]);
}
int query(int rt,int l,int r,int x,int y,int R)
{
    if(l==r) return l;
    int mid=(l+r)>>1,ans=-1;
    if(x<=mid&&MX[ls]>R) ans=query(ls,l,mid,x,y,R);
    if(ans==-1&&MX[rs]>R) ans=query(rs,mid+1,r,x,y,R);
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        tot=0;
        scanf("%d%d",&n,&q);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            id[a[i]]=i;
        }
        id[n+1]=n+1;
        build(1,1,n+1);
        int lst=0,l,k,op,ans;
        for (int i = 1; i <= q; i++)
        {
            scanf("%d%d",&op,&l);
            if (op == 1)
            {
                l^=lst;
                update(1,1,n+1,a[l]);
            }
            else if(op==2)
            {
                scanf("%d",&k);
                l^=lst,k^=lst;
                ans=query(1,1,n+1,k,n+1,l);
                printf("%d\n",lst=ans);
            }
        }
    }
    return 0;
}
Last modification:August 24th, 2019 at 10:32 pm
如果觉得我的文章对你有用,请随意赞赏