「NOIP2017」列队 //线段树线段树

「NOIP2017」列队
放loj的题面好啦

题意
【「NOIP2017」列队 //线段树】有一个n行m列的方阵，第i行j列的点编号为(i-1)m+j。
给出q次操作，每次把第x行y列的点拿出来，然后把这一行它之后的点都向左推，把最后一列x行之后的点都向上推，然后把之前(x,y)的点放到最后一个位置，询问这个点的编号。

题解
//树状数组的做法我不会呀写一写暴力一些的做法吧
维护每一行和最后一列，于是需要实现的操作就变成了找到并删掉第k个数、把一个数插到末尾。
这东西是不是随便套个数据结构就好啦？
我写了个动态开点的线段树~~不会别的~~ 空间上来看是比较劣…不过512M就可以乱开了
初始状态怎么办呢…打一个等差数列的标记就好了

代码

#include #define V 15000000 #define N 300005 #define New(w) (w=(w?w:++cnt)) using namespace std; typedef long long ll; char ch; inline void rd(int &x) { x=0; do ch=getchar(); while(ch<'0'||ch>'9'); do x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); while(ch>='0'&&ch<='9'); } bool flag; int n,m,q,Rt,cnt,L,x,y, sz[V],c[V][2],rt[N],mx[V]; ll st[V],ans,tp; inline void pd(int x,int l,int r,int mid) { if(!st[x])return; sz[New(c[x][0])]=mx[c[x][0]]=mid-l+1; st[c[x][0]]=st[x]; sz[New(c[x][1])]=mx[c[x][1]]=r-mid+1; st[c[x][1]]=st[x]+(ll)(mid-l+1)*(flag?m:1); st[x]=0; } void build(int &x,int l,int r,int r_,ll fr) { sz[New(x)]=r_-l+1,mx[x]=r_-l+1; if(r==r_) {st[x]=fr; return; } int mid=l+r>>1; if(r_>mid)build(c[x][1],mid+1,r,r_,fr+(ll)(mid-l+1)*(flag?m:1)); build(c[x][0],l,mid,r_>1,sz[New(x)]++,mx[x]++; pd(x,l,r,mid); if(mx[c[x][0]]>1; pd(x,l,r,mid); return (loc>sz[c[x][0]])?qry(c[x][1],mid+1,r, loc-sz[c[x][0]]):qry(c[x][0],l,mid,loc); } int main() { rd(n),rd(m),rd(q); L=max(n,m)+q; for(int i=1; i<=n; i++) build(rt[i],1,L,m-1,(ll)(i-1)*m+1); flag=1,build(Rt,1,L,n,m); while(q--) { rd(x),rd(y); if(y^m) flag=0,printf("%lld\n",ans=qry(rt[x],1,L,y)), flag=1,tp=qry(Rt,1,L,x), ins(Rt,1,L,ans), flag=0,ins(rt[x],1,L,tp); else flag=1,printf("%lld\n",ans=qry(Rt,1,L,x)), ins(Rt,1,L,ans); } }