自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 21:54:37，当前版本为作者最后更新于2018-01-06 16:04:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我是洛谷全站跑得最快的，1488ms。 使用筛选最优解的新功能就可以找到我。 使用的是 NOIP 范围的算法，不是平衡树，是树状数组。

考虑前 $50 \%$：

观察到 $q \leq 500$，也就是说有效的行数不超过 $500$ 行。

我们把行数离散化。

那么需要维护的数的数量最多只有 $q (m - 1) + n$ 个

一次操作的复杂度最多是 $n + m - 1$。

那么时间复杂度 $\mathcal O (q \log q + q (n + m - 1))$，空间复杂度$\mathcal O (q (m - 1) + n)$。

再看接下来的 $30 \%$：

发现有 $x_i = 1$，也就是说，有效的格子只有第一行和最后一列。

我们把第一行和最后一列压到一起去，那么我们要对这个序列支持：

1. 删除第 $k$ 个元素

2. 在末尾添加一个元素

这个操作能用平衡树实现，但是我用树状数组来实现。

用树状数组维护一个 01 序列，第 $i$ 位上是 0 表示这个位置上的数已经被删除了或者还没有被插入，第 $i$ 位上是 1 表示这一位上的数没有被删除。

那么删除操作就是 $1 \to 0$，插入操作就是 $0 \to 1$。

第 $k$ 个元素就是前缀和为 $k$ 的位置。

对于查找这个位置的操作，我使用树状数组二分，具体见代码，时间 $\mathcal O (\log n)$。

那么最后的 $20 \%$ 呢？

定义一行中原来的元素为初始时这一行前 $m - 1$ 个元素中，没有离队过的元素。

我们观察到对于本来就在这一行中的元素，我们可以直接算出它的值，而不用存储。

那么我们判断每一次询问是不是在本行的原来的元素中，如果是，直接判断掉。

那么每一行的“非原来的元素”有多少个呢？

我们不知道一行会有多少个，但是我们知道，所有行的这样的元素个数的总和不超过 $q$ 个。

这启发了我们对于每一行，只对其“非原来的元素”开一个树状数组维护。

而对于“原来的元素”，我们直接离线预处理。

预处理时需要对所有的询问按照 $x_i$ 为第一关键字，询问编号为第二关键字排序。

再对最后一列单独处理。

时间复杂度 $\mathcal O (q \log q + q \log m + q \log (n + q))$，空间复杂度 $O(n + m + q)$。

具体看代码吧！

代码：

#pragma GCC optimize("O2")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;++i)
#define dF(i,a,b) for(int i=a;i>=b;--i)
#define F2(i,a,b) for(int i=a;i<b;++i)
#define getchar() (SS==TT&&(TT=(SS=BB)+fread(BB,1,1<<15,stdin),TT==SS)?EOF:*SS++)
#define RR register
char BB[1<<15],*SS=BB,*TT=BB;
inline int read(){
	RR int x;RR bool f;RR char c;
	for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
	for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');
	return f?-x:x;
}
using namespace std;
int q,I[300010];
long long n,m,a[300010],b[300010];
inline bool cmp(int p1,int p2){return a[p1]==a[p2]?p1<p2:a[p1]<a[p2];}
int h[300010],len[300010],len2[300010],bit[900010];
long long arr[900010];
long long Ans[300010];
inline void Ins(int*array,int siz,int i,int x){for(;i<=siz;array[i]+=x,i+=i&-i);}
inline int binary(int*array,int siz,int x){
	int l=1,r,mid,sum,ans;
	while(l<=siz&&array[l]<x) l<<=1, ans=l;
	r=l; sum=array[l>>=1];
	while(l<r-1){
		mid=l+r>>1;
		if(mid>siz||array[mid]+sum>=x) r=mid, ans=mid;
		else l=mid, sum+=array[l];
	} ans=r;
	return ans;
}
int stk[300001],top;
int main(){
	n=read(), m=read(), q=read();
	F(i,1,q) a[i]=read(), b[i]=read(), I[i]=i;
	sort(I+1,I+q+1,cmp);
	F(i,1,m-1) Ins(bit,m-1,i,1);
	F(i,1,n) len[i]=m-1;
	F(i,1,q){
		if(a[I[i-1]]!=a[I[i]])
			while(top) Ins(bit,m-1,stk[top--],1);
		if(b[I[i]]>len[a[I[i]]]) continue;
		int pos=binary(bit,m-1,b[I[i]]);
		Ans[I[i]]=(a[I[i]]-1)*m+pos;
		Ins(bit,m-1,pos,-1);
		stk[++top]=pos;
		--len[a[I[i]]];
	}
	int iter=0;
	F(i,1,n){
		while(iter<=q&&a[I[iter]]<i) ++iter;
		h[i]=iter-1;
	}
	h[n+1]=q;
	memset(bit,0,sizeof bit);
	F(i,1,n) len[i]=0, len2[i]=m-1; len[n+1]=n;
	F(i,1,n) Ins(bit+h[n+1],n+q,i,1), arr[q+i]=i*m;
	F(i,1,q){
		if(Ans[i]){
			int pos=binary(bit+h[n+1],n+q,a[i]);
			Ins(bit+h[n+1],n+q,pos,-1);
			Ins(bit+h[n+1],n+q,++len[n+1],1);
			arr[h[n+1]+len[n+1]]=Ans[i];
			Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],++len[a[i]],1);
			arr[h[a[i]]+len[a[i]]]=arr[h[n+1]+pos];
			--len2[a[i]];
		}
		else{
			int pos=binary(bit+h[n+1],n+q,a[i]);
			Ins(bit+h[n+1],n+q,pos,-1);
			Ins(bit+h[n+1],n+q,++len[n+1],1);
			if(b[i]!=m){
				int pos2=binary(bit+h[a[i]],h[a[i]+1]-h[a[i]],b[i]-len2[a[i]]);
				Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],pos2,-1);
				Ans[i]=arr[h[a[i]]+pos2];
				Ins(bit+h[a[i]],h[a[i]+1]-h[a[i]],++len[a[i]],1);
				arr[h[a[i]]+len[a[i]]]=arr[h[n+1]+pos];
			} else Ans[i]=arr[h[n+1]+pos];
			arr[h[n+1]+len[n+1]]=Ans[i];
		}
	}
	F(i,1,q) printf("%lld\n",Ans[i]);
	return 0;
}