洛谷P3960 列队 NOIp2017 线段树/树状数组/splay
正解:动态开点线段树
解题报告:
因为最近学主席树的时候顺便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+100,M=1e7+1000;
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=0;rg bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),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)>>1;
if(to<=mid)modify(tr[nw].ls,l,mid,to);else modify(tr[nw].rs,mid+1,r,to);
}
il int query(int nw,int l,int r,int to)
{
if(l==r)return l;int mid=(l+r)>>1,tmp=mid-l+1-tr[tr[nw].ls].sz;
if(to<=tmp)return query(tr[nw].ls,l,mid,to);return query(tr[nw].rs,mid+1,r,to-tmp);
}
il int wk1(int x,int y)
{
int pos=query(rt[n+1],1,mx,x);modify(rt[n+1],1,mx,pos);
int ans=(pos<=n?1ll*pos*m:v[n+1][pos-n-1]);
return v[n+1].push_back(y?y:ans),ans;
}
il int wk2(int x,int y)
{
int pos=query(rt[x],1,mx,y);modify(rt[x],1,mx,pos);
int ans=(pos<m?1ll*(x-1)*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,0):wk2(x,y)));}
return 0;
}