100AC代码

#include<iostream>
#include<stack>
#define nmax 200000
#define qmax 300000
#define lognmax 20
#define inf 0x7fffffff
using namespace std;
int d[nmax],c[nmax],r[qmax],v[qmax],t[nmax][lognmax],cost[nmax][lognmax];
int main(){
	#ifdef local
		system("");
		int logn=3;
	#endif
	//---输入O(n)---//
	#ifdef local
		cout<<"\033[32mn,q:\n\033[0m";
	#endif
	int n,q;
	cin>>n>>q; 
	#ifdef local
		cout<<"\033[32md,c:\n\033[0m";
	#endif
	for(int i=1;i<=n;i++)
		cin>>d[i]>>c[i];
	#ifdef local
		cout<<"\033[32mr,v:\n\033[0m";
	#endif
	for(int i=1;i<=q;i++)
		cin>>r[i]>>v[i];
	//---计算To数组O(logn)---//
	stack<int>mono;
	for(int i=1;i<=n;i++){
		while(!mono.empty()&&d[mono.top()]<d[i]){
			t[mono.top()][0]=i;
			mono.pop();
		}
		mono.push(i);
	}
	for(int k=1;k<20;k++)
		for(int i=1;i<=n;i++)
			t[i][k]=t[t[i][k-1]][k-1]; 
	#ifdef local
		cout<<"\033[32mTo数组:\n\033[0m";
		for(int k=0;k<=logn;k++){
			for(int i=1;i<=n;i++)
				cout<<t[i][k]<<" ";
			cout<<"\n";
		}
		cout<<"\n";
	#endif
	//---计算Cost数组(logn)---//
	for(int i=1;i<=n;i++)
		cost[i][0]=c[i];
	for(int k=0;k<20;k++)
		cost[0][k]=inf;
	for(int k=1;k<20;k++)
		for(int i=1;i<=n;i++){
			cost[i][k]=cost[i][k-1]+cost[t[i][k-1]][k-1];
			if(cost[i][k]<0)
				cost[i][k]=inf;
		}
	#ifdef local
		cout<<"\033[32mCost数组:\n\033[0m";
		for(int k=0;k<=logn;k++){
			for(int i=1;i<=n;i++)
				cout<<cost[i][k]<<" ";
			cout<<"\n";
		}
		cout<<"\n";
	#endif
	//---解决并回答O(logn)---//
	#ifdef local
		cout<<"\033[32mans:\n\033[0m";
	#endif
	for(int i=1;i<=q;i++){
		for(int k=19;k>=0;k--)
			if(v[i]>cost[r[i]][k]){
				v[i]-=cost[r[i]][k];
				r[i]=t[r[i]][k];
			}
		cout<<r[i]<<"\n";
	}
	//---完结撒花---//
	return 0;
}

数据统计

截止至2025.5.22.13:53，有28次提交，其中25次是hyr提交的，还有3次，是zfj帮hyr调试代码时提交的。

本题思路

两个st表，一个是to，另一个是cost，然后二分/递归查找，时间复杂度$O(nlog_2n)$。