线段树维护哈希 | CF213E Two Permutations + CF452F Permutation

__终于学到了线段树维护xx，嘿嘿，嘿嘿嘿..树树:D

做了两题，感觉知识点是维护区间相同不相同可以拿hash做，不连续的区间也可以拿hash维护

主要是出得很有想法，太妙了要想得到hh

1. CF213E Two Permutations

考虑枚举x(因为值域不会很大)

观察到其实如果x++，会变动的数只有最左边要被剔除的，和最右边要新增加的，类似于滑动窗口

然后就变成用线段树维护 一个不连续的区间的hash值问题了

具体的，用pos[b[i]]=i表示数b[i]所在的位置，节点的值为该数的值

更新的话:

for(int i=1;i<=m-n;i++){// x ~[1,m-n]
        update(1,pos[i],pos[i],0,-1);//表示去掉最左边
        update(1,pos[n+i],pos[n+i],n+i,1);// 表示增加最右边
        hasha=(hasha+sum)%mod;// 显然x+1，a的hash值要加ΣB[i],i=0~n-1
        if(t[1].ha==hasha) ans++;         
    }

 (注意push_up和update的时候要修改区间长度，才能保证位数是对齐的

以及合并时hash的写法要和下面哈希a时一致，谁是笨蛋我不说

#include<bits/stdc++.h>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const ll base=31;
const ll mod=1e9+7;
const int maxn=2e5+5;
int n,m,a[maxn],b[maxn],pos[maxn];
ll B[maxn];
void init(){
    B[0]=1;
    for(int i=1;i<maxn;i++) B[i]=B[i-1]*base%mod;
}
struct seg{
    int l,r,len;
    ll ha;
/*    seg friend operator +(const seg &a,const seg &b){
        seg ans;
        ans.len=a.len+b.len;
        ans.ha=a.ha+b.ha*B[a.len];
        return ans; 
    }
*/
}t[maxn<<2];
void push_up(int rt){
    t[rt].len=t[ls].len+t[rs].len;
    t[rt].ha=(t[rs].ha+t[ls].ha*B[t[rs].len]%mod)%mod;
    //cout<<ls<<" "<<rs<<" "<<t[ls].len<<endl;
}
void build(int rt,int l,int r){
    t[rt].l=l;t[rt].r=r;
    if(l==r){
        t[rt].len=0;
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    push_up(rt);
}
void update(int rt,int l,int r,int op,int k){
    //cout<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<" "<<l<<" "<<r<<endl;
    if(l<=t[rt].l&&t[rt].r<=r){
        //cout<<rt<<" "<<t[rt].len<<" "<<k<<" "<<op<<endl;
        t[rt].len+=k;
        t[rt].ha=op;
        return;
    }
    if(t[ls].r>=l) update(ls,l,r,op,k);
    if(t[rs].l<=r) update(rs,l,r,op,k);
    push_up(rt);
}
int main(){ 
    //freopen("lys.in","r",stdin);
    fastio;
    init(); 
      
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,m);

    ll hasha=0;
    ll sum=0;
    for(int i=1;i<=n;i++){
        hasha=(hasha*base+a[i])%mod;
        sum=(sum+B[i-1])%mod;
    }

    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=m;i++) pos[b[i]]=i;
    //cout<<"hash: "<<hasha<<endl;
    for(int i=1;i<=n;i++) {
        update(1,pos[a[i]],pos[a[i]],a[i],1);    
    }
    int ans=0;
    if(t[1].ha==hasha) ans++;
    for(int i=1;i<=m-n;i++){// x ~[1,m-n]
        update(1,pos[i],pos[i],0,-1);
        update(1,pos[n+i],pos[n+i],n+i,1);
        hasha=(hasha+sum)%mod;
        if(t[1].ha==hasha) ans++;         
    }
    cout<<ans;    
}

2. CF452F Permutation

哟，又是不连续(

考虑弄一个类似权值线段树的东西，把排列拍成桶

要求存在某个数u，使得u+d和u-d异侧

异侧这个条件转化成：枚举到i时，一个出现在左边（设为1），一个出现在右边（设为0）

如果无解的话，也就是形成了以u为中心的回文串

判回文串同样的用hash就可以

#include<bits/stdc++.h>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=2*int(3e5)+5;
const ll mod=1e9+7;
const ll base=3;
int n;
ll B[maxn];
void init(){
    B[0]=1;
    for(int i=1;i<=3e5;i++)
     B[i]=B[i-1]*base%mod;
}
struct seg{
    int l,r,len;
    ll ha,hb;
    seg friend operator + (const seg &a,const seg &b){
        seg ans;
        ans.l=a.l,ans.r=b.r;
        ans.ha=(b.ha+a.ha*B[b.len]%mod)%mod;
        ans.hb=(a.hb+b.hb*B[a.len]%mod)%mod;
        ans.len=ans.r-ans.l+1;
        return ans;
    }
    //
}t[maxn<<2];
void push_up(int rt){
    t[rt]=t[ls]+t[rs];
}
void build(int rt,int l,int r){
    t[rt].l=l;t[rt].r=r;t[rt].len=r-l+1;
    if(l==r){
       t[rt].ha=t[rt].hb=0;
       return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    push_up(rt);
}
void update(int rt,int l,int r){
    if(l<=t[rt].l&&t[rt].r<=r){
        // update
        t[rt].ha=t[rt].hb=1;
        return;  
    }
    if(t[ls].r>=l) update(ls,l,r);
    if(t[rs].l<=r) update(rs,l,r);
    push_up(rt);
}
seg ask(int rt,int l,int r){
    if(l<=t[rt].l&&t[rt].r<=r){
        return t[rt];
    }
    if(r<=t[ls].r) return ask(ls,l,r);
    if(l>=t[rs].l) return ask(rs,l,r);
    return ask(ls,l,r)+ask(rs,l,r);
} 
int w[maxn];
int main(){
    //freopen("lys.in","r",stdin);
    fastio;
    cin>>n;
    init();
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    update(1,w[1],w[1]);
    for(int i=2;i<n;i++){
        update(1,w[i],w[i]);
        int d=min(w[i]-1,n-w[i]);
        if(!d) continue;
        seg pre=ask(1,w[i]-d,w[i]-1);
        seg aft=ask(1,w[i]+1,w[i]+d);
        //cout<<"debug: "<<w[i]<<" "<<a<<" "<<b<<endl;
        if(pre.ha!=aft.hb){
            return puts("YES"),0; 
        }
        //cout<<"finish "<<i<<endl;
    }
    return puts("NO"),0;
}