这题: LOJ #3373. 「eJOI2020」喷泉

样例输出 5 0 5 4 2

我的输出 5 0 5 3 2

每个部分都有注释了的方便调试的输出。

make_fa应该没问题。

问题应该出在query。

小概率在 make_st。

谢谢！！！

#include <queue>
#include <iostream>

using namespace std;

struct cilcle
{
    int h,w,id;
};
bool operator<(cilcle a,cilcle b)
{
    return a.h<b.h;
}
bool operator>(cilcle a,cilcle b)
{
    return a.h>b.h;
}
priority_queue <cilcle,vector<cilcle>,greater<cilcle> > q;
int n,m;
int c[100005],d[100005];
int fa[100005];
int stp[100005][22],stw[100005][22];
void make_fa()
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        cin>>c[i]>>d[i];
        stw[i][0]=d[i];
        if(!q.empty())
        {
            while(q.top().h<c[i]&&( !q.empty() ) )
            {
                fa[q.top().id]=i;
                stp[q.top().id][0]=i;
                q.pop();
            }
        }
        cilcle pig;
        pig.h=c[i];
        pig.w=d[i];
        pig.id=i;
        q.push(pig);
    }
    /*
    for(i=1;i<=n;i++)
    {
        cout<<fa[i]<<endl;
    }
    */
}
void make_st()
{
    int i,j,k;

    for(j=1;j<=22;j++)
    {
        for(i=1;i<=n;i++)
        {
            stp[i][j]=stp[stp[i][j-1]][j-1];
            stw[i][j]=stw[i][j-1]+stw[stp[i][j-1]][j-1];
        }
    }
    /*
    for(j=0;j<=22;j++)
    {
        for(i=1;i<=n;i++)
        {
            stp[i][0]=fa[i];
            cout<<stp[i][j]<<' '<<stw[i][j]<<"     ";
        }
        cout<<endl;
    }
    */
}
int query(int x,int y)
{
    for(int i=22;i>=0;i--)
    {
        //if(x==3)cout<<x<<' '<<y<<' '<<stw[x][i]<<endl;
        if(stp[x][i]!=0&&stw[x][i]<y)
        {
            return query(stp[x][i],y-stw[x][i]);
        }
    }
    if(fa[x]==0&&y>d[x])return 0;
    //cout<<x<<' '<<y<<endl;
    return x;
}
int main()
{
    int i,j,k;
    cin>>n>>m;
    make_fa();
    make_st();
    for(i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        cout<<query(x,y)<<endl;
    }
    return 0;
}