Yijan's Blog HomeArchives
某些杂题

Interesting Drug

考虑选择物品的过程，选择物品就会删掉这个东西，所以相当于是一个扩展区间的过程。

第一步选择 $i$ ，也就是说最开始区间是 $(i,i)$ ，每轮可以扩展到 $(i-1,i)$ 和 $(i,i+1)$ 。

把这个看成一个二维平面上行走的过程，那么我们可以把这个过程倒过来，也就是初始在 $(1,n)$ ，走到 $(i,i)$ 能得到的最大权值。

如果第 $i$ 个物品在 $C_i$ 步被选择，相当于是从 $(i+1,i+C_i-1)$ 走到 $(i,i+C_i-1)$ 和 $(i-C_i+1,i - 1)$ 到 $(i-C_i+1 , i)$ 这两种，倒过来就是在新图上，这样的路径有 $D_i$ 的贡献。

这样的路径的端点称为关键点，那么我们可以对关键点排序后用 BIT 来优化 $dp$（查询相当于前缀最大值），复杂度 $O(n\log n)$ 。

小问题在于开始在 $(i,i)$ 相当于第一步拿 $(i,i)$ ，直接给结束在 $(i,i)$ 的方案加上如果第一步选择 $i$ 可以获得贡献。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000056
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int C[MAXN] , D[MAXN];
 
struct tcurts {
	int sx , sy , tx , ty , w;
} S[MAXN] ;
 
bool cmp( tcurts& a , tcurts& b ) {
	return a.sx != b.sx ? a.sx < b.sx : a.sy > b.sy;
}
 
ll T[MAXN];
void add( int x , ll c ) {
	x = n * 2 - x + 1;
//	cout << "add " << x << ' ' << c << endl;
	while( x <= n * 2 + 4 ) T[x] = max( T[x] , c ) , x += ( x & -x );
}
ll mx( int x ) {
	x = n * 2 - x + 1;
//	cout << "Find " << x << endl;
	ll as = 0;
	while( x > 0 ) as = max( as , T[x] ) , x -= ( x & -x );
	return as;
}
 
ll dp[MAXN] , ans[MAXN];
 
void solve() {
	cin >> n;
	rep( i , 1 , n ) scanf("%d",C + i);
	rep( i , 1 , n ) scanf("%d",D + i);
	int num = 0;
	rep( i , 1 , n ) {
		if( C[i] != 1 && i + C[i] - 1 <= n ) S[++ num] = (tcurts) { i , i + C[i] - 1 , i + 1 , i + C[i] - 1 , D[i] };
		if( i - C[i] + 1 >= 1 ) S[++ num] = (tcurts) { i - C[i] + 1 , i , i - C[i] + 1 , i - 1 , D[i] };
	}
	rep( i , 1 , n ) S[++ num] = (tcurts) { i , i , 0 , 0 , 0 };
	sort( S + 1 , S + 1 + num , cmp );
	int cur = 1 , ls;
	rep( i , 1 , num ) {
		if( cur > num ) break;
		int tx = S[cur].sx , ls = cur;
		while( cur <= num && S[cur].sx == tx ) {
			dp[cur] = mx( S[cur].sy ) + S[cur].w;
			if( S[cur].tx == S[cur].sx ) add( S[cur].ty , dp[cur] );
			++ cur;
		}
		rep( j , ls , cur ) 
			if( S[j].tx && S[j].tx != S[j].sx ) add( S[j].ty , dp[j] ); 
	}
	rep( i , 1 , num ) if( !S[i].tx ) ans[S[i].sx] = dp[i];
	rep( i , 1 , n ) printf("%lld ",ans[i] + ( C[i] == 1 ? D[i] : 0 ) );
}
 
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

Parklife

考虑把区间的包含关系建成树，然后相当于是树上选择若干点，满足所有节点被覆盖了不超过 $k$ 次。

于是可以考虑一个 $dp$ ：

朴素 $dp$ 是 $O(n^2)$ 的。

转移的本质是对儿子求和，然后与 $\{0,A[u]\}$ 做 $(\max,+)$ 卷积。

通过打表可以发现，这个 $dp$ 是凸的。

所以可以用 堆 来维护 $dp$ 数组的差分，差分是递减的，于是在每个点我们相当于堆里插入一个 $A[u]$ 。相当于在某个 $i$ 不会选择让儿子中的点被自己再选择一次，而是选择这个点本身。

