关于快读,问个问题QwQ
查看原帖
关于快读,问个问题QwQ
722016
WFHFAQFXY楼主2025/2/5 21:25

在调试这个题的时候,发现了一个很奇怪的错误使我丢了一个小时: 此下为代码:

#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来输入的,那么为什么在程序中体现出来的输入顺序就是错误的,还是说他有一种特性使输入顺序变换了

2025/2/5 21:25
加载中...