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 
   
     #include 
    
      #include 
     
       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; }