复杂度 $O(n\log n)$

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];
struct tcurts {
	int l , r , val;
} S[MAXN] ;
bool cmp( tcurts a , tcurts b ) {
	return a.l != b.l ? a.l < b.l : a.r > b.r;
}

vi G[MAXN];
vector<pii> stk;

int mxd[MAXN] , hea[MAXN];
void afs( int u , int f ) {
	mxd[u] = 1;
	for( int v : G[u] ) if( v != f ) {
		afs( v , u );
		if( mxd[v] + 1 > mxd[u] ) {
			mxd[u] = mxd[v] + 1;
			hea[u] = v;
		}
	}
}

void dfs( int u , int f , multiset<int,greater<int>>& Q ) {
	if( !hea[u] ) {
		Q.insert( A[u] );
		return;
	}
	multiset<int,greater<int>> q;
	dfs( hea[u] , u , Q );
//	if( u == 1 ) { for( int x : Q ) printf("%d ",x); puts(""); }
	
	for( int v : G[u] ) if( v != f && v != hea[u] ) {
		q.clear();
		dfs( v , u , q );
		auto itq = q.begin() , itQ = Q.begin();
		int cur = 0 , tt = 0;
		vi qwq;
		while( itq != q.end() ) {
			tt = (*itQ) + (*itq);
			qwq.pb( tt );
			++ itQ , ++ itq;
		}
		Q.erase( Q.begin() , itQ );
		for( int t : qwq ) Q.insert( t );
	}
//	if( u == 1 ) { for( int x : Q ) printf("%d ",x); puts(""); }
	if( u ) Q.insert( A[u] );
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) {
		scanf("%lld%lld%lld",&S[i].l,&S[i].r,&S[i].val);
	}
	sort( S + 1 , S + 1 + n , cmp );
	int cur = 1 , las = 1;
	stk.eb( mp( 11451419 , 0 ) );
	rep( i , 1 , n ) {
		while( stk.back().fi <= S[i].l ) stk.pop_back();
//		cout << stk.back().se << ' ' << i << endl;
		G[stk.back().se].pb( i ) , A[i] = S[i].val;
		stk.eb( mp( S[i].r , i ) );
	}
	afs( 0 , 0 );
	multiset<int,greater<int>> Q;
	dfs( 0 , 0 , Q );
	int ans = 0;
	for( auto v : Q ) {
//		cout << v << endl;
		ans += v;
		printf("%lld ",ans);
	}
	rep( i , Q.size() + 1 , n ) printf("%lld ",ans);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
 

Code-Cola Plants

考虑条件从 $a$ 出发经过 $A$ 边集能走到所有点，如果所有除 $a$ 点都有一条入边在 $A$ 中，那么明显所有点都可以从 $a$ 到达。由于只有 $n-1$ 条边可以用，这必要性也显然。

同理，我们知道题目限制相当于是每个点有一个入边在 $A$ 一个出边在 $B$ 。

然后发现可以拆点，对所有点建立入点和出点，这样就是对于一个点，它可以匹配很多个边，左边放点右边放边后相当于是做一个二分图匹配，直接跑即使用网络流复杂度也难以接受（虽然用一些神仙板子还是可以跑过去的）。

考虑这个二分图的性质，发现它本质上是一个点边匹配。我们拆点后，从 $u$ 的出点向 $v$ 的入点连无向边后，相当于是要选择一些边，给这些边定向，满足除开 $a$ 的入点和 $b$ 的出点外，所有点周围都有一条边指向这个点（也就是说这个点和这个边匹配）。也就是，现在我们只需要不关注 $a$ 的入点和 $b$ 的出点的情况下，找到这个图上的一个基环树，然后环上任意顺序，环外从里到外连就好了。不难发现这个图可能是不联通的，但是显然这无关紧要，对每个联通块跑一次就行了。复杂度 $O(n + m)$ 。

找基环树的过程参考了某个标算，这样写看起来非常简洁。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , a , b;
 
vector<pii> G[MAXN];
int vis[MAXN];
int wi[MAXN];
 
int pt , ed;
void afs( int u , int ef ) {
	vis[u] = 2;
	for( auto& t : G[u] ) if( t.se != ef ) {
		int v = t.fi;
		if( vis[v] == 2 ) pt = v , ed = t.se;
		else if( !vis[v] ) afs( v , t.se );
	}
	vis[u] = 3;
}
void dfs( int u , int ef ) {
	vis[u] = 1;
	for( auto& t : G[u] ) if( t.se != ef ) {
		int v = t.fi;
		if( vis[v] == 3 ) wi[t.se] = v , dfs( v , t.se );
	}
}
 
