洛谷P3960 列队 NOIp2017 线段树/树状数组/splay

时间：2021-09-15 02:53:07

正解:动态开点线段树

解题报告:

传送门!

因为最近学主席树的时候顺便get到了动态开点线段树?刚好想起来很久很久以前就想做结果一直麻油做的这题,,,所以就做下好了QAQ

然后说下,这题有很多种方法,我目前是先只写个最傻逼的方法,等学了splay什么的再来upd一下QAQ(这题好像有,线段树.树状数组.splay等各种方法,我可能都会写只要我麻油咕QAQ

然后就直接进入正题QAQ

首先其实要知道动态开点线段树和线段树思想什么的都是一样儿的,只是实现方法有一点儿区别(就是动态开点线段树节省点儿空间而已QAQ

所以就考虑线段树怎么做昂QAQ

首先可以发现,每次变动之后,有影响的只会是这个点,这一行,最后一列,对趴

所以可以考虑对每一行(不包括最后一个点QAQ)以及最后一列分别开个线段树

然后每次对当前操作(x,y),先记录ans,并把这个编号从x这一行的线段树中删去,加入第n+1棵树的最后一个位置，然后把第n+1棵的x位置加入到第x行的最后一个位置

然后注意以下如果x=n也就是说它本来就在最后一列的时候就不用管了QAQ

然后关于动态开点,我提下QAQ

考虑q的范围，即最多有q个点加入，那么线段树的长度最长为 max(n,m)+q

然后考虑到nmq范围,所以动态开点,over

然后再说一个方法,其实也是动态开点线段树,只是还要简单点儿,因为它还开了个vector

然后有vector的话就每次压进去就好了鸭,就是说线段树是个权值线段树记录被修改后的数字的,具体的值在vector中查询一下就好

具体看代码QAQ

然后记得开ll,,,我也不知道我什么猪脑子开了个int然后还麻油发现有什么不对,,,我都佩服我自己了QAQ

$upd:$半年后$gql$重新来康眼差点忘了咋做了,,,一句话总结就,$vector$存数值.线段树存下标,然后就可以资瓷删除操作了.

　　     另外安利$loj$最短代码,思想和我是一样的但代码绝短,,,$QAQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define rg register

#define gc getchar()

#define int long long

#define rp(i,x,y) for(rg ll i=x;i<=y;++i)

#define my(i,x,y) for(rg ll i=x;i>=y;--i)

const int N=3e5+,M=1e7+;

int n,m,q,rt[N],nod_cnt,mx;

struct sgtr{int ls,rs,sz;}tr[M];

vector<int>v[N];

il int read()

{

    rg char ch=gc;rg int x=;rg bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void modify(int &nw,int l,int r,int to)

{

    if(!nw)nw=++nod_cnt;++tr[nw].sz;if(l==r)return;

    int mid=(l+r)>>;

    if(to<=mid)modify(tr[nw].ls,l,mid,to);else modify(tr[nw].rs,mid+,r,to);

}

il int query(int nw,int l,int r,int to)

{

    if(l==r)return l;int mid=(l+r)>>,tmp=mid-l+-tr[tr[nw].ls].sz;

    if(to<=tmp)return query(tr[nw].ls,l,mid,to);return query(tr[nw].rs,mid+,r,to-tmp);

}

il int wk1(int x,int y)

{

    int pos=query(rt[n+],,mx,x);modify(rt[n+],,mx,pos);

    int ans=(pos<=n?1ll*pos*m:v[n+][pos-n-]);

    return v[n+].push_back(y?y:ans),ans;

}

il int wk2(int x,int y)

{

    int pos=query(rt[x],,mx,y);modify(rt[x],,mx,pos);

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

    return v[x].push_back(wk1(x,ans)),ans;

}

main()

{

//    freopen("ld.in","r",stdin);freopen("ld.out","w",stdout);

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

    while(q--){int x=read(),y=read();printf("%lld\n",(y==m?wk1(x,):wk2(x,y)));}

    return ;

}

先放下开vector做的代码QAQ(然后不开vector的代码可能就咕了QAQ?

相关文章