题解 P3960 【列队】

· · 题解

我是洛谷全站跑得最快的，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;
}