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;elseP[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;
}