WA了一个点,还是270000行出错,求大佬帮忙改题
#include <bits/stdc++.h>
#define G getchar()
#define ll long long
#define mid (l + r) >> 1
#define in cin
#define out cout
using namespace std;
bool happy1041;
ll time1 = clock();
//
struct node{
ll ord,x,y,ans;
};
node que[300005],oque[300005];
ll n,m,q;
ll T[600005],lsl[600005];
vector <ll> neww[300005];
ll lowbit(ll a){
return a&(-a);
}
ll query(ll num){
ll to=0,bz=1; bool lb=0;
while(to+bz<=m+q&&num>T[to+bz]){
to+=bz;
if(lb)
bz<<=1;
else lb=1;
}
num-=T[to];
bz>>=1;
while(bz>=1){
if(to+bz<=m+q&&num>T[to+bz]){
to+=bz;
num-=T[to];
}
bz>>=1;
}
return to+1;
}
void add(ll po,ll num)
{
while(po<=m+q){
T[po]+=num;
po+=lowbit(po);
}
}
bool cmp(node a,node b){
if(a.x<b.x) return true;
if(a.x==b.x&&a.ord<b.ord) return true;
return false;
}
//
bool Happy1041;
void usage() {
ll time2 = clock();
cout << "Memory usage: " << (&Happy1041 - &happy1041) / 1024 / 1024 << " Mb , Time usage: " << time2 - time1 << " ms\n";
}
int main() {
// ifstream in("phalanx.in");
// ofstream out("phalanx.out");
in>>n>>m>>q;
for(int i=1; i<=q; ++i){
que[i].ord=i;
in>>que[i].x>>que[i].y;
oque[i]=que[i];
}
sort(que+1,que+q+1,cmp);
for(int i=1; i<m; ++i) add(i,1);
add(m+q,1);
ll numnew=0;
for(int i=1; i<=q; ++i){
if(que[i].x!=que[i-1].x){
numnew=0;
if(i-1>=1){
if(que[i-1].ans!=m+q)
{
add(que[i-1].ans,1);
add(++numnew+m-1,-1);
}
ll t1=i-2;
while(t1>=1&&que[t1].x==que[t1+1].x){
if(que[t1].ans!=m+q)
{
add(que[t1].ans,1);
add(++numnew+m-1,-1);
}
--t1;
}
}
numnew=0;
}
que[i].ans=query(que[i].y);
oque[que[i].ord].ans=que[i].ans;
if(que[i].ans!=m+q)
{
add(que[i].ans,-1);
add(++numnew+m-1,1);
}
}
memset(T,0,sizeof(T));
for(int i=1; i<=n; ++i){
lsl[i]=i*m;
add(i,1);
}
numnew=0;
// for(int i=1; i<=q; ++i)
// {
// out<<oque[i].ans<<endl;
// }
// out<<endl;
for(int i=1; i<=q; ++i){
ll aba=query(oque[i].x);
bool lb=1;
++numnew;
if(oque[i].ans<=m-1){
lsl[numnew+n]=(oque[i].x-1)*m+oque[i].ans;
}
else if(oque[i].ans<=m+neww[oque[i].x].size()-1){
lsl[numnew+n]=neww[oque[i].x][oque[i].ans-m];
}
else{
lsl[numnew+n]=lsl[aba];
lb=0;
}
// for(int j=1; j<=numnew+n; ++j)
// out<<lsl[j]<<" ";
// out<<"\n";
out<<lsl[numnew+n]<<endl;
if(lb)
neww[oque[i].x].push_back(lsl[aba]);
add(aba,-1);
add(numnew+n,1);
}
return 0;
}