[NOIp2017提高组]列队

[NOIp2017提高组]列队

题目大意

一个(n imes m(n,mle3 imes10^5))的方阵，每个格子里的人都有一个编号。初始时第(i)行第(j)列的编号为((i-1)*m+j)。

(q(qle3 imes10^5))次事件，每次在((x,y))位置上的人离队。剩下的人向左、向前填补空位，然后离队的人在((n,m))处归队。

求每次离队事件中的人的编号。

思路：

对于每一行(1sim m-1)列建一棵线段树，对于最后一列也建一棵线段树。开同样数量的vector。

((x,y))离队时，在第(x)棵线段树上找到第(y)个未移动的值在vector中的位置，再从最后一列的线段树中找到第(x)个未移动的值加入第(x)个vector末尾，最后将答案加入最后一列对应vector末尾即可。

时间复杂度(mathcal O(qlog n))。

源代码：

#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
using int64=long long;
constexpr int N=3e5+2,SIZE=1e7;
int n,m,q,lim;
std::vector<int64> v[N];
class SegmentTree {
	#define mid ((b+e)>>1)
	private:
		struct Node {
			int val,left,right;
		};
		Node node[SIZE];
		int sz,new_node() {
			return ++sz;
		}
	public:
		int root[N];
		void modify(int &p,const int &b,const int &e,const int &x) {
			p=p?:new_node();
			node[p].val++;
			if(b==e) return;
			if(x<=mid) modify(node[p].left,b,mid,x);
			if(x>mid) modify(node[p].right,mid+1,e,x);
		}
		int query(const int &p,const int &b,const int &e,const int &k) {
			if(b==e) return b;
			const int tmp=mid-b+1-node[node[p].left].val;
			return k<=tmp?query(node[p].left,b,mid,k):query(node[p].right,mid+1,e,k-tmp);
		}
	#undef mid
};
SegmentTree t;
int64 del2(const int &x,const int64 &y) {
	const int tmp=t.query(t.root[n+1],1,lim,x);
	t.modify(t.root[n+1],1,lim,tmp);
	const int64 ans=tmp<=n?(int64)tmp*m:v[n+1][tmp-n-1];
	v[n+1].emplace_back(y?:ans);
	return ans;
}
int64 del1(const int &x,const int &y) {
	const int tmp=t.query(t.root[x],1,lim,y);
	t.modify(t.root[x],1,lim,tmp);
	const int64 ans=tmp<m?(int64)(x-1)*m+tmp:v[x][tmp-m];
	v[x].emplace_back(del2(x,ans));
	return ans;
}
int main() {
	n=getint(),m=getint(),q=getint();
	lim=std::max(n,m)+q;
	for(register int i=0;i<q;i++) {
		const int x=getint(),y=getint();
		printf("%lld
",y==m?del2(x,0):del1(x,y));
	}
	return 0;
}