题解 P3960 【列队】
小粉兔
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)$。
具体看代码吧！
代码：
```cpp
#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;
}
```