P8251 [NOI Online 2022 提高组] 丹钓战

题面

有 \(n\) 个二元组 \((a_i, b_i)\)，编号为 \(1\) 到 \(n\)。

有一个初始为空的栈 \(S\)，向其中加入元素 \((a_i, b_i)\) 时，先不断弹出栈顶元素直至栈空或栈顶元素 \((a_j , b_j)\) 满足 \(a_i \neq a_j\) 且 \(b_i < b_j\)，然后再将其加入栈中。

如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。

有 \(q\) 个询问 \([l_i, r_i]\)，表示若将编号在 \([l_i, r_i]\) 中的二元组按编号从小到大依次入栈，会有多少个二元组是“成功的”。

询问之间相互独立。

思路

既然是丹（单）钓（调）战（栈），所以肯定是可以单调栈的。

首先用单调栈预处理，用链表的思想来维护出栈的元素。如果没有后继，那么就设为 \(n+1\)。

然后对于每一个询问，只要维护 \(l\) 到 \(r\) 的链表元素计数就好了。

非正解但是民间数据+卡常可过。

代码

#include 
#define LIWENX_AK_IOI for(int i=1;i<=n;i++)
#define OLLO_AK_IOI while(m--)
using namespace std;

namespace IO {
	const int SIZE=1<<21;
	static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
	int qr;
	char qu[55],c;
	bool f;
#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
#define puts(x) IO::Puts(x)
	template
	inline void read(T&x) {
		for(f=1,c=getchar(); c<48||c>57; c=getchar())f^=c=='-';
		for(x=0; c<=57&&c>=48; c=getchar()) x=(x<<1)+(x<<3)+(c&15);
		x=f?x:-x;
	}
	template
	inline void write(T x) {
		if(!x) putchar(48);
		if(x<0) putchar('-'),x=-x;
		while(x) qu[++qr]=x%10^48,x/=10;
		while(qr) putchar(qu[qr--]);
	}
	inline void Puts(const char*s) {
		for(int i=0; s[i]; i++)
			putchar(s[i]);
		putchar('\n');
	}
	struct Flusher_ {
		~Flusher_() {
			flush();
		}
	} io_flusher_;
}
using IO::read;
using IO::write;


const int SIZE = 5E5+1;
int n,m;
int a[SIZE],b[SIZE];

int top=0;
int sta[SIZE],linkable[SIZE];

inline void yuchuli(int i) {
	while(top!=0&&((a[sta[top]]==a[i]||b[sta[top]]<=b[i]))) {
		linkable[sta[top]]=i;
		top--; // Pop
	}
	sta[++top]=i; // Push
}

inline void yuchuli2(int i) {
	if(!linkable[i]) {
		linkable[i]=n+1;
	}
}

int main() {
	read(n);
	read(m);
	LIWENX_AK_IOI {
		read(a[i]);
	}
	LIWENX_AK_IOI {
		read(b[i]);
	}
	LIWENX_AK_IOI {
		yuchuli(i);
	}
	LIWENX_AK_IOI {
		yuchuli2(i);
	}
	OLLO_AK_IOI {
		int l,r,i,ans=0;
		read(l);
		read(r);
		i=l;
		while(i<=r) {
			ans++;
			i=linkable[i];
		}
		write(ans);
		putchar('\n');
	}
	return 0;
}