\u6211\u6ca1\u6709\u8138\u628a\u8fd9\u7bc7\u6587\u7ae0\u79f0\u4f5c\u662f\u300c\u6211\u300d\u7684\u9898\u89e3\u3002
\n\u96be\u5ea6\u975e\u5e38\u7684\u5927\u3002
\n\u8bf4\u5b9e\u8bdd\u6839\u672c\u4e0d\u77e5\u9053\u600e\u4e48\u5199\uff0c\u4e5f\u65e0\u6cd5\u7406\u89e3\u3002
\n\u518d\u4e00\u6b21\u611f\u53d7\u5230\u4eba\u548c\u5de8\u795e\u7684\u533a\u522b\u3002<\/p>\n
\u300c\u4eba\u8ddf\u4eba\u4e4b\u95f4\u662f\u6709\u5dee\u8ddd\u7684\u3002\u300d<\/p><\/blockquote>\n
\u5b9e\u5728\u662f\u65e0\u6cd5\u7406\u89e3\uff0c\u6240\u4ee5\u53ea\u80fd\u6284\u5c0f\u7c89\u5154\u7684\u9898\u89e3\u4e86\u3002
\n\u53ef\u80fd\u7b49\u5230\u6211\u7684\u80fd\u529b\u6709\u63d0\u5347\u4e86\u4e4b\u540e\u624d\u80fd\u7406\u89e3\u8fd9\u9053\u9898\u7684\u6b63\u89e3\u5427\u3002
\n\u8bdd\u8bf4\u6709\u4e2asm\u6253\u6210\u4e86rt\u5361\u4e86\u6211\u534a\u5929\u3002<\/p>\n#include<iostream>\r\n#include<cstdio>\r\n#include<algorithm>\r\n#include<cstring>\r\nusing namespace std;\r\n#define lwbt(_A) ((_A)&(-(_A)))\r\n\r\n\r\nint q,loc[300005];\r\nlong long n,m,X[300005],Y[300005],ans[300005],arr[900005];\r\nint len[300005],len2[300005],h[300005],tr[900005];\r\ninline void add(int *_H,int _L,int _X,int _A){\r\n while(_X<=_L){\r\n _H[_X]+=_A;\r\n _X+=lwbt(_X);\r\n }\r\n}\r\ninline bool cmp(const int &_A,const int &_B){\r\n return (X[_A]==X[_B])?(_A<_B):(X[_A]<X[_B]);\r\n}\r\ninline int srch(int *_H,int _L,int _X){\r\n int l=1,r,mid,sm,rt;\r\n while((l<=_L)&&(_H[l]<_X)){\r\n l<<=1,rt=l;\r\n }\r\n r=l;\r\n sm=_H[l>>=1];\r\n while(l+1<r){\r\n mid=(l+r)>>1;\r\n if(mid>_L||_H[mid]+sm>=_X){\r\n r=mid,rt=mid;\r\n }else{\r\n l=mid,sm+=_H[l];\r\n }\r\n }\r\n rt=r;\r\n return rt;\r\n}\r\nint st[300005],tp=0;\r\nvoid init(){\r\n scanf(\"%lld%lld%lld\",&n,&m,&q);\r\n for(int i=1;i<=q;++i){\r\n scanf(\"%lld%lld\",&X[i],&Y[i]);\r\n loc[i]=i;\r\n }\r\n sort(loc+1,loc+1+q,cmp);\r\n for(int i=1;i<m;++i){\r\n add(tr,m-1,i,1);\r\n }\r\n for(int i=1;i<=n;++i){\r\n len[i]=m-1;\r\n }\r\n for(int i=1;i<=q;++i){\r\n if(X[loc[i-1]]!=X[loc[i]]){\r\n while(tp){\r\n add(tr,m-1,st[tp--],1);\r\n }\r\n }\r\n if(Y[loc[i]]>len[X[loc[i]]]){\r\n continue;\r\n }\r\n int pos=srch(tr,m-1,Y[loc[i]]);\r\n ans[loc[i]]=(X[loc[i]]-1)*m+pos;\r\n add(tr,m-1,pos,-1);\r\n st[++tp]=pos;\r\n --len[X[loc[i]]];\r\n }\r\n int it=0;\r\n for(int i=1;i<=n;++i){\r\n while(it<=q&&X[loc[it]]<i){\r\n ++it;\r\n }\r\n h[i]=it-1;\r\n }\r\n h[n+1]=q;\r\n memset(tr,0,sizeof(tr));\r\n for(int i=1;i<=n;++i){\r\n len[i]=0,len2[i]=m-1;\r\n }\r\n len[n+1]=n;\r\n for(int i=1;i<=n;++i){\r\n add(tr+h[n+1],n+q,i,1);\r\n arr[q+i]=i*m;\r\n }\r\n for(int i=1;i<=q;++i){\r\n if(ans[i]){\r\n int pos=srch(tr+h[n+1],n+q,X[i]);\r\n add(tr+h[n+1],n+q,pos,-1);\r\n add(tr+h[n+1],n+q,++len[n+1],1);\r\n arr[h[n+1]+len[n+1]]=ans[i];\r\n add(tr+h[X[i]],h[X[i]+1]-h[X[i]],++len[X[i]],1);\r\n arr[h[X[i]]+len[X[i]]]=arr[h[n+1]+pos];\r\n --len2[X[i]];\r\n }else{\r\n int pos=srch(tr+h[n+1],n+q,X[i]);\r\n add(tr+h[n+1],n+q,pos,-1);\r\n add(tr+h[n+1],n+q,++len[n+1],1);\r\n if(Y[i]!=m){\r\n int pos2=srch(tr+h[X[i]],h[X[i]+1]-h[X[i]],Y[i]-len2[X[i]]);\r\n add(tr+h[X[i]],h[X[i]+1]-h[X[i]],pos2,-1);\r\n ans[i]=arr[h[X[i]]+pos2];\r\n add(tr+h[X[i]],h[X[i]+1]-h[X[i]],++len[X[i]],1);\r\n arr[h[X[i]]+len[X[i]]]=arr[h[n+1]+pos];\r\n }else{\r\n ans[i]=arr[h[n+1]+pos];\r\n }\r\n arr[h[n+1]+len[n+1]]=ans[i];\r\n }\r\n }\r\n for(int i=1;i<=q;++i){\r\n printf(\"%lld\\n\",ans[i]);\r\n }\r\n} \r\nint main(){\r\n init();\r\n return 0;\r\n}<\/code><\/pre>\n<\/p>\n","protected":false},"excerpt":{"rendered":"
\u6211\u6ca1\u6709\u8138\u628a\u8fd9\u7bc7\u6587\u7ae0\u79f0\u4f5c\u662f\u300c\u6211\u300d\u7684\u9898\u89e3\u3002 \u96be\u5ea6\u975e\u5e38\u7684\u5927\u3002 \u8bf4\u5b9e\u8bdd\u6839\u672c\u4e0d\u77e5\u9053\u600e\u4e48\u5199\uff0c\u4e5f\u65e0\u6cd5\u7406\u89e3\u3002 \u518d\u4e00\u6b21\u611f\u53d7\u5230\u4eba\u548c … <\/p>\n