NOIP2017 Day2 T3 列队（treap）

　　可以直接用treap上大模拟...n+1个treap维护n行的前m-1个点和最后一列。

　　需要支持删除一个点或者一段区间，而空间并不支持存下所有的点的时候，可以用一个点代替一个区间，记录区间首项的值和区间长度，这样每次查询某个点x的时候就可以用x在某个点y代表的区间里的rank来得到x的值，然后把x删去的时候，就把y这个区间从$[l,r]$拆分成$[l,x-1]$和$[x+1,r]$，重新加入。

　　类似的题有NOI超级钢琴

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#define ll long long

#define int long long

#define lt tree[x].ls

#define rt tree[x].rs

using namespace std;

const int maxn=;

struct poi{ll beg; int rnd, size, ls, rs, len;}tree[maxn];

int n, m, Q, x, y, tott, tmp, rk;

ll ans;

int root[maxn], cnt[maxn], Len[maxn];

inline void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline void build(int &x, ll beg, int len)

{

    tree[x=++tott].beg=beg; tree[x].size=;

    tree[x].len=Len[x]=len;

    tree[x].rnd=rand()<<|rand();

}

inline void up(int x)

{

    tree[x].size=tree[lt].size+tree[rt].size+;

    tree[x].len=tree[lt].len+tree[rt].len+Len[x];

}

void split(int x, int &l, int &r, int k)

{

    if(!k) l=, r=x;

    else if(tree[x].size==k) l=x, r=;

    else if(tree[lt].size>=k) r=x, split(lt, l, lt, k), up(x);

    else l=x, split(rt, rt, r, k-tree[lt].size-), up(x);

}

void rank(int x, int k)

{

    if(tree[lt].len<k && tree[lt].len+Len[x]>=k) ans=k-tree[lt].len, rk+=tree[lt].size+;

    else if(k<=tree[lt].len) rank(lt, k);

    else rk+=tree[lt].size+, rank(rt, k-tree[lt].len-Len[x]);

}

void merge(int &x, int l, int r)

{

    if(!l || !r) x=l+r;

    else if(tree[l].rnd<tree[r].rnd) x=l, merge(rt, rt, r), up(x);

    else x=r, merge(lt, l, lt), up(x);

}

inline void disc(int &Root, ll &poi, int pos)

{

    int x, y;

    rk=; rank(Root, pos);

    split(Root, Root, y, rk); if(rk-) split(Root, Root, x, rk-); else x=Root;

    if(ans-) build(tmp, tree[x].beg, ans-), merge(Root, Root, tmp);

    if(Len[x]-ans) build(tmp, tree[x].beg+ans*(Root==root[n+]?m:), Len[x]-ans), merge(Root, Root, tmp);

    merge(Root, Root, y); poi=x;

}

inline ll query(int posx, int posy)

{

    if(posy!=m)

    {

        ll ANS, poi;

        disc(root[posx], poi, posy); ANS=tree[poi].beg+ans-;

        build(tmp, ANS, ); merge(root[n+], root[n+], tmp);

        disc(root[n+], poi, posx); poi=tree[poi].beg+(ans-)*m;

        build(tmp, poi, ); merge(root[posx], root[posx], tmp);

        return ANS;

    }

    ll poi;

    disc(root[n+], poi, posx); poi=tree[poi].beg+(ans-)*m;

    build(tmp, poi, ); merge(root[n+], root[n+], tmp);

    return poi;

}

#undef int

int main()

{

    srand();

    read(n); read(m); read(Q);

    for(int i=;i<=n;i++) build(root[i], 1ll*+(i-)*m, m-); build(root[n+], m, n);

    for(int i=;i<=Q;i++) read(x), read(y), printf("%lld\n", query(x, y));

}

　　线段树好写很多，而且非常快。

　　可以发现如果不是从最后一列加进来的数的话一定是递增的，那么这些数我们可以直接用n棵权值线段树来维护找第k大即可，把删点改为加点，就不会爆空间，然后剩下从最后一列加进来的直接丢进一个vector里面，如果查询的数不在线段树里就直接在vector里查询。最后一列维护的方法同理。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#include<vector>

#define ll long long

#define lt tree[x].ls

#define rt tree[x].rs

using namespace std;

const int maxn=;

struct poi{int ls, rs, size;}tree[maxn<<];

vector<ll>h[maxn];

int n, m, q, tott, x, y;

ll mx;

int root[maxn];

inline void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

void update(int &x, int l, int r, int cx)

{

    if(!x) x=++tott; tree[x].size++;

    if(l==r) return;

    int mid=(l+r)>>;

    if(cx<=mid) update(lt, l, mid, cx);

    else update(rt, mid+, r, cx);

}

int query(int x, int l, int r, int k)

{

    if(l==r) return l;

    int mid=(l+r)>>, lsize=mid-l+-tree[lt].size;

    if(lsize>=k) return query(lt, l, mid, k);

    return query(rt, mid+, r, k-lsize);

}

inline ll delr(int x, ll y)

{

    ll pos=query(root[n+], , mx, x); update(root[n+], , mx, pos);

    ll ans=pos<=n?1ll*pos*m:h[n+][pos-n-];

    h[n+].push_back(y?y:ans);

    return ans;

}

inline ll dell(int x, ll y)

{

    ll pos=query(root[x], , mx, y); update(root[x], , mx, pos);

    ll ans=pos<m?1ll*(x-)*m+pos:h[x][pos-m];

    h[x].push_back(delr(x, ans));

    return ans;

}

int main()

{

    read(n); read(m); read(q); mx=max(n, m)+q;

    for(int i=;i<=q;i++)

    {

        read(x); read(y);

        if(y==m) printf("%lld\n", delr(x, ));

        else printf("%lld\n", dell(x, y));

    }

}

巴特西

NOIP2017 Day2 T3 列队（treap）

最新文章

热门文章