Description

Xiao A and Xiao B decide to travel during the holiday. They number the cities they want to go from 1 to N, and the smaller cities are in the west of the larger cities. It is known that the altitude of each city is different from each other. Remember that the altitude of city I is \ (h_i \), and the distance between city \ (I \) and city \ (J \) \ (d[i,j] \) is exactly the absolute value of the altitude difference between the two cities, that is \ (d[i,j] = |H_i - H_j|\).
During the trip, Xiao A and Xiao B drive in turn. Xiao A drives on the first day, and then rotates once A day. They plan to choose A city S as the starting point, drive all the way East, and drive up to \ (X \) kilometers to end the trip. Small A and small B have different driving styles. Small B always selects the nearest city as the destination along the forward direction, while small A always selects the second nearest city as the destination along the forward direction (Note: in this question, if the distance from the current city to the two cities is the same, it is considered to be closer to the city with low altitude). If any one of them cannot choose the destination city according to their own principles, or the total distance to reach the destination will exceed \ (X \) kilometers, they will end their journey.
Before leaving, little A wants to know two questions:
1. For A given \ (X=X_0 \), which city to start from, the ratio of the total number of trips driven by small A to the total number of trips driven by small B is the smallest (if the travel distance of small B is \ (0 \), the ratio can be regarded as infinity, and the two infinities are regarded as equal). If you start from multiple cities and the ratio of the total number of trips driven by small A to the total number of trips driven by small B is the smallest, the city with the highest altitude will be output.
2. For any given \ (X=X_i \) and departure city \ (S_i \), the total number of driving trips of small A and small B.

HINT

\(1 ≤ N ≤ 10 ^ 5, 1 ≤ M ≤ 10 ^ 4, - 10 ^ 9 ≤ H_i ≤ 10 ^ 9, 0 ≤ X_0 ≤ 10 ^ 9, 1 ≤ S_i ≤ N, 0 ≤ X_i ≤ 10 ^ 9 \), ensure that \ (H_i \) are different from each other

Solution

Preprocess the first and second smallest cities from each city
\(f[i][j] \) indicates the city that starts from \ (I \) and arrives by \ (2^j \)
\(g1[i][j]\) means starting from \ (I \) and taking \ (2^j \) wheel A
\(g2[i][j]\) indicates the distance from \ (I \) to \ (2^j \) round small B
Multiply the solution

#define K 18
#define N 100005
#define INF 1000000005
typedef long long ll;
struct city{
	int h,x;
}h[N];
int f[N][K],g1[N][K],g2[N][K],nxt1[N],nxt2[N],n,m;
set<city> s;
set<city>::iterator xx;
bool operator < (city x,city y){
	if(x.h!=y.h) return x.h<y.h;
	return x.x<y.x;
}
//x is better than y 
inline bool cmp(int u,int x,int y){
	if(!x) return false;
	if(!y) return true;
	if(abs(h[x].h-h[u].h)!=abs(h[y].h-h[u].h))
		return abs(h[x].h-h[u].h)<abs(h[y].h-h[u].h);
	return h[x].h<h[y].h;
}
inline int dis(int x,int y){
	if(x&&y) 
		return abs(h[x].h-h[y].h)<INF?abs(h[x].h-h[y].h):INF;
	return INF;
}
inline void drive(int u,int x,int &d1,int &d2){
	int i;d1=d2=0;
	while(x){
		for(i=K-1;i>=0&&g1[u][i]+g2[u][i]>x;--i);
		if(i<0) return;
		x-=(g1[u][i]+g2[u][i]);
		d1+=g1[u][i];d2+=g2[u][i];
		u=f[u][i];
	}
}
inline bool cmp2(int j,int k,int d1,int d2,int i,int id){
	if(d1<0) return true;
	if(d2&&k) return 1ll*j*d2<1ll*d1*k||(1ll*j*d2==1ll*d1*k&&h[i].h>h[id].h);
	if(d2||k) return k;
	return h[i].h>h[id].h;
}
inline void Aireen(){
	n=read();
	for(int i=1;i<=n;++i)
		h[i].h=-read(),h[i].x=i;
	city c1,c2;
	s.clear();
	for(int i=n-1;i;--i){
		s.insert(h[i+1]);
		c1=(*s.upper_bound(h[i]));
		if(s.count(c1)){
			s.erase(c1);
			c2=(*s.upper_bound(h[i]));
			s.insert(c1);
			nxt1[i]=c1.x;nxt2[i]=c2.x;
		}
		else continue;
	}
	
	s.clear();
	for(int i=1;i<=n;++i)
		h[i].h=-h[i].h;
	for(int i=n-1;i;--i){
		s.insert(h[i+1]);
		c1=(*s.upper_bound(h[i]));
		
		if(s.count(c1)){
			s.erase(c1);
			c2=(*s.upper_bound(h[i]));
			s.insert(c1);
			if(cmp(i,c1.x,nxt1[i])){
				nxt2[i]=nxt1[i];
				nxt1[i]=c1.x;
				if(s.count(c2)&&cmp(i,c2.x,nxt2[i]))
					nxt2[i]=c2.x; 
			}
			else if(cmp(i,c1.x,nxt2[i]))
				nxt2[i]=c1.x; 
		}
		else continue;
	}
	 
	for(int j=0;j<K;++j)
		g1[n][j]=g2[n][j]=g1[0][j]=g2[0][j]=INF; 
	for(int i=n-1;i;--i){
		f[i][0]=nxt2[i];
		f[i][1]=nxt1[nxt2[i]];
		g1[i][0]=g1[i][1]=dis(i,nxt2[i]);
		g2[i][1]=dis(nxt2[i],nxt1[nxt2[i]]);
		for(int j=2;j<K;++j){
			f[i][j]=f[f[i][j-1]][j-1];
			g1[i][j]=g1[i][j-1]+g1[f[i][j-1]][j-1];
			if(g1[i][j]>INF) g1[i][j]=INF;
			g2[i][j]=g2[i][j-1]+g2[f[i][j-1]][j-1];
			if(g2[i][j]>INF) g2[i][j]=INF;
		}
	}
	
	int u,x,d1=-1,d2,id;
	x=read();
	for(int i=1,j,k;i<=n;++i){
		drive(i,x,j,k);
		if(cmp2(j,k,d1,d2,i,id)) d1=j,d2=k,id=i;
	}
	printf("%d\n",id);
	
	m=read();
	while(m--){
		u=read();x=read();
		drive(u,x,d1,d2);
		printf("%d %d\n",d1,d2);
	}
}

2017-10-27 13:30:24