捞：link | 题目

为什么以下两份代码结果不一样？？？？

WA:

#include<bits/stdc++.h>
using namespace std;
int n,q;
int d[100005],c[100005];
int nxt[100005][20],total[100005][20];//nxt[i][j]代表从i开始水溢出pow(2, j)次后的编号 
//total[i][j]代表从i开始水溢出pow(2, j)个圆盘的容量总和 
int dp[100005][20];//RMQ，dp[i][j]表示从i开始，pow(2, j) - 1个数中的最大、最小值 
char *p1,*p2,buf[1000005];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0,f=1;char ch=nc();
    while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}
    while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();
   	return x*f;
}
inline void work(){
    for(int i=1;i<=n;i++)
        dp[i][0]=d[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
inline int RMQ(int l,int r){
    int cnt=0;
    while((1<<(cnt+1))<=r-l+1)
		cnt++;
    return max(dp[l][cnt],dp[r-(1<<cnt)+1][cnt]);
}
int main()
{
	n=read(),q=read();
	for(int i=1;i<=n;i++)
		d[i]=read(),c[i]=read();
	work();
	c[n+1]=1e9;
	for(int i=1;i<n;i++){
		int l=i+1,r=n+1,res=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(RMQ(i+1,mid)<=d[i])
				l=mid+1,res=mid;
			else
				r=mid-1;
		}
		nxt[i][0]=res;
		total[i][0]=c[res];
	}
    nxt[n][0]=n+1;
    total[n][0]=c[n+1];
    for(int j=1;j<=16;j++)
        for(int i=1;i<=n;i++){
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
            total[i][j]=total[i][j-1]+total[nxt[i][j-1]][j-1];
        }
    while(q--){
        int x=read(),y=read();
        if(y>c[x]){
            y-=c[x];
            for(int i=16;i>=0;i--)
                if(y>total[x][i]){
                    y-=total[x][i];
                    x=nxt[x][i];
                }
            x=nxt[x][0];
        }
        if(x==n+1)
			printf("0\n");
        else
			printf("%d\n",x);
    }
    return 0;
}

AC:

#include<bits/stdc++.h>
using namespace std;
int n,q;
int d[100005],c[100005];
int nxt[100005][20],total[100005][20];//nxt[i][j]代表从i开始水溢出pow(2, j)次后的编号 
//total[i][j]代表从i开始水溢出pow(2, j)个圆盘的容量总和 
int dp[100005][20];//RMQ，dp[i][j]表示从i开始，pow(2, j) - 1个数中的最大、最小值 
char *p1,*p2,buf[1000005];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0,f=1;char ch=nc();
    while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}
    while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();
   	return x*f;
}
inline void work(){
    for(int i=1;i<=n;i++)
        dp[i][0]=d[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
inline int RMQ(int l,int r){
    int cnt=0;
    while((1<<(cnt+1))<=r-l+1)
		cnt++;
    return max(dp[l][cnt],dp[r-(1<<cnt)+1][cnt]);
}
int main()
{
	n=read(),q=read();
	for(int i=1;i<=n;i++)
		d[i]=read(),c[i]=read();
	work();
	c[n+1]=1e9;
	for(int i=1;i<n;i++){
		int l=i+1,r=n+1,res=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(RMQ(i+1,mid)<=d[i])
				l=mid+1,res=mid;
			else
				r=mid-1;
		}
		nxt[i][0]=l;
		total[i][0]=c[l];
	}
    nxt[n][0]=n+1;
    total[n][0]=c[n+1];
    for(int j=1;j<=16;j++)
        for(int i=1;i<=n;i++){
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
            total[i][j]=total[i][j-1]+total[nxt[i][j-1]][j-1];
        }
    while(q--){
        int x=read(),y=read();
        if(y>c[x]){
            y-=c[x];
            for(int i=16;i>=0;i--)
                if(y>total[x][i]){
                    y-=total[x][i];
                    x=nxt[x][i];
                }
            x=nxt[x][0];
        }
        if(x==n+1)
			printf("0\n");
        else
			printf("%d\n",x);
    }
    return 0;
}