题解：P3960 [NOIP 2017 提高组] 列队
huangzixi071018
·
·
题解
题目大意：
# 思路：
维护这个方阵的行和列。先预处理出第 $i$ 个询问要查询的数在这一行的位置（有可能不在这一行，则大于 $m$，所以需要最后一列的补上），用数状数组预处理，原来的数没离开则为 $1$，否则为 $0$,找前缀和为 $y$ 的数。然后处理行，如果这一行查询的值是原本的值，那么直接输出，否则是前面处理过的数，用一个 vector 来处理每一行的前 $m-1$ 个数和第 $n$ 列的数，最后还要把第 $n$ 列的数向左移，来维护整个方阵。
# 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
id[i]表示第i个询问对应的在第a[i].x行的原来的列数（如果存在的话）
s[i]表示现在在第i行的前m-1个数而原来不在的数
s[0]表示现在在第n列的数
*/
const int N=3e5+5;
vector<pair<int,int>>e[N];
vector<ll>s[N];
struct node{
int x,y;
}a[N];
int tree[2*N],mx,id[N];
int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
for(int i=x;i<=mx;i+=lowbit(i)){
tree[i]+=y;
}
}
int query(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)){
res+=tree[i];
}
return res;
}
int js(int x){
int l=0,r=mx,res=mx+1;
while(l<=r){
int mid=(l+r)/2;
if(query(mid)>=x){
res=mid;
r=mid-1;
}else{
l=mid+1;
}
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
mx=max(n,m)+q;
for(int i=1;i<=q;i++){
cin>>a[i].x>>a[i].y;
if(a[i].y!=m){
e[a[i].x].push_back(make_pair(a[i].y,i));
}
}
for(int i=1;i<=mx;i++){
add(i,1);
}
for(int i=1;i<=n;i++){
for(int j=0;j<e[i].size();j++){
int y=e[i][j].first,x=e[i][j].second;
id[x]=js(y);
add(id[x],-1);
}
for(int j=0;j<e[i].size();j++){
int x=e[i][j].second;
add(id[x],1);
}
}
for(int i=1;i<=q;i++){
int h=js(a[i].x);
ll la,ans;//la第a[i].x行最后一位
add(h,-1);
if(h<=n){
la=1ll*m*h;
}else{
la=s[0][h-n-1];
}
if(a[i].y==m){
ans=la;
}else{
s[a[i].x].push_back(la);//把最后一位向左移一位
if(id[i]<m){
ans=1ll*(a[i].x-1)*m+id[i];
}else{
ans=s[a[i].x][id[i]-m];
}
}
s[0].push_back(ans);
cout<<ans<<"\n";
}
return 0;
}
```