P4715 「英语」Z 语言

时间:2023-03-09 20:20:27
P4715 「英语」Z 语言

题解:

平衡树维护hash值

为了支持加入删除操作 x*base^y 其中y为他是第k大

同一般的维护方法,我们不用对每个节点维护他的hash值

而是只用记录他的x值(他的位置) 然后通过updata的时候维护

很神奇的一点是

我用了mo数就炸了。。。

直接自然溢出就好了。。。应该是哪里正负没处理好。。

另外还wa了一个点。。

代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+;
const ll Base=;
ll n,m,q,cl[N],a[N],b[N];
map<ll,ll> M;
struct Splay{
ll count2[N],data[N],ls[N],rs[N],fa[N],v[N],vv[N],root=,cnt=;
void updata(ll x)
{
count2[x]=count2[ls[x]]+count2[rs[x]]+;
data[x]=(data[ls[x]]+1ll*data[rs[x]]*cl[count2[ls[x]]+]
+cl[count2[ls[x]]]*v[x]);
}
void rotate(ll x,ll y)
{
ll fa1=fa[x];
if (y==)
{
rs[fa1]=ls[x];
if (ls[x]) fa[ls[x]]=fa1;
} else
{
ls[fa1]=rs[x];
if (rs[x]) fa[rs[x]]=fa1;
}
fa[x]=fa[fa1];
if (fa[fa1])
{
ls[fa[fa1]]==fa1?ls[fa[fa1]]=x:rs[fa[fa1]]=x;
}
fa[fa1]=x;
if (y==) ls[x]=fa1; else rs[x]=fa1;
updata(fa1); updata(x);
}
void splay(ll x,ll goal)
{
ll fa1=fa[x];
while (fa1!=goal)
{
if (fa[fa1]==goal)
x==ls[fa1]?rotate(x,):rotate(x,);
else
if (fa1==ls[fa[fa1]])
if (x==ls[fa1]) rotate(fa1,),rotate(x,);
else rotate(x,),rotate(x,);
else
if (x==rs[fa1]) rotate(fa1,),rotate(x,);
else rotate(x,),rotate(x,);
fa1=fa[x];
}
if (!goal) root=x;
}
ll search(ll goal)
{
ll x=root;
while (x)
{
if (vv[x]==goal) return(x);
if (vv[x]<goal) x=rs[x];
else x=ls[x];
}
}
void ins(ll y,ll x1)
{
ll x=root;
while (x)
{
if (y>vv[x])
if (rs[x]) x=rs[x]; else break;
else
if (ls[x]) x=ls[x]; else break;
}
if (!x) root=++cnt;
else
{
if (y>vv[x])
{
rs[x]=++cnt; fa[cnt]=x;
} else
{
ls[x]=++cnt; fa[cnt]=x;
}
}
vv[cnt]=y; v[cnt]=x1; count2[cnt]=;
splay(cnt,);
}
void del(ll x1)
{
ll x=search(x1);
splay(x,);
if (!ls[x])
{
root=rs[root]; fa[root]=; return;
}
ll y=ls[x];
while (rs[y]) y=rs[y];
rs[y]=rs[x];
if (rs[y]) fa[rs[y]]=y;
updata(y);
root=ls[x]; fa[ls[x]]=; splay(y,);
}
}A,B;
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
cl[]=;
for (ll i=;i<N;i++) cl[i]=(1ll*cl[i-]*Base);
cin>>n>>m>>q;
ll cnt=;
for (ll i=;i<m;i++) cnt+=cl[i];
for (ll i=;i<=n;i++) cin>>a[i];
for (ll i=;i<=m;i++) A.ins(a[i],i);
++M[A.data[A.root]];
for (ll i=m+;i<=n;i++)
{
A.del(a[i-m]); A.ins(a[i],i);
ll tmp=A.data[A.root]-1ll*cnt*(i-m);
++M[tmp];
}
for (ll i=;i<=m;i++)
{
cin>>b[i];
B.ins(b[i],i);
}
for (ll i=;i<=q;i++)
{
ll x,y;
cin>>x>>y;
B.del(b[x]);
b[x]=y;
B.ins(y,x);
cout<<M[B.data[B.root]]<<endl;
}
return ;
}