P8010「Wdsr-3」令人感伤的红雨

发表于 分类于 本文字数： 3.4k 阅读时长 ≈ 4 分钟

P8010 「Wdsr-3」令人感伤的红雨

提供一个 的卡常做法。

思路

我们先来看这令人头大的三堆函数。

首先我们可以发现 指的是 中最靠右的最大值出现的位置。
令 ，那么序列 一定单调不降。

所以有：

那么我们可以对 中关于 的两个式子做进一步转化：

于是我们得到了 关于 的转化：

那么我们能得到 关于 的转化：

我们发现，在 中，由于 单调不增且不大于零，所以我们可以得到：

其实就是要维护 中 到 的距离。如果此时 ，则不存在答案，应输出 0。

维护区间最大值的位置，我们考虑用线段树。在左右区间合并时做分类讨论即可。

卡常

由于线段树的 过大，以正常的常数根本无法通过 的数据。
但是理论来讲 2.5 秒是可以通过 的，所以我们需要运用一些卡常技巧。

具体内容见代码。

代码

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T&x){//快读
	int w=0;x=0;
	char ch = getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w=1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t);read(args...);
}
template <typename T>
inline T Max(T x,T y){//实测手写会比自带的max、if和三目运算快
  return (x > y ? x : y);
}
const int N = 6e6+10;
int n,m;
int P=1,DEP=0;
struct Tree{//用结构体内存访问比较连续
	ll mx; int pos;
	Tree(){
		mx = 0; pos = 0;
	}
	Tree(ll tmx,int tpos){
		mx = tmx; pos = tpos;
	}
	inline Tree operator + (const Tree&G) const{//实测重载运算符比外层调用函数快
		if(mx==G.mx) return Tree(mx,Max(pos,G.pos));
		else if(mx>G.mx) return Tree(mx,pos);
		else return G;
	}
}tr[N*3];
ll tag[N*3];
int main(){
// 	freopen("in.in","r",stdin);
// 	freopen("out.out","w",stdout);
	
	read(n,m);
	while(P<=n+1) P<<=1;
	for(int i=1,x;i<=n;++i){
		read(x); tr[i+P] = Tree(1ll*x,i);//直接读入省掉建树的常数
	}
	for(int i=P-1;i;--i) tr[i] = tr[i<<1]+tr[i<<1|1];//用重载运算符
	for(int i=1,opt,x,y;i<=m;++i){
		read(opt,x,y);
		if(opt==1){//把update内容搬到主函数里
			int l = 1+P-1,r = x+P+1; ll k = 1ll*y;
			while(l^1^r){
				if(~l&1) tr[l^1].mx+=k,tag[l^1]+=k;
				if(r&1) tr[r^1].mx+=k,tag[r^1]+=k;
				l>>=1;r>>=1;//直接更新，实测比写push_up函数快
				tr[l] = tr[l<<1]+tr[l<<1|1];
				tr[l].mx += tag[l];//标记永久化要加累加标记值
				tr[r] = tr[r<<1]+tr[r<<1|1];
				tr[r].mx += tag[r];
			}
			for(l>>=1; l ;l>>=1){//更新上传
				tr[l] = tr[l<<1]+tr[l<<1|1];
				tr[l].mx += tag[l];
			}
		}
		else{//把query内容搬到主函数里
			int l = 1+P-1,r = y+P+1; Tree resl,resr;
			while(l^1^r){
				if(~l&1) resl = resl+tr[l^1];//注意左右区间合并顺序
				if(r&1) resr = tr[r^1]+resr;
				l>>=1;r>>=1;
				resl.mx += tag[l];//累加标记值
				resr.mx += tag[r];
			}
			printf("%d\n",Max(0,x-(resl+resr).pos));//没有答案输出0
		}
	}

	// fclose(stdin);
 	// fclose(stdout);
	return 0;
}