E. Pretty Song
題目意思是求一個單詞串所有連續子串的元音字母比例之和，原因字母定義為：I, E, A, O, U, Y
舉例來說：
單詞：
BYOB（元音字母有：Y和O）
一個字母的子串：B,Y,O,B
sigma=0/1+1/1+1/1+0/1=2
兩個字母的子串：B,Y,O,B
sigma=0/2+2/2+2/2+0/1=2
三個字母的子串：B,Y,O,B
sigma=0/3+2/3+2/3+0/3=1.33
四個字母的子串：B,Y,O,B
sigma=0/4+1/4+1/4+0/4=0.5
總加和為5.833
通過找規律可以發現，一個字符串的連續子串中每一個字母在該長度所有子串中的出現次數是有規律的
比如一個長度為7的字符串，它的每一個字母在所有子串中的次數如以下矩陣所示：
其中行代表每種長度的子串（從1到n），列代表該字符串中每一個字母在各長度子串中的出現次數
1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 2 3 3 3 2 1
1 2 3 4 3 2 1
1 2 3 3 3 2 1
1 2 2 2 2 2 1
1 1 1 1 1 1 1
假設該矩陣為a[][]，那么最終的答案就應該為sigma(a[i][j]*b[j]/j)，考慮到i和j的范圍都到5*10^5，如果直接算，肯定TLE
然后觀察這個矩陣，發現下一行跟上一行相比，只是多增加了中間一段（比如第二行相比于第一行增加了2~n-1這n-2個位置），而且都是增加1，然后求和的時候除數不同
于是可以想到用樹狀數組/線段樹存儲1~n個元素的值，這樣每次取其中一段求和復雜度就是log級別，時限ok
實現的時候注意這個矩陣是對稱的，所以循環只到行數的一半，奇數行特判一下(這里寫的比較挫)
PS：直接保存累加和就行了。不用樹狀數組啥的，【腦殘。。殺雞用牛刀。。
挫代碼如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
double a[500010];
int fg[500010], n;
char s[500010];
int Lowbit(int n) {
return n & (-n);
}
void Modify(int i) {
while(i <= n) {
a[i] += 1.0;
i += Lowbit(i);
}
}
double Add(int i) {
double res = 0;
while(i != 0) {
res += a[i];
i -= Lowbit(i);
}
return res;
}
int main() {
int i;
double res = 0, pre1 = 0, pre2 = 0, tp = 0, nt = 0;
scanf("%s", s);
memset(a, 0, sizeof(a));
n = strlen(s);
for(i = 0; i < n; ++i) {
if(s[i] == 'I' || s[i] == 'E' || s[i] == 'A' || s[i] == 'O' || s[i] == 'U' || s[i] == 'Y') {
fg[i + 1] = 1;
Modify(i + 1);
}
else
fg[i] = 0;
}
for(i = 1; i <= n/2; ++i) {
res += nt / i;
res += nt / (n-i+1);
tp = Add(n-i+1) - Add(i-1);
nt += tp;
pre1 = tp / i;
pre2 = tp / (n-i+1);
res += pre1;
res += pre2;
}
if(n%2) {
res += nt / i;
tp = Add(n-i+1) - Add(i-1);
nt += tp;
pre1 = tp / i;
res += pre1;
}
printf("%.6lf\n", res);
return 0;
}