传送门
解题思路
对于每个人的棋子，总是最高的那个棋子发挥决定性作用，被消耗后，再看剩下的最高的棋子。这就相当于单调不递增栈的维护过程。
最后就要比较两个人的单调不递增栈是否完全相同。
和经典的楼房重建相似，但是这个题不止需要维护单调栈的长度，还要维护哈希值。
我是分开写的，但是实际上可以直接用pair表示哈希值和长度，写起来条理一些。
顺便我把序列倒过来了（为了和楼房重建重合度大一些）
AC代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=2e5+5;
const int mod=1e9+7;
int d[2][maxn*4],len[2][maxn*4],n,m,a[2][maxn];
long long Hash[2][maxn*4],mi[maxn];
int getans(int op,int id,int l,int r,int v){
if(l==r) return d[op][id]>=v;
if(d[op][id]<v) return 0;
int mid=(l+r)/2;
if(d[op][id*2]>=v) return getans(op,id*2,l,mid,v)+len[op][id]-len[op][id*2];
return getans(op,id*2+1,mid+1,r,v);
}
long long gethash(int op,int id,int l,int r,int v){
if(l==r) return d[op][id]>=v?Hash[op][id]:0;
if(d[op][id]<v) return 0;
int mid=(l+r)/2;
if(d[op][id*2]>=v) return (gethash(op,id*2,l,mid,v)*mi[len[op][id]-len[op][id*2]]+(Hash[op][id]-Hash[op][id*2]*mi[len[op][id]-len[op][id*2]])%mod+mod)%mod;
return gethash(op,id*2+1,mid+1,r,v);
}
void pushup(int op,int id,int l,int r){
int mid=(l+r)/2;
d[op][id]=max(d[op][id*2],d[op][id*2+1]);
int x=getans(op,id*2+1,mid+1,r,d[op][id*2]);
long long y=gethash(op,id*2+1,mid+1,r,d[op][id*2]);
len[op][id]=len[op][id*2]+x;
Hash[op][id]=(Hash[op][id*2]*mi[x]+y)%mod;
return;
}
void add(int op,int id,int l,int r,int x,int v){
if(l==r){
d[op][id]=v;
len[op][id]=1;
Hash[op][id]=v%mod;
return;
}
int mid=(l+r)/2;
if(x<=mid) add(op,id*2,l,mid,x,v);
else add(op,id*2+1,mid+1,r,x,v);
pushup(op,id,l,r);
}
int main()
{
mi[0]=1;
for(int i=1;i<=200000;i++) mi[i]=mi[i-1]*998244353%mod;
n=read();
for(int i=n;i>=1;i--){
a[0][i]=read();
add(0,1,1,n,i,a[0][i]);
}
m=read();
for(int i=m;i>=1;i--){
a[1][i]=read();
add(1,1,1,m,i,a[1][i]);
}
int T=read();
while(T--){
int op=read(),x=read(),y=read();
if(op==1) add(0,1,1,n,n-x+1,y),a[0][n-x+1]=y;
else add(1,1,1,m,m-x+1,y),a[1][m-x+1]=y;
if(Hash[0][1]==Hash[1][1]) puts("YES");
else puts("NO");
}
return 0;
}