void solve() {
	while( cin >> n >> m >> a >> b ) {
		rep( i , 1 , n * 2 ) vis[i] = 0 , G[i].clear();
		rep( i , 1 , m ) wi[i] = 0;
		vis[a + n] = vis[b] = 1;
		rep( i , 1 , m ) {
			static int u , v;
			scanf("%d%d",&u,&v);
			G[u].eb( mp( v + n , i ) ) , G[v + n].eb( mp( u , i ) );
		}
		int flg = 0;
		rep( i , 1 , n << 1 ) if( !vis[i] ) {
			pt = ed = 0;
			afs( i , 0 );
			if( !pt ) { puts("NO"); flg = 1; break; }
			wi[ed] = pt;
			dfs( pt , ed );
		}
		if( flg ) continue;
		vi A , B;
		rep( i , 1 , m ) if( wi[i] ) if( wi[i] > n ) A.pb( i ); else B.pb( i );
		puts("YES");
		for( int t : A ) printf("%d ",t); puts("");
		for( int t : B ) printf("%d ",t); puts("");
	}
}
 
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

Dev, Please Add This!

不愧是 Petr 评价的 Best Problem 2018。

我们考虑一个球，当它滚到某个位置后，可以这么滚一波：

相当于我们可以拿完这个极长连续段内的所有星星。也就是说，如果可以到达所有极长连续段，那么我们就必然可以拿完所有星星。对于起点来说，它确实只能往某一个方向去滚，所以我们可以认为起点连续段有两种，要么是起点竖直方向连续段，要么是水平方向。

假设当球在某个点，它往某个方向跑后只能到达所在的极长连续段的一端。于是我们可以考虑给每个横着的、竖着的极长连续段建个点，然后建条边到其两端的点所在的另一个方向的极长连续段。

然后何时能够拿到一颗星星，相当于是这个星星所在点的竖直连续段和水平连续段有一个被经过了。我们可以设 $v_i$ 表示 $i$ 这个点在结束滚球后是否有被经过，那么这个限制相当于是 $v_{H_i} \or v_{V_i} = 1$ 也就是要么这个点的水平连续段被经过，要么竖直连续段被经过。因为我们的目的是拿到所有星星，所以这些条件必须全部被满足。

首先预处理出所有可达关系，也就是对于 $i,j$ 我们处理出 $i\to j,j \to i$ 是否可通过有向图到达。

再考虑，假设对于任意两个点，它们互相不可达，那么我们在这两个点之间只会选择一个点到达，也就是 $v_i \and v_j = 0$ 。

再对于从两个出发点都无法到达的点 $i$ ，我们认为 $i$ 是必然不可到达的，也就是 $v_i = 0$ 。

现在，做一次 2-Sat 就做完了。为什么呢？

考虑两个点 $i,j$ ，如果 $i$ 可以到达 $j$ 但是 $j$ 无法到达 $i$ ，我们认为 $i > j$ 。同时，如果 $i,j$ 互相可达，我们认为 $i = j$。

假装我们现在找到了一个满足上述三种条件的一个点的集合 $S$ ，那么其中任意两个点，必然有一个这两个点之间的可达关系。也就是说任意两个点都可比。于是我们必然可以把这个集合进行一个类比的“排序”。同时，不存在一个同时大于两个出发点的点，那么通过调整，一定可以让某个出发点作为开始。也就是，最后我们一定可以找到一个 $S$ 中元素的排列，让第一个点是出发点，同时之后的点上一个点可以到达这一个点。这不就是找到了一个可行解吗？

复杂度是 $O(n^2m^2)$ 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "assert.h"
using namespace std;
#define MAXN 506
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
char ch[MAXN][MAXN];
int S[MAXN][MAXN] , H[MAXN][MAXN] , cnt;
 
vi G[5006];
vector<pii> tt;
 
int abl[5006][5006];
int st;
void dfs( int u ) {
	abl[st][u] = 1;
	for( int v : G[u] ) if( !abl[st][v] ) 
		dfs( v );
}
 
vi gg[1000006];
 
