兔队线段树维护后缀非严格递增子序列的哈希值：CCPC2023深圳K

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134372798

https://vjudge.net/contest/594134#problem/K

场上想到如果两个序列的后缀非严格递增子序列相同则平局，但不知道怎么维护

发现不用输出谁赢，只用判断是否平局，所以肯定是判断两个东西是否相等

然后如果单纯维护后缀非严格递增子序列，可以直接兔队线段树 O(nlog⁡2n)O(n\log^2n)

发现判断相等，直接上哈希。然后拿兔队线段树维护哈希值即可

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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 200010
//#define M
#define mo 998244353
#define m2 (int)(1e9+7)
void Mod(int &a) { if(a>=mo || a<=-mo) a%=mo; if(a<0) a+=mo; }
void Add(int &a, int b) { a+=b; Mod(a); }
void Mul(int &a, int b) { Mod(b); a*=b; Mod(a); } 
int c[N]; 
struct node {
	int s, w; 
	node operator + (const node &A) const {
		node B; B.w=w+A.w; 
		B.s=c[A.w]*s+A.s; Mod(B.s); 
		return B; 
	}
};
int n, m, i, j, k, T;
int n1, n2, q, op, x, y, rt1, rt2; 

struct Segment_tree_Rabbit {
	int tot, ls[N<<2], rs[N<<2]; 
	node L[N<<2], P[N<<2]; 
	int mx[N<<2]; 
	node modify(int k, int l, int r, int Mx) {
		if(l==r) {
			if(P[k].s>=Mx) return P[k]; 
			else return {0, 0}; 
		}
		if(mx[k]<Mx) return {0, 0}; 
		int mid=(l+r)>>1; 
		if(mx[rs[k]]<Mx) return modify(ls[k], l, mid, Mx); 
		else {
			auto t=modify(rs[k], mid+1, r, Mx); 
			return L[k]+t; 
		}
	}
	void push_up(int k, int l, int mid) {
		L[k]=modify(ls[k], l, mid, mx[rs[k]]); 
		P[k]=L[k]+P[rs[k]]; 
		mx[k]=max(mx[ls[k]], mx[rs[k]]); 
	}
	void build(int &k, int l, int r) {
		if(!k) k=++tot; 
		if(l==r) return P[k]={0, 1}, mx[k]=0, void(); 
		int mid=(l+r)>>1; 
		build(ls[k], l, mid); 
		build(rs[k], mid+1, r); 
		push_up(k, l, mid); 
	}
	void add(int k, int l, int r, int x, int y) {
		if(l==r) return P[k]={y, 1}, mx[k]=y, void(); 
		int mid=(l+r)>>1; 
		if(x<=mid) add(ls[k], l, mid, x, y);
		else add(rs[k], mid+1, r, x, y); 
		push_up(k, l, mid); 
		debug("%lld [%lld %lld] %lld %lld (%lld %lld) | %lld %lld\n", 
			k, l, r, P[k].w, P[k].s, x, y, L[k].w, P[rs[k]].w); 
		if(k==1) debug("\n"); 
	}
}Seg1, Seg2;

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	for(i=c[0]=1; i<N; ++i) c[i]=(c[i-1]*m2+mo)%mo; 
	n1=read(); 
	Seg1.build(rt1, 1, n1); 
	for(i=1; i<=n1; ++i) k=read(), Seg1.add(rt1, 1, n1, i, k); 
	n2=read(); 
	Seg2.build(rt2, 1, n2); 
	for(i=1; i<=n2; ++i) k=read(), Seg2.add(rt2, 1, n2, i, k); 
	debug("> %lld %lld\n", Seg1.P[1].w, Seg2.P[1].w); 
	q=read(); 
	while(q--) {
		op=read(); x=read(); y=read(); 
		if(op==1) Seg1.add(rt1, 1, n1, x, y); 
		if(op==2) Seg2.add(rt2, 1, n2, x, y); 
		debug("> %lld %lld\n", Seg1.P[1].w, Seg2.P[1].w); 
		printf(Seg1.P[1].s==Seg2.P[1].s ? "YES\n" : "NO\n"); 
	}
	return 0;
}