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

Posted on Edited on

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

题意十分明白（这次NOI Online题意给得实在是太舒服了），不再赘述。

其实一开始我以为要利用 ai≠aja_i\neq a_j 来做文章，后面发现好像并不需要。

题目明显是想让我们 O(n)O(n) 或者 O(nlog⁡n)O(n\log n) 来解决的，所以我猜想区间内的答案应该和全局的答案有某种关系。于是我们可以先按题意模拟一下 [1,n][1,n] 区间的情况。我们可以将每个数入栈时的前一个数记录下来，记为 preipre_i 。特殊地，当 ii 是成功的，我们不妨记 prei=0pre_i = 0 。

然后我们发现了一个重要的性质：

[l,r][l,r] 中满足 prei<lpre_i < l 的 ii 的个数就是我们要求的答案。

不难想到用 FjF_j 表示 prei=jpre_i = j 的 ii 的个数，那么对 FF 数组求个前缀和就能得出全局中满足 prei<jpre_i < j 的个数。

那么，我们可以发现， [1,l−1][1,l-1] 的所有数都是满足 prei<lpre_i < l 的，可以轻松计算，而 [l,n][l,n] 的 preipre_i 却让人无从下手。我尝试将 [r+1,n][r+1,n] 分离出来，但是失败了。

这时，我就想，既然前面很好处理，后面很难，那为什么不将询问按 rr 从小到大排个序，然后将二元组逐个加入呢？（这是个树状数组的经典操作）

接下来就很好想了。我们只需要用两行代码弄出一个树状数组来帮忙维护一下之前提到的 FF 函数的动态前缀和就好了。

注意，树状数组下标不能为 00 ，所以我们不能把 preipre_i 等于 00 的数记录进去。可以另外开一个 SS 数组来记录成功的数的个数的前缀和。

对于一个询问 [l,r][l,r] ，答案是：

Sr−Sl−1+Query(l−1)−(l−1)+Sl−1S_r - S_{l-1} +Query(l-1) - (l-1) + S_{l-1}

其中 SiS_i 表示 [1,i][1,i] 在全局状态下成功的个数， Query(i)Query(i) 表示 FF 数组前 ii 项的前缀和（也就是 [1,r][1,r] 中满足 prei<lpre_i < l 的 ii 的个数）。

为什么要减去 (l−1)(l-1) 呢？因为 [1,l−1][1,l-1] 中的 l−1l-1 个数都是满足要求的，而我们不需要它们。

为什么要加上 Sl−1S_{l-1} 呢？因为我们在减去 (l−1)(l-1) 的时候多减了成功的数，而成功的数不再 QueryQuery 的计算范围内，所以要补回来。

也就是：

Query(l−1)−(l−1)+SrQuery(l-1) - (l-1) + S_r

最后别忘了把询问排回原来的顺序。

考场代码（民间数据过了，官方不知）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#define gc getchar
#define pc putchar
#define lowbit(x) (x&-(x))
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define abs(x) (x>0?x:-(x))
typedef long long LL;
using namespace std;
namespace Leon{
	inline int read(){
		int xx=0;bool pp=1;char ch=gc();
		while (ch>57||ch<48) ch=='-'?pp=0:0,ch=gc();
		while (ch<58&&ch>47) xx=(xx<<1)+(xx<<3)+(ch^48),ch=gc();
		return pp?xx:-xx;
	}
	inline LL readLL(){
		LL xx=0;bool pp=1;char ch=gc();
		while (ch>57||ch<48) ch=='-'?pp=0:0,ch=gc();
		while (ch<58&&ch>47) xx=(xx<<1ll)+(xx<<3ll)+(LL)(ch^48),ch=gc();
		return pp?xx:-xx;
	}
	inline string getstr(){
		string ss;char ch=gc();
		while (ch>'z'||ch<'a') ch=gc();
		while (ch<='z'&&ch>='a') ss+=ch,ch=gc();
		return ss;
	}
	inline void putstr(const string ss){
		for (int i=0;i<ss.length();++i){
			pc(ss[i]);
		}
	}
	void putint(int xx){
		if (xx) putint(xx/10),pc(xx%10+48);
	}
	inline void print(int xx){
		if (xx<0) xx=-xx,pc('-');
		if (xx) putint(xx);
		else pc('0');
	}
	void putLL(LL xx){
		if (xx) putLL(xx/10ll),pc(xx%10+48);
	}
	inline void printLL(LL xx){
		if (xx<0) xx=-xx,pc('-');
		if (xx) putLL(xx);
		else pc('0');
	}
}
using namespace Leon;
const int N=5e5+1;
int n,q,A[N],B[N],st[N],top,S[N];
struct node{
	int l,r,tag,ans;
} G[N];
inline bool cmpr(node a,node b){
	return a.r<b.r;
}
inline bool cmptag(node a,node b){
	return a.tag<b.tag;
}
int T[N];
inline void Add(int x,int y){
	for (;x<=n;x+=lowbit(x)) T[x]+=y;
}
inline int Query(int x){
	int res=0;for (;x;x-=lowbit(x)) res+=T[x];return res;
}
//以上是快读快输以及一些易实现的东西。 
signed main(){
	freopen("stack.in","r",stdin);
	freopen("stack.out","w",stdout);
	//freopen("t.in","r",stdin);
	//freopen("t.out","w",stdout);
	n=read(),q=read();
	for (int i=1;i<=n;++i) A[i]=read();
	for (int i=1;i<=n;++i) B[i]=read();
	for (int i=1;i<=q;++i)
		G[i].l=read(),G[i].r=read(),G[i].tag=i;
	//输入 
	sort(G+1,G+1+q,cmpr);
	//按r排序 
	int now=1;
	for (int i=1;i<=q;++i){
		while (now<=n&&now<=G[i].r){
			//将该入栈的数入栈，该出栈的出栈。 
			while (top&&
			(A[st[top]]==A[now]||B[st[top]]<=B[now]))
				--top;
			//按题目模拟单调栈 
			if (st[top]) Add(st[top],1);
			//如果不成功就加入树状数组 
			S[now]=S[now-1]+(st[top]==0);
			//如果成功了就加入S数组 
			st[++top]=now;
			//入栈 
			++now;
		}
		int le=G[i].l,ri=G[i].r;
		G[i].ans=Query(le-1)-(le-1)+S[ri];
		//计算 
	}
	sort(G+1,G+1+q,cmptag);
	//排回来 
	for (int i=1;i<=q;++i) print(G[i].ans),pc('\n');
	return 0;
}

作者很菜，欢迎指出问题！