【线段树动态开点】NOIP2017 列队

题面自取

​

由于对齐的操作很难实现，可以把离队的人的位置空出来

因为操作次数是有限的，直接把加入的人放在末尾

用线段树维护区间内被删除的位置个数，询问就是找第y个没被删除的位置

这样每行开一个线段树，最后一列也开一个线段树，动态开点。

要注意不断操作后序列是乱的，如果询问得到的位置小于m，可以直接计算出这个位置的编号

否则大于m的部分用vector记录每个位置编号

​

示例程序：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
inline char nc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
	int res=0,f=1;char ch=nc();
	while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
	while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
	return res*f;
}

const int maxn=300005,maxs=12000005;
int n,m,q,M;
int s[maxs],ls[maxs],rs[maxs],Rot[maxn],len;
inline void pushup(int x) {s[x]=s[ls[x]]+s[rs[x]];}
void ist(int &x,int l,int r,int k){
	if (!x) x=++len;
	if (l==r) return (void)(s[x]=1,x);
	int mid=l+r>>1;
	if (k<=mid) ist(ls[x],l,mid,k);else ist(rs[x],mid+1,r,k);
	pushup(x);
}
int qry(int x,int l,int r,int k){
	if (l==r) return l;
	int mid=l+r>>1,tem=mid-l+1 - s[ls[x]];
	if (k<=tem) return qry(ls[x],l,mid,k);else return qry(rs[x],mid+1,r,k-tem);
}
vector<ll> V[maxn];
ll work0(int x,ll w){
	int p=qry(Rot[0],1,M,x); ist(Rot[0],1,M,p);
	ll res=(p<=n)?(ll)p*m:V[0][p-n-1];
	V[0].push_back(w?w:res);
	return res;
}
ll work1(int x,int y){
	int p=qry(Rot[x],1,M,y); ist(Rot[x],1,M,p);
	ll res=(p<m)?((ll)x-1)*m+p:V[x][p-m];
	V[x].push_back(work0(x,res));
	return res;
}
int main(){
	n=red(),m=red();q=red();M=max(n,m)+q;
	while (q--){
		int x=red(),y=red();
		printf("%lld\n",y==m?work0(x,0):work1(x,y));
	}
	return 0;
}