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

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

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

---

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

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

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

#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 LOCALfreopen("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;
}