这题我改了三天，考场上部分分暴力拿了50，考完试发现与正解很接近只是没写出来。
对于每一行和最后一列建n+1颗线段树，维护前缀和。
复杂度qlogn
假如你移动一个坐标为(x,y)的人，你要将第x行线段树中前缀和为y处的值变为0，再将其移至最后一列的末尾，然后将最后一列中前缀和为x处的值变为一，并将这个位置上的数添加到第x行线段树的末尾。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,q; 4 typedef long long ll; 5 struct node 6 { 7 int l,r,s;bool lz;ll x,y; 8 }t[15000005]; 9 10 int idx,mx[300005],ed[300005],id[300005]; 11 void pd(int z) 12 { 13 if(!t[z].lz) 14 { 15 t[z].l=++idx; 16 t[z].r=++idx; 17 ll m=(t[z].x+t[z].y)>>1; 18 t[t[z].l].x=t[z].x;t[t[z].l].y=m; 19 t[t[z].r].x=m+1;t[t[z].r].y=t[z].y; 20 t[t[z].l].s=t[t[z].l].y-t[t[z].l].x+1; 21 t[t[z].r].s=t[t[z].r].y-t[t[z].r].x+1; 22 t[z].s=t[t[z].l].s+t[t[z].r].s; 23 t[z].lz=1; 24 } 25 } 26 void change(int z,int l,int r,int L,int R,ll l1,ll r1) 27 { 28 if(l==L&&r==R) 29 { 30 t[z].x=l1;t[z].y=r1;t[z].s=r1-l1+1;return; 31 } 32 33 pd(z); 34 int m=(l+r)>>1; 35 if(R<=m)change(t[z].l,l,m,L,R,l1,r1); 36 else if(L>m)change(t[z].r,m+1,r,L,R,l1,r1); 37 else 38 { 39 change(t[z].l,l,m,L,m,l1,l1+m-L); 40 change(t[z].r,m+1,r,m+1,R,l1+m-L+1,r1); 41 } 42 t[z].s=t[t[z].l].s+t[t[z].r].s; 43 } 44 ll pos1,pos2; 45 void query(int z,int l,int r,int s) 46 { 47 if(l==r) 48 { 49 pos1=l;pos2=t[z].x;return; 50 } 51 if(t[z].l==0) t[z].l=++idx; 52 if(t[z].r==0) t[z].r=++idx; 53 pd(z); 54 int m=(l+r)>>1; 55 if(t[t[z].l].s>=s) 56 query(t[z].l,l,m,s); 57 else 58 query(t[z].r,m+1,r,s-t[t[z].l].s); 59 } 60 int xx[300005],yy[300005]; 61 int main() 62 { 63 scanf("%d%d%d",&n,&m,&q); 64 for(int i=1;i<=q;++i) 65 { 66 scanf("%d%d",&xx[i],&yy[i]); 67 mx[xx[i]]++; 68 } 69 for(int i=1;i<=n;++i) 70 { 71 mx[i]+=m-1;id[i]=++idx; 72 change(id[i],1,mx[i],1,m-1,1ll*(i-1)*m+1,1ll*i*m-1); 73 ed[i]=m-1; 74 } 75 id[n+1]=++idx;mx[n+1]=n+q;ed[n+1]=n; 76 for(int i=1;i<=n;++i) 77 change(id[n+1],1,mx[n+1],i,i,1ll*i*m,1ll*i*m); 78 int x,y; 79 for(int i=1;i<=q;++i) 80 { 81 x=xx[i];y=yy[i]; 82 if(y==m) 83 { 84 query(id[n+1],1,mx[n+1],x); 85 change(id[n+1],1,mx[n+1],pos1,pos1,0,-1); 86 ed[n+1]++; 87 change(id[n+1],1,mx[n+1],ed[n+1],ed[n+1],pos2,pos2); 88 printf("%lld\n",pos2); 89 } 90 else 91 { 92 //cout<<666<<endl; 93 query(id[x],1,mx[x],y); 94 ll a1=pos1,a2=pos2;ed[n+1]++;ed[x]++; 95 query(id[n+1],1,mx[n+1],x); 96 97 change(id[x],1,mx[x],a1,a1,0,-1); 98 change(id[x],1,mx[x],ed[x],ed[x],pos2,pos2); 99 100 change(id[n+1],1,mx[n+1],pos1,pos1,0,-1); 101 change(id[n+1],1,mx[n+1],ed[n+1],ed[n+1],a2,a2); 102 103 printf("%lld\n",a2); 104 } 105 } 106 return 0; 107 } 108