[DS记录]P5310 [Ynoi2011] 遥远的过去
command_block
2021-07-06 20:58:27
**题意** ： 定义两个序列匹配当且仅当它们离散化后相同。
给出两个序列 $A,B$ ，支持对 $B$ 进行单点修改，，保证 $A,B$ 中的数字两两不同。
询问 $B$ 在 $A$ 中匹配的次数。
允许离线，$|A|,|B|,q\leq 10^5$ ，时限$\texttt{1s}$。
------------
简单题。
先将数字离散化。
使用 $\rm Hash$ ，先求出 $A$ 的每个长度为 $|B|$ 的子串的 $\rm Hash$ 值，然后动态维护 $B$ 的 $\rm Hash$ 值，容易得到答案。
- ## 处理 $A$
我们需要支持 ：
- 在前端删除一个数
- 在后端插入一个数
使用权值线段树维护。
每个数有两个权值，排名和位权。整个串的 $\rm Hash$ 值是 “排名 $\times$ 位权” 的和。
当在前端删除一个数 $x$ 时，去掉它的贡献，然后将大于 $x$ 的所有数排名减 $1$。
当在后端插入一个数 $x$ 时，他的位权为 $1$。将所有其他数的位权乘以 $B$ ，并将大于 $x$ 的所有数排名加 $1$。
- ## 处理 $B$
只需支持单点修改。
每个数的位权不会变，但是排名可能会边，同样容易使用线段树维护。
复杂度 $O(n\log n)$。
代码实现用了双模。1A 了很开心 qwq~
```cpp
#include<algorithm>
#include<cstdio>
#include<map>
#define Pr pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define MaxN 100500
using namespace std;
const int mod1=998244353,mod2=1000000007,Bas1=233333333,Bas2=1919810;
inline Pr add(Pr A,Pr B)
{return mp((A.fir+B.fir)%mod1,(A.sec+B.sec)%mod2);}
inline Pr mul(Pr A,int c)
{return mp(1ll*A.fir*c%mod1,1ll*A.sec*c%mod2);}
inline Pr mul(Pr A,Pr B)
{return mp(1ll*A.fir*B.fir%mod1,1ll*A.sec*B.sec%mod2);}
void chk(Pr &A)
{A.fir=(A.fir%mod1+mod1)%mod1;A.sec=(A.sec%mod2+mod2)%mod2;}
struct Node
{
Pr s,s0,tg;int c,td;
inline void ladd(int td2)
{td+=td2;s=add(s,mul(s0,td2));}
inline void ltim(Pr tg2)
{tg=mul(tg,tg2);s=mul(s,tg2);s0=mul(s0,tg2);}
}a[1<<20|500];
int tn;
void clr(int l=1,int r=tn,int u=1)
{
a[u].s=a[u].s0=mp(0,0);
a[u].tg=mp(1,1);
a[u].td=a[u].c=0;
if (l==r)return ;
int mid=(l+r)>>1;
clr(l,mid,u<<1);
clr(mid+1,r,u<<1|1);
}
inline void up(int u){
int l=u<<1,r=u<<1|1;
a[u].c=a[l].c+a[r].c;
a[u].s=add(a[l].s,a[r].s);
a[u].s0=add(a[l].s0,a[r].s0);
}
inline void ladd(int u)
{
if (a[u].td){
a[u<<1].ladd(a[u].td);
a[u<<1|1].ladd(a[u].td);
a[u].td=0;
}
if (a[u].tg.fir!=1||a[u].tg.sec!=1){
a[u<<1].ltim(a[u].tg);
a[u<<1|1].ltim(a[u].tg);
a[u].tg=mp(1,1);
}
}
int to;
void del(int l=1,int r=tn,int u=1)
{
if (l==r){
a[u].s=a[u].s0=mp(0,0);
a[u].td=a[u].c=0;
return ;
}int mid=(l+r)>>1;ladd(u);
if (to<=mid)del(l,mid,u<<1);
else del(mid+1,r,u<<1|1);
up(u);
}
int wfc;Pr wfc2;
void ins(int l=1,int r=tn,int u=1)
{
if (l==r){
a[u].s=mul(wfc2,wfc);
a[u].s0=wfc2;a[u].c=1;
return ;
}int mid=(l+r)>>1;ladd(u);
if (to<=mid)ins(l,mid,u<<1);
else ins(mid+1,r,u<<1|1);
up(u);
}
void add(int l=1,int r=tn,int u=1)
{
if (to<=l){a[u].ladd(wfc);return ;}
int mid=(l+r)>>1;ladd(u);
if (to<=mid)add(l,mid,u<<1);
add(mid+1,r,u<<1|1);
up(u);
}
int ret;
void qryc(int l=1,int r=tn,int u=1)
{
if (r<=to){ret+=a[u].c;return ;}
int mid=(l+r)>>1;ladd(u);
qryc(l,mid,u<<1);
if (mid<to)qryc(mid+1,r,u<<1|1);
}
map<Pr,int> ss;
int n,m,q,s[MaxN],b[MaxN],t[MaxN],c[MaxN],sx[MaxN*3]
,pw1[MaxN],pw2[MaxN];
int main()
{
scanf("%d%d%d",&n,&m,&q);
pw1[0]=pw2[0]=1;
for (int i=1;i<=m;i++){
pw1[i]=1ll*pw1[i-1]*Bas1%mod1;
pw2[i]=1ll*pw2[i-1]*Bas2%mod2;
}
for (int i=1;i<=n;i++){
scanf("%d",&s[i]);
sx[++tn]=s[i];
}
for (int i=1;i<=m;i++){
scanf("%d",&b[i]);
sx[++tn]=b[i];
}
for (int i=1;i<=q;i++){
scanf("%d%d",&t[i],&c[i]);
sx[++tn]=c[i];
}
sort(sx+1,sx+tn+1);
tn=unique(sx+1,sx+tn+1)-sx-1;
for (int i=1;i<=n;i++)s[i]=lower_bound(sx+1,sx+tn+1,s[i])-sx;
for (int i=1;i<=m;i++)b[i]=lower_bound(sx+1,sx+tn+1,b[i])-sx;
for (int i=1;i<=q;i++)c[i]=lower_bound(sx+1,sx+tn+1,c[i])-sx;
clr();
for (int i=1;i<=m;i++){
a[1].ltim(mp(Bas1,Bas2));
to=s[i]+1;wfc=1;if (to<=tn)add();
to=s[i];ret=0;qryc();
wfc=ret+1;wfc2=mp(1,1);ins();
}
chk(a[1].s);ss[a[1].s]++;
for (int i=m+1;i<=n;i++){
to=s[i-m];del();
to++;wfc=-1;if (to<=tn)add();
a[1].ltim(mp(Bas1,Bas2));
to=s[i]+1;wfc=1;if (to<=tn)add();
to=s[i];ret=0;qryc();
wfc=ret+1;wfc2=mp(1,1);ins();
chk(a[1].s);ss[a[1].s]++;
}
clr();
for (int i=1;i<=m;i++){
to=b[i]+1;wfc=1;if (to<=tn)add();
to=b[i];ret=0;qryc();
wfc=ret+1;wfc2=mp(pw1[m-i],pw2[m-i]);ins();
}
for (int i=1;i<=q;i++){
to=b[t[i]];del();
to++;wfc=-1;if (to<=tn)add();
b[t[i]]=c[i];
to=c[i]+1;wfc=1;if (to<=tn)add();
to=c[i];ret=0;qryc();
wfc=ret+1;wfc2=mp(pw1[m-t[i]],pw2[m-t[i]]);ins();
chk(a[1].s);
printf("%d\n",ss.find(a[1].s)!=ss.end() ? ss[a[1].s] : 0);
}return 0;
}
```