在调试这个题的时候,发现了一个很奇怪的错误使我丢了一个小时: 此下为代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int ls,rs,num;
}seg[20000005];
int rot[2000005],n,a[2000005],lsh[2000005],h,m,x,y,z,cnt;
inline int rd(){int x=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*w;}
int build(int l,int r)
{
cnt++;
int rt=cnt;
seg[rt].num=0;
if(l<r)
{
int mid=(l+r)/2;
seg[rt].ls=build(l,mid);
seg[rt].rs=build(mid+1,r);
}
return rt;
}
int dl(int las,int ca,int l,int r)
{
cnt++;
int rt=cnt;
seg[rt]=seg[las];
seg[rt].num=seg[las].num+1;
if(l<r)
{
int mid=(l+r)/2;
if(ca<=mid) seg[rt].ls=dl(seg[las].ls,ca,l,mid);
else seg[rt].rs=dl(seg[las].rs,ca,mid+1,r);
}
return rt;
}
int que(int st,int ed,int l,int r,int las)
{
if(l==r)
{
return l;
}
int cf=seg[seg[ed].ls].num-seg[seg[st].ls].num,mid=(l+r)/2;
if(cf>=las) return que(seg[st].ls,seg[ed].ls,l,mid,las);
else return que(seg[st].rs,seg[ed].rs,mid+1,r,las-cf);
}
signed main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++)
{
lsh[i]=rd();
a[i]=lsh[i];
}
sort(lsh+1,lsh+1+n);
h=unique(lsh+1,lsh+1+n)-lsh-1;
rot[0]=build(1,h);
for(int i=1;i<=n;i++)
{
rot[i]=dl(rot[i-1],lower_bound(lsh+1,lsh+1+h,a[i])-lsh,1,h);
}
for(int i=1;i<=m;i++)
{
cout<<lsh[que(rot[rd()-1],rot[rd()],1,h,rd())]<<'\n';
}
return 0;
}
这个是错误代码,但是若将倒数第四行修改为如下:
x=rd(),y=rd(),z=rd();
cout<<lsh[que(rot[x-1],rot[y],1,h,z)]<<'\n';
就变为了正确代码,已知输入顺序就是按x,y,z来输入的,那么为什么在程序中体现出来的输入顺序就是错误的,还是说他有一种特性使输入顺序变换了