首页 > 代码库 > hdu 4455 Substrings(树状数组+递推)
hdu 4455 Substrings(树状数组+递推)
题目链接:hdu 4455 Substrings
题目大意:给定一个长度为N的序列,现在有Q次询问,每次给定一个w,表示长度,输出序列中长度为w的连续子序列
的权值和。序列的权值表示序列中不同元素的个数。
解题思路:递推,先预处理处每个位置和前面相同的数据的最短距离P。dp[i]表示说长度为i子序列的权值和,dp[i+1] =
dp[i] + v - c。v为[i+1~N]中P值大于i的个数,我们可以看作将长度为i的子序列长度向后增加1,那么v则为增加长度带来
的权值增加值,c则是最后一个长度为i的序列,因为它不能再增加长度,可是长度又不够,所以只能扣除掉。在递推的
过程中维护c即可,对于P可以用树状数组优化。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6;
int N, A[maxn + 5], P[maxn + 5], T[maxn + 5], fenw[maxn + 5];
ll dp[maxn + 5];
#define lowbit(x) ((x)&(-x))
void add (int x, int d) {
while (x <= maxn) {
fenw[x] += d;
x += lowbit(x);
}
}
int sum(int x) {
int ret = 0;
while (x) {
ret += fenw[x];
x -= lowbit(x);
}
return ret;
}
void init () {
int x;
memset(T, -1, sizeof(T));
memset(fenw, 0, sizeof(fenw));
for (int i = 1; i <= N; i++) {
scanf("%d", &x);
A[i] = x;
if (T[x] == -1)
P[i] = N;
else
P[i] = i - T[x];
T[x] = i;
add(P[i], 1);
}
}
void solve() {
memset(T, 0, sizeof(T));
int c = 1;
dp[1] = N;
T[A[N]] = 1;
for (int i = 2; i <= N; i++) {
add(P[i-1], -1);
int v = sum(maxn) - sum(i-1);
dp[i] = dp[i-1] + v - c;
if (T[A[N-i+1]] == 0) {
T[A[N-i+1]] = 1;
c++;
}
}
}
int main () {
while (scanf("%d", &N) == 1 && N) {
init();
solve();
int Q, x;
scanf("%d", &Q);
while (Q--) {
scanf("%d", &x);
printf("%I64d\n", dp[x]);
}
}
return 0;
}
hdu 4455 Substrings(树状数组+递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。