网站建设淄博佳铉网络,学网站开发前景,网站建设多久,成都网站建设工作https://vjudge.net/contest/594134#problem/K
场上想到如果两个序列的后缀非严格递增子序列相同则平局#xff0c;但不知道怎么维护 发现不用输出谁赢#xff0c;只用判断是否平局#xff0c;所以肯定是判断两个东西是否相等
然后如果单纯维护后缀非严格递增子序列#…https://vjudge.net/contest/594134#problem/K
场上想到如果两个序列的后缀非严格递增子序列相同则平局但不知道怎么维护 发现不用输出谁赢只用判断是否平局所以肯定是判断两个东西是否相等
然后如果单纯维护后缀非严格递增子序列可以直接兔队线段树 O ( n log 2 n ) O(n\log^2n) O(nlog2n)
发现判断相等直接上哈希。然后拿兔队线段树维护哈希值即可
#includebits/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 x0,f1;char chgetchar(); while(ch0||
ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){
x(x1)(x3)(ch^48);chgetchar();}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)(1e97)
void Mod(int a) { if(amo || a-mo) a%mo; if(a0) amo; }
void Add(int a, int b) { ab; 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.wwA.w; B.sc[A.w]*sA.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[N2], rs[N2]; node L[N2], P[N2]; int mx[N2]; node modify(int k, int l, int r, int Mx) {if(lr) {if(P[k].sMx) return P[k]; else return {0, 0}; }if(mx[k]Mx) return {0, 0}; int mid(lr)1; if(mx[rs[k]]Mx) return modify(ls[k], l, mid, Mx); else {auto tmodify(rs[k], mid1, 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) ktot; if(lr) return P[k]{0, 1}, mx[k]0, void(); int mid(lr)1; build(ls[k], l, mid); build(rs[k], mid1, r); push_up(k, l, mid); }void add(int k, int l, int r, int x, int y) {if(lr) return P[k]{y, 1}, mx[k]y, void(); int mid(lr)1; if(xmid) add(ls[k], l, mid, x, y);else add(rs[k], mid1, 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(k1) debug(\n); }
}Seg1, Seg2;signed main()
{#ifdef LOCALfreopen(in.txt, r, stdin);freopen(out.txt, w, stdout);#endif
// Tread();
// while(T--) {
//
// }for(ic[0]1; iN; i) c[i](c[i-1]*m2mo)%mo; n1read(); Seg1.build(rt1, 1, n1); for(i1; in1; i) kread(), Seg1.add(rt1, 1, n1, i, k); n2read(); Seg2.build(rt2, 1, n2); for(i1; in2; i) kread(), Seg2.add(rt2, 1, n2, i, k); debug( %lld %lld\n, Seg1.P[1].w, Seg2.P[1].w); qread(); while(q--) {opread(); xread(); yread(); if(op1) Seg1.add(rt1, 1, n1, x, y); if(op2) Seg2.add(rt2, 1, n2, x, y); debug( %lld %lld\n, Seg1.P[1].w, Seg2.P[1].w); printf(Seg1.P[1].sSeg2.P[1].s ? YES\n : NO\n); }return 0;
}