int dfn[5006] , low[5006] , stk[5006] , top , ins[5006] , clo , scc , bel[5006];
void tarjan( int u ) {
	dfn[u] = low[u] = ++ clo , stk[++ top] = u , ins[u] = 1;
	for( int v : gg[u] ) {
		if( !dfn[v] ) tarjan( v ) , low[u] = min( low[u] , low[v] );
		else if( ins[v] ) low[u] = min( low[u] , dfn[v] );
	}
	if( dfn[u] == low[u] ) {
		int x; ++ scc;
		do {
			x = stk[top--];
			ins[x] = 0;
			bel[x] = scc;
		} while( x != u );
	}
}
 
void solve() {
	cin >> n >> m;
	rep( i , 1 , n ) scanf("%s",ch[i] + 1);
	rep( i , 1 , n ) ch[i][0] = ch[i][m + 1] = '#';
	rep( i , 1 , m ) ch[0][i] = ch[n + 1][i] = '#';
	rep( i , 1 , n ) rep( j , 1 , m ) 
		if( ch[i][j] != '#' ) {
			if( ch[i][j - 1] == '#' ) H[i][j] = ++ cnt;
			else H[i][j] = H[i][j - 1];
		}
	rep( j , 1 , m ) rep( i , 1 , n ) 
		if( ch[i][j] != '#' ) {
			if( ch[i - 1][j] == '#' ) S[i][j] = ++ cnt;
			else S[i][j] = S[i - 1][j];
		}
	int ss = 0 , sh = 0;
	rep( i , 1 , n ) rep( j , 1 , m ) {
		if( ch[i][j] != '#' ) {
			if( ch[i][j - 1] == '#' || ch[i][j + 1] == '#' ) G[H[i][j]].pb( S[i][j] );
			if( ch[i - 1][j] == '#' || ch[i + 1][j] == '#' ) G[S[i][j]].pb( H[i][j] ); 
		}
		if( ch[i][j] == 'O' ) sh = H[i][j] , ss = S[i][j];
		if( ch[i][j] == '*' ) { // S[i][j] | H[i][j] = 1
			gg[S[i][j] + cnt].pb( H[i][j] );
			gg[H[i][j] + cnt].pb( S[i][j] );
		}
	}
	assert( ss && sh );
	rep( i , 1 , cnt ) {
		st = i;
		dfs( st );
	}
	rep( i , 1 , cnt ) rep( j , 1 , i ) if( !abl[i][j] && !abl[j][i] ) 
		gg[i].pb( j + cnt ) , gg[j].pb( i + cnt );
	rep( i , 1 , cnt ) if( !abl[ss][i] && !abl[sh][i] ) 
		gg[i].pb( i + cnt );
	rep( i , 1 , cnt << 1 ) if( !dfn[i] ) tarjan( i );
	rep( i , 1 , cnt ) if( bel[i] == bel[i + cnt] ) return void( puts("NO") );
	puts("YES");
}
 
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

Dstorv

直接 $dp$ ，状态是前 $i$ 个人，当前剩下 $j$ 个向左，$k$ 个向右，但是不太能优化。

考虑任意一种情况，必然都是从某个点断开，这个点之前最后会成为 $A$ 个向左的人，这个点之后变成 $B$ 个向右的人。我们考虑枚举这个分界点，设 $dp[i][j]$ 表示前 $i$ 个人，在右边还有 $j$ 个向左的人正在走过来时，最终剩下 $A$ 个向左的人的概率。

我们考虑第 $i$ 个人，如果原本是在左走，那么 $dp[i - 1][j + 1] \to dp[i][j]$。

如果原本在往右走，那么 $[j \ge 1] (l \times dp[i][j - 1] + r \times dp[i - 1][j])$ 。

直接转移即可，复杂度 $O(n^2)$。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 5006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 1000000007 
typedef long long ll;
int n , r , h , pl , a , b;
int A[MAXN];
 
int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}
 
int dpl[MAXN][MAXN] , dpr[MAXN][MAXN]; char S[MAXN];
 
int work( int dp[MAXN][MAXN] , char* S , int x ) {
	dp[0][x] = 1;
	rep( i , 1 , n ) {
		if( S[i] == 'H' ) 
			rep( j , 0 , n ) dp[i][j] = dp[i - 1][j + 1];
		else 
			rep( j , 0 , n ) dp[i][j] = ( j >= 1 ? ( pl * 1ll * dp[i][j - 1] + ( 1 - pl + P ) * 1ll * dp[i - 1][j] ) % P : 0 );
	}
}
 
