1 条题解
-
1
考虑设计一个哈希函数 。
其中 表示 。
然后类似于滑动窗口计算区间哈希值,加入一个数就计算贡献,减去一个数就计算这个数产生了贡献,两个东西都可以树状数组维护,那么愉快做完了。
#include<bits/stdc++.h> #define int unsigned long long #define lowbit(x)(x&(-x)) using namespace std; //f(x) 表示 x 前面小于 x 的数的数量 //hash(x) = 1331^(x)*f(x) const int maxn = 1e6+114; const int base = 1145141; int tr[maxn][2],_pow[maxn]; void add(int x,int v,int type){ while(x<maxn){ tr[x][type]+=v; x+=lowbit(x); } } int pre(int x,int type){ int res=0; while(x>0){ res+=tr[x][type]; x-=lowbit(x); } return res; } int a[maxn],b[maxn],n,m,s,val1,ans; queue<int> q; signed main(){ _pow[0]=1; for(int i=1;i<maxn;i++) _pow[i]=_pow[i-1]*base; cin>>n>>m>>s; for(int i=1;i<=n;i++){ cin>>a[i]; a[i]++; } for(int i=1;i<=m;i++){ cin>>b[i]; b[i]++; val1+=_pow[i]*pre(b[i]-1,0); add(b[i],1,0); } for(int i=0;i<maxn;i++) tr[i][0]=tr[i][1]=0; int val2=0,sum=0; for(int i=1;i<=n;i++){ val2+=_pow[i]*pre(a[i]-1,0); add(a[i],1,0); add(a[i],_pow[i],1); sum+=_pow[i]; if(i>m){ val2-=(sum-pre(a[i-m],1)); add(a[i-m],-1,0); add(a[i-m],-_pow[i-m],1); sum-=_pow[i-m]; } if(i>=m){ if(val2==val1*_pow[i-m]){ q.push(i-m+1); } } } cout<<q.size()<<'\n'; while(q.size()>0){ cout<<q.front()<<'\n'; q.pop(); } return 0; } /* 9 6 10 5 6 2 10 10 7 3 2 9 1 4 4 3 2 1 */
感觉最多评绿吧,再高就恶评了(逃。
- 1
信息
- ID
- 1461
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 39
- 已通过
- 12
- 上传者