首页 > 代码库 > HDU 4455 Substrings --递推+树状数组优化
HDU 4455 Substrings --递推+树状数组优化
题意： 给一串数字，给q个查询，每次查询长度为w的所有子串中不同的数字个数之和为多少。
解法：先预处理出D[i]为： 每个值的左边和它相等的值的位置和它的位置的距离，如果左边没有与他相同的，设为n+8（看做无穷）。
考虑已知w=k的答案，推w = k+1时，这时每个区间都将增加一个数，即后n-k个数会增加到这些区间中，容易知道，如果区间内有该数，那么个数不会加1，,即D[i] > k时，结果++，即查询后n-k个数有多少个D[i] > k 的数即为要加上的数，然后最后面还会损失一个区间，损失的是不能增加一个数的那个区间，随着w的增加，该区间会向左边伸展，所以记录一下该区间有多少个不同的数即可。 求区间内有多少个D[i]>k可以用树状数组先求有多少个D[i]<=k（getsum(k)），然后区间长度减一下即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define lll __int64using namespace std;#define N 1000107int c[N],n,D[N],Last,vis[N],a[N],pos[N],L[N];lll sum[N];int lowbit(int x) { return x&-x; }void modify(int x,int val){ while(x <= n+10) { c[x]+=val; x += lowbit(x); }}int getsum(int x){ int res = 0; while(x > 0) { res += c[x]; x -= lowbit(x); } return res;}int main(){ int q,i,j,w; while(scanf("%d",&n)!=EOF && n) { for(i=1;i<=n;i++) scanf("%d",&a[i]); memset(pos,0,sizeof(pos)); for(i=1;i<=n;i++) { int x = a[i]; D[i] = i-pos[x]; if(D[i] == i) D[i] = n+8; pos[x] = i; } memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); for(i=2;i<=n;i++) modify(D[i],1); sum[1] = n; Last = 1; vis[a[n]] = 1; for(i=2;i<=n;i++) { sum[i] = sum[i-1]+(n-i+1-getsum(i-1))-Last; modify(D[i],-1); if(!vis[a[n-i+1]]) { vis[a[n-i+1]] = 1; Last++; } } scanf("%d",&q); while(q--) { scanf("%d",&w); printf("%I64d\n",sum[w]); } } return 0;}
HDU 4455 Substrings --递推+树状数组优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。