答案与解析
正确答案:<p style="text-align: left;">#pragma GCC optimize(3)</p><p style="text-align: left;">#include <bits/stdc++.h></p><p style="text-align: left;">#define ll long long</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int Max=300005;</p><p style="text-align: left;">int n,m,q,sum,tot;</p><p style="text-align: left;">int tree[Max*20],lc[Max*20],rc[Max*20],rt[Max];</p><p style="text-align: left;">vector<ll>num[Max];</p><p style="text-align: left;">inline int get_int()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=0;char c;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(c=getchar();!isdigit(c);c=getchar());</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void print(ll x)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x>9) print(x/10);</p><p style="text-align: left;"><span style="white-space:pre"> </span>putchar('0'+x%10);</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void add(int &now,int l,int r,int pos)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!now) now=++tot;tree[now]++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(l==r) return;</p><p style="text-align: left;"><span style="white-space:pre"> </span>int mid=(l+r)>>1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(pos<=mid) add(lc[now],l,mid,pos);</p><p style="text-align: left;"><span style="white-space:pre"> </span>else add(rc[now],mid+1,r,pos);</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int Q(int root,int l,int r,int k)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(l==r) return l;</p><p style="text-align: left;"><span style="white-space:pre"> </span>int mid=(l+r)>>1,sum=(mid-l+1)-tree[lc[root]];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(sum>=k) Q(lc[root],l,mid,k);</p><p style="text-align: left;"><span style="white-space:pre"> </span>else Q(rc[root],mid+1,r,k-sum);</p><p style="text-align: left;">}</p><p style="text-align: left;">inline ll Qr(int x,ll v)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int pos=Q(rt[n+1],1,sum,x);add(rt[n+1],1,sum,pos);</p><p style="text-align: left;"><span style="white-space:pre"> </span>ll ans=pos<=n?(ll)m*pos:num[n+1][pos-n-1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>return num[n+1].push_back(v?v:ans),ans;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline ll Ql(int x,int y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int pos=Q(rt[x],1,sum,y);add(rt[x],1,sum,pos);</p><p style="text-align: left;"><span style="white-space:pre"> </span>ll ans=pos<m?(ll)(x-1)*m+pos:num[x][pos-m];</p><p style="text-align: left;"><span style="white-space:pre"> </span>return num[x].push_back(Qr(x,ans)),ans;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"> <span style="white-space:pre"> </span>n=get_int(),m=get_int(),q=get_int(),sum=max(n,m)+q;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(q--)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int x=get_int(),y=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(y==m) print(Qr(x,0)),putchar('\n');</p><p style="text-align: left;"><span style="white-space:pre"> </span> else print(Ql(x,y)),putchar('\n');</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。