void solve() {
	cin >> n >> r >> h;
	scanf("%s",S + 1);
	cin >> a >> b;
	swap( a , b );
	pl = h * 1ll * Pow( r + h , P - 2 ) % P;
	work( dpl , S , a );
	reverse( S + 1 , S + 1 + n );
	rep( i , 1 , n ) S[i] = ( S[i] == 'H' ? 'R' : 'H' );
	pl = r * 1ll * Pow( r + h , P - 2 ) % P;
	work( dpr , S , b );
	int res = 0;
	rep( i , 0 , n ) res = ( res + dpl[i][0] * 1ll * dpr[n - i][0] % P ) % P;
	cout << res << endl;
}
 
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

The Jump from Height of Self-importance to Height of IQ Level

我们考虑用平衡树来处理平移。

然后对于每个平衡树上的点，考虑这段区间，我们打一个标记表示是否存在长度为 $3$ 的上升子序列。

如果无长度为 $3$ 的上升子序列，我们再维护一下区间内的最大（$mx$）、最小值（$mn$），以及区间内长度为 $2$ 的上升子序列的开头的最大值（$smx$）以及结尾的最小值（$smn$）。

然后考虑 pushup 操作。最大最小值的维护显然。考虑长度为 $2$ 的开头的最大值这个东西，结尾最小值维护方式类似。

首先可以继承左右儿子的这个值。然后需要考虑从左右各选出一个点的情况，右儿子必然选择 $mx$ ，那么我们需要在左儿子中找小于这个数的最大值。可以发现，左儿子中小于这个数的数必然单调递减，否则可以形成长度为 $3$ 的上升子序列。于是我们直接在平衡树上二分即可，具体操作是看右儿子中最小值是否小于这个数，如果是递归到右儿子，否则到左儿子，随时拿当前节点的值取 $\max$ 即可。

pushup 的复杂度是 $O(\log n)$ 的，总复杂度是 $O(n\log^2 n)$。

我用的 splay 成功被卡常了，一种优化方法是 rotate 的时候只对曾经的父亲进行 pushup ，splay 结束后再对这个点本身 pushup ，可以卡过去（）

然后介绍一下 $O(n \sqrt n \log n)$ 的做法，而且这个做法速度吊打我的做法（splay 太慢辣）

考虑对询问分块，我们用块内涉及到的分界点砍成 $O(\sqrt n)$ 块，然后相当于是进行排序，询问是否有长度为 $3$ 的上升子序列。对于任意一个序列，我们可以通过两个桶来解决是否存在长度为 $3$ 的上升子序列这个问题，大概就是往桶里递减地塞数，如果第一个不行酒塞第二个，如果都不行那么存在长度为 $3$ 的上升子序列。对每个段维护这样的桶的开头结尾即可，每个询问块只需要跑一次，一次 $O(n)$ ，具体可以参考神仙 zjk 的提交。

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "assert.h"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , q;
int A[MAXN];
 
int ch[MAXN][2] , fa[MAXN] , mn[MAXN] , mx[MAXN] , smn[MAXN] , smx[MAXN] , siz[MAXN] , ok[MAXN] , idx , rt;
 
int lower( int u , int x ) {
	if( ch[u][0] && mn[ch[u][0]] < x ) return max( A[u] < x ? A[u] : 0 , lower( ch[u][0] , x ) );
	else if( ch[u][1] && mn[ch[u][1]] < x ) return max( A[u] < x ? A[u] : 0 , lower( ch[u][1] , x ) );
	else return A[u] < x ? A[u] : 0;
}
int upper( int u , int x ) {
	if( ch[u][1] && mx[ch[u][1]] > x ) return min( A[u] > x ? A[u] : 0x3f3f3f3f , upper( ch[u][1] , x ) );
	else if( ch[u][0] && mx[ch[u][0]] > x ) return min( A[u] > x ? A[u] : 0x3f3f3f3f , upper( ch[u][0] , x ) );
	else return A[u] > x ? A[u] : 0x3f3f3f3f;
}
 
