luogu3960 列队

参考这篇
#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

typedef long long ll;

int n, m, q, maxn, rot[300005], cnt, uu, vv;

ll ans;

vector<ll> vec[300005];

struct Node{

	int l, r, sum;

}nd[11000005];

int queryPos(int o, int l, int r, int x){

	if(l==r)	return l;

	else{

		int mid=(l+r)>>1;

		int siz=mid-l+1-nd[nd[o].l].sum;

		if(x<=siz)	return queryPos(nd[o].l, l, mid, x);

		else	return queryPos(nd[o].r, mid+1, r, x-siz);

	}

}

void shanchu(int &o, int l, int r, int x){

	if(!o)	o = ++cnt;

	nd[o].sum++;

	if(l==r)	;

	else{

		int mid=(l+r)>>1;

		if(x<=mid)	shanchu(nd[o].l, l, mid, x);

		else	shanchu(nd[o].r, mid+1, r, x);

	}

}

void delCol(int x){

	int pos=queryPos(rot[n+1], 1, maxn, x);

	shanchu(rot[n+1], 1, maxn, pos);

	if(pos<=n)	ans = (ll)m * pos;

	else	ans = vec[n+1][pos-n-1];

}

void delRow(int uu, int vv){

	int pos=queryPos(rot[uu], 1, maxn, vv);

	shanchu(rot[uu], 1, maxn, pos);

	delCol(uu);

	vec[uu].push_back(ans);

	if(pos<=m-1)	ans = (ll)m * (uu - 1) + pos;

	else	ans = vec[uu][pos-m];

}

int main(){

	cin>>n>>m>>q;

	maxn = max(n, m) + q;

	while(q--){

		scanf("%d %d", &uu, &vv);

		if(vv==m)	delCol(uu);

		else	delRow(uu, vv);

		printf("%lld\n", ans);

		vec[n+1].push_back(ans);

	}

	return 0;

}
巴特西

luogu3960 列队

最新文章

热门文章
