社区讨论

请问luogu与本地输出不一致的原因？

学学无止境
P1486[NOI2004] 郁闷的出纳员参与者 7已保存回复 13

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
13 条
当前快照
1 份
快照标识符
@mi7dxjiq
此快照首次捕获于
2025/11/20 20:05
4 个月前
此快照最后确认于
2025/11/20 22:29
4 个月前
查看原帖
RT
本题本蒟蒻用的 TreapTreap
暂不谈是否有其他锅
但是 #11 的数据我下载后在本地跑答案是正确的 ((换了两个IDEIDE试了试是对的))
但是在luoguluogu评测与luoguluogu IDEIDE 就有一个数是错的
蒟蒻经过DebugDebug 发现luoguluogu上，我的TreapTreap在m某一次插入一个节点后显示出大小 +2+2，其余均正常.
本蒟蒻用的Windows，但是这个与换行之类的无关应该不会有问题啊蒟蒻不明白为什么，求教各位大佬，实在没办法了
各位大佬可以试一试：
测试点输入数据
CPP
20 0
I 4
F 1
I 6
S 9
F 14
I 6
I 7
A 8
I 3
F 2
I 9
I 6
I 6
S 3
S 5
I 6
F 1
I 3
A 2
F 5
本地正确输出：
CPP
4
-1
14
7
3
5
luoguluogu错误输出:
CPP
4
-1
14
7
5
5
代码:
CPP
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
#define inf 100000000
int n,t,minx,val,temp,ans;
bool flag;
char opt[2];

struct Treap
{
    int tot,root;
    struct node
    {
        int l,r,dat,val,cnt,size;
    }a[100010];
    inline void Update(int p)
    { 
        a[p].size=a[p].cnt+a[a[p].l].size+a[a[p].r].size;
    }
    inline void build()
    {
        New(inf);
        root=1;
        Update(root);
    }
    inline int New(int val)
    {
        a[++tot].val=val;
        a[tot].cnt=a[tot].size=1;
        a[tot].dat=rand();
        return tot;
    }
    inline void zag(int &p)
    {
        int q=a[p].r;
        a[p].r=a[q].l,a[q].l=p,p=q;
        Update(a[p].l),Update(p);
    }
    inline void zig(int &p)
    {
        int q=a[p].l;
        a[p].l=a[q].r,a[q].r=p,p=q;
        Update(a[p].r),Update(p);
    }
    inline void Insert(int &p,int val)
    {
        if(p==0)
        {
            p=New(val);
            return;
        }
        if(val==a[p].val)
        {
            a[p].cnt++;
            Update(p);
            return;
        }
        if(val<a[p].val)
        {
            Insert(a[p].l,val);
            if(a[a[p].l].dat<a[p].dat)
                zig(p);
        }
        if(val>a[p].val)
        {
            Insert(a[p].r,val);
            if(a[a[p].r].dat>a[p].dat)
                zag(p);
        }
        Update(p);
    }
    inline void Remove(int &p,int val)
    {
        if(p==0)
            return;
        if(a[p].val<val)
        {
            Remove(a[p].l,val);
            p=a[p].r;
            if(p)
                Remove(p,val);
        }
        if(a[p].val>=val&&a[p].l)
            Remove(a[p].l,val);
        Update(p);
    }
    inline int GetValByRank(int &p,int val)
    {
        if(a[a[p].r].size>=val)
            return GetValByRank(a[p].r,val);
        if(a[a[p].r].size+a[p].cnt>=val)
            return a[p].val;
        return GetValByRank(a[p].l,val-a[a[p].r].size-a[p].cnt);
    }
}Tree;

int main()
{
    //freopen("1.txt","r",stdin);
    scanf("%d%d",&n,&minx);
    Tree.build();
    for(register int i=1;i<=n;i++)
    {
        scanf("%s%d",opt,&val);
        if(opt[0]=='I'&&val>minx)
            Tree.Insert(Tree.root,val-temp);
        else if(opt[0]=='A')
        {
            if(flag)
            {
                t=Tree.a[Tree.root].size;
                Tree.Remove(Tree.root,minx-temp);
                ans+=(t-Tree.a[Tree.root].size);
            }
            flag=false;
            temp+=val; 
        }
        else if(opt[0]=='S')
            temp-=val,flag=true;
        else
        {
            if(flag)
            {
                t=Tree.a[Tree.root].size;
                Tree.Remove(Tree.root,minx-temp);
                ans+=(t-Tree.a[Tree.root].size);
            }
            if(val>Tree.a[Tree.root].size-1)
                printf("-1\n");
            else
            printf("%d\n",Tree.GetValByRank(Tree.root,val+1)+temp);
        }	
    }
    printf("%d\n",ans); 
    return 0;
}

回复

共 13 条回复，欢迎继续交流。

正在加载回复...