XCPC Notes

Appearance

发布时间：2024-08-07

异或哈希 ​

判断一个区间是否与另外一个区间相等 ​

CF1418G(判断一个有多少个子序列所有数出现恰好3(k)次) ​

  • 对于每种不同的数，赋值一个哈希值
  • 这里使用加减代替异或达到相同效果
  • 具体来讲，对于如果出现了k次，那么就是变成-(k-1)次，那么如果前面出现了k-1次，相加就会等于0
cpp
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1),nums,freq(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++)a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
    vector<ULL> h(n+1),rdm(n+1);
    for(int i=0;i<=n;i++)rdm[i]=rng();
    vector<int> fre(n+1);
    for(int i=1;i<=n;i++){
        h[i]=h[i-1];
        h[i]-=fre[a[i]]*rdm[a[i]];
        (fre[a[i]]+=1)%=k;
        h[i]+=fre[a[i]]*rdm[a[i]];
    }
    fre.assign(n+1,0);
    unordered_map<ULL,int> cnt;
    cnt[0]=1;
    int ans=0;
    for(int i=1,j=0;i<=n;i++){
        fre[a[i]]++;
        while(fre[a[i]]>k){
            fre[a[j]]--;
            cnt[h[j-1]]--;
            j++;
        }
        ans+=cnt[h[i]]++;
    }
    cout<<ans<<"\n";
}

[ABC250E] Prefix Equality ​

题意：

两个序列a,b，每次询问x,y，问a从1-x的集合与b从1-y的集合是否相同

cpp
int a[N],b[N],n;
mt19937_64 rng(time(0));
void solve(){   
    cin>>n;
    vector<int> nums;
    for(int i=1;i<=n;i++)cin>>a[i],nums.push_back(a[i]);
    for(int i=1;i<=n;i++)cin>>b[i],nums.push_back(b[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    vector<int> rdm(nums.size()+1);
    for(int i=0;i<nums.size();i++)rdm[i]=rng();
    for(int i=1;i<=n;i++)a[i]=rdm[lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()];
    for(int i=1;i<=n;i++)b[i]=rdm[lower_bound(nums.begin(),nums.end(),b[i])-nums.begin()];
    vector<int> A(n+1),B(n+1);
    map<int,bool> mpA,mpB;
    for(int i=1;i<=n;i++){
        A[i]=A[i-1];
        B[i]=B[i-1];
        if(!mpA.count(a[i]))A[i]^=a[i],mpA[a[i]]=1;
        if(!mpB.count(b[i]))B[i]^=b[i],mpB[b[i]]=1;
    }
    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        if(A[x]==B[y])cout<<"Yes\n";
        else cout<<"No\n";
    }
}

CF1175F ​

题意：

询问多少个子区间[l,r]满足:

  • 最大值为r-l+1
  • 每个数字只出现一次

思路：

  • 枚举1的位置，然后向左向右扩展
  • 异或哈希判断
cpp
void solve(){   
    cin>>n;
    vector<int> pos;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1)pos.push_back(i);
    }
    for(int i=1;i<=n;i++)rdm[i]=rng(),h[i]=h[i-1]^rdm[i];
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]^rdm[a[i]];
    int ans=0;
    for(int i=0;i<pos.size();i++){
        int L=(i==0?1:pos[i-1]+1),R=(i==pos.size()-1?n:pos[i+1]-1);
        int mx=1;
        for(int j=pos[i];j>=L;j--){
            mx=max(mx,a[j]);
            int l=j,r=j+mx-1;
            if(r>n)continue;
            if((sum[r]^sum[l-1])==h[mx])ans++;
        }
        mx=1;
        for(int j=pos[i]+1;j<=R;j++){
            mx=max(mx,a[j]);
            int l=j-mx+1,r=j;
            if(l<1)continue;
            if((sum[r]^sum[l-1])==h[mx])ans++;
        }
    }
    cout<<ans<<"\n";
}

P6688 可重集 ​

题意：
一个长度为n的数组，q次询问

  • 0 x y把位置为x的数改成y
  • 1 l1 r1 l2 r2询问两个区间是否本质相同

两个本质相同的区间：分别将两个区间排序，存在一个数k使得pi+k=qi

思路：

  • 如果是直接判断相等(k=0)，直接异或哈希即可
  • 这里需要构造一个哈希函数，能快速获得一个区间+k后的哈希值
  • 使用指数函数即可
cpp
const int mod=1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Node{
    int l,r,mn;
    int hsh;
};
int base=rng()%mod,rdm[N];
int a[N];
void init(){
    rdm[0]=1;
    for(int i=1;i<N;i++)rdm[i]=(rdm[i-1]*base)%mod;
}
struct SegmentTree{
    vector<Node> t;
    void init(int n){
        t=vector<Node>(n<<2);
    }
    void pushup(int p){
        t[p].mn=min(t[p<<1].mn,t[p<<1|1].mn);
        t[p].hsh=(t[p<<1].hsh+t[p<<1|1].hsh)%mod;
    }
    void build(int p,int l,int r){
        t[p]={l,r,INF,0};
        if(l==r){
            t[p].mn=a[l];
            t[p].hsh=rdm[a[l]];
            return;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }
    void modify(int p,int x,int y){
        if(t[p].l==t[p].r){
            t[p].mn=y;
            t[p].hsh=rdm[y];
            return;
        }
        int mid=t[p].l+t[p].r>>1;
        if(x<=mid)modify(p<<1,x,y);
        else modify(p<<1|1,x,y);
        pushup(p);
    }
    int query_hash(int p,int l,int r){
        if(l<=t[p].l&&r>=t[p].r)return t[p].hsh;
        int mid=t[p].l+t[p].r>>1;
        int res=0;
        if(l<=mid)(res+=query_hash(p<<1,l,r))%=mod;
        if(r>mid)(res+=query_hash(p<<1|1,l,r))%=mod;
        return res;
    }
    int query_min(int p,int l,int r){
        if(l<=t[p].l&&r>=t[p].r)return t[p].mn;
        int mid=t[p].l+t[p].r>>1;
        int res=INF;
        if(l<=mid)res=min(res,query_min(p<<1,l,r));
        if(r>mid)res=min(res,query_min(p<<1|1,l,r));
        return res;
    }
} seg;
void solve(){   
    init();
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    seg.init(n+1);
    seg.build(1,1,n);
    while(q--){
        int op;
        cin>>op;
        if(op==0){
            int x,y;
            cin>>x>>y;
            seg.modify(1,x,y);
        }
        else{
            int l,r,L,R;
            cin>>l>>r>>L>>R;
            int mn1=seg.query_min(1,l,r),mn2=seg.query_min(1,L,R);
            int h1=seg.query_hash(1,l,r),h2=seg.query_hash(1,L,R);
            if(mn1<=mn2){
                int k=mn2-mn1;
                (h1*=rdm[k])%=mod;
            }
            else{
                int k=mn1-mn2;
                (h2*=rdm[k])%=mod;
            }
            cout<<(h1==h2?"YES\n":"NO\n");
        }
    }
}

Wenwei Lin · 2022 — 2025