void pu( int u ) {
	int ls = ch[u][0] , rs = ch[u][1];
	siz[u] = siz[ls] + siz[rs] + 1;
	mx[u] = max( mx[ls] , mx[rs] ) , mn[u] = min( mn[ls] , mn[rs] );
	mx[u] = max( mx[u] , A[u] ) , mn[u] = min( mn[u] , A[u] );
	if( siz[u] == 1 ) { smx[u] = 0 , smn[u] = 0x3f3f3f3f , ok[u] = 0; return; }
	ok[u] = 0;
	if( ok[ls] || ok[rs] || ( ls && rs && ( ( mn[ls] < A[u] && A[u] < mx[rs] ) || smx[rs] > mn[ls] || smn[ls] < mx[rs] ) ) || ( ls && smn[ls] < A[u] ) || ( rs && smx[rs] > A[u] ) ) {
		ok[u] = 1;
		return;
	}
	smx[u] = max( smx[ls] , smx[rs] );
	smn[u] = min( smn[ls] , smn[rs] );
	if( ls ) smx[u] = max( smx[u] , lower( ls , max( mx[rs] , A[u] ) ) ) , smn[u] = min( smn[u] , mn[ls] < A[u] ? A[u] : 0x3f3f3f3f );
	if( rs ) smn[u] = min( smn[u] , upper( rs , min( mn[ls] , A[u] ) ) ) , smx[u] = max( smx[u] , mx[rs] > A[u] ? A[u] : 0 );
}
 
void rotate( int u ) {
	int f = fa[u] , g = fa[f] , k = ch[f][1] == u , w = ch[u][k ^ 1];
	if( g ) ch[g][ch[g][1] == f] = u; ch[u][k ^ 1] = f , ch[f][k] = w;
	fa[w] = f , fa[f] = u , fa[u] = g;
	pu( f );
}
void splay( int u , int t = 0 ) {
	if( u == t ) return;
	int f , g;
	while( fa[u] != t ) {
		int f = fa[u] , g = fa[f];
		if( g != t ) rotate( ( ( ch[f][1] == u ) ^ ( ch[g][1] == f ) ) ? u : f );
		rotate( u );
	}
	pu( u );
	if( !t ) rt = u;
}
 
int build( int l , int r , int f ) {
	if( l > r ) return 0;
	int u = l + r >> 1;
	fa[u] = f;
	int ls = build( l , u - 1 , u ) , rs = build( u + 1 , r , u );
	ch[u][0] = ls , ch[u][1] = rs;
	pu( u );
	return u;
}
 
int rnk( int u , int x ) {
	if( siz[ch[u][0]] >= x ) return rnk( ch[u][0] , x );
	else if( x == siz[ch[u][0]] + 1 ) return u;
	else return rnk( ch[u][1] , x - siz[ch[u][0]] - 1 );
}
 
//void wkr( int l , int r , int k ) {
//	++ l , ++ r;
//	int u = rnk( rt , l - 1 ) , v = rnk( rt , r - k + 1 );
//	splay( u ) , splay( v , u );
//	int t = ch[v][0];
//	ch[v][0] = fa[t] = 0;
//	pu( v ) , pu( u );
//	u = rnk( rt , r - ( r - k - l + 1 ) ) , v = rnk( rt , r + 1 - ( r - k - l + 1 ) );
//	splay( u );
//	splay( v , u );
//	ch[v][0] = t , fa[t] = v;
//	pu( v ) , pu( u );
//}
 
void wkr( int l , int r , int k ) {
	if( k == 0 || k == r - l + 1 ) return;
	++ l , ++ r;
	int u = rnk( rt , l - 1 ) , v = rnk( rt , r - k ) , x = rnk( rt , r );
	splay( u ) , splay( v , u ) , splay( x , v );
	int q = ch[x][1];
	fa[x] = u , fa[v] = x , fa[q] = v;
	ch[u][1] = x , ch[x][1] = v , ch[v][1] = q;
	pu( v );
	pu( x );
	pu( u );
}
 
void solve() {
	memset( mn , 0x3f , sizeof mn ) , memset( smn , 0x3f , sizeof smn );
	cin >> n;
	A[1] = 0x3f3f3f3f , A[n + 2] = -0x3f3f3f3f;
	rep( i , 2 , n + 1 ) scanf("%d",&A[i]);
	rt = ( 1 + n + 2 ) >> 1;
	build( 1 , n + 2 , 0 );
//	cout << ok[rt] << endl;
	cin >> q;
	while( q-- ) {
		static int l , r , k;
		scanf("%d%d%d",&l,&r,&k);
		wkr( l , r , k );
		puts(ok[rt] ? "YES" : "NO");
	}
}
 
signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
文章作者: yijan
文章链接: https://yijan.co/mou-xie-zha-ti/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！