前言

今天給大家帶來兩道貢獻法的問題，先來講一下什么是貢獻法。

貢獻法，與其說是一種算法，不如說是一種數學方法，是一種思維方式。

先來給大家舉個例子，假設現在有個問題，需要你在一個只有小寫字母的字符串中查找所有僅包含一個字符a的子串數量。

暴力的話是枚舉所有子串，O(n^2)顯然不符合我們的預期，那么有什么方法優化呢？

這就要用到我們今天要講的貢獻法了，這一種橫看成嶺側成峰的算法，我們來觀察下面的樣例。

bbbbbacccc

可以發現在中間位置出現了a，我們將a的左右兩側劃分出來。

bbbbb|a|cccc

問題就轉化成了在a的左邊選一個字母，同時在a的右邊選一個字母的所有選法。

我們設左邊的字符數量為left，右邊的字符數量為right，那么根據排列組合的知識可以得到子串數量為：

(left + 1) * (right + 1)

注意這里要加一因為a也要算進去。

以上就是貢獻法的大致思路，所謂橫看成嶺側成峰，就是從結果出發，逆推出有效的結論。

可能有的小伙伴發現了我們這個題目有一個要求，即——僅包含一個字符a。

那我們就來想一下，如果沒有這個條件，貢獻法可不可行呢？

答案是否定的，我們來觀察下面的序列

bbbbabbabbb

可以明顯的發現最長的串是同時包含兩個a的，而我們使用貢獻法就需要分別求出包含指定a的所有子串，我們將這些子串視為一個集合。

在計算完所有包含指定的a的所有子串后我們要進行集合合并，而根據容斥原理，集合合并時需要減去兩個集合的交集，顯然這個交集我們是不好求出來的。

造成這種情況的原因就是兩個集合不是互斥的，放在概率論中就可以說兩個條件不是獨立的。

所以在判斷能否使用貢獻法之前需要先判斷一下給定的條件能否使每個元素的貢獻皆相互獨立。

反之，如果發現條件能夠使整個結果的集合劃分為幾個部分，那么就可以使用貢獻法。（反應在題目中一般就是“唯一”，“單個”等詞）

紙上學來終得錢，接下來我們就根據具體的題目分析，一起來看看所謂的“貢獻法”到底有何魔力。

---

孤獨的照片

---

分析

暴力枚舉所有區間的話時間復雜度是O(n^2)，顯然行不通，但是我們發現所有的孤獨的照片都有一個特點，即——同時包含兩種牛，并且其中有一種牛的數量為1。

很敏銳的發現題目中有唯一的條件，那么可不可以用我們上面講的貢獻法來寫呢？

使用貢獻法需要滿足一個條件，即——我們選定的貢獻的對象可以將要求的集合劃分。

很顯然是可以的，因為兩頭可能孤獨的牛不會出現在同一張“孤獨的照片”內，所以任意兩頭牛產生的貢獻的交集為空集，所以我們可以使用貢獻法。

那么接下來我們就來思考一下如何使用貢獻法。

根據上面的思路，我們需要通過排列組合來每頭牛的貢獻就要保證當前區間只有一頭此類牛。

這個簡單，我們預處理出每頭牛左邊和右邊的同類牛的位置(使用掃描法)，就可以計算出對于每頭牛的最長的“孤獨的照片”，隨后進行排列組合就好了。

這道題排列組合有一個小技巧，因為有一個要求最短區間長度為3，所以我們需要分類討論該位置在區間兩邊和在區間中間的情況。

---

代碼

/*貢獻法
*/
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 500010;
char s[N];
int n;
int l[N], r[N];
LL ans;LL find(char x)
{int m = 0;memset(l, 0, sizeof(l)); memset(r, 0, sizeof(r));for(int i = 1; i <= n; i++)if(s[i] == x)l[i] = m, m = i;m = n + 1;for(int i = n; i >= 1; i--)if(s[i] == x)r[i] = m, m = i;// 預處理LL ls = 0;for(int i = 1; i <= n; i++){if(s[i] == x) //匹配了{int left = i - l[i] - 1, right = r[i] - i - 1; //左右長度//printf("%d %d %d ", i, left, right);ls += max((LL)0, (LL)left * right);ls += max(0, left - 1);ls += max(0, right - 1);}}return ls;
}int main()
{scanf("%d%s", &n, s + 1);ans += find('G');ans += find('H');printf("%lld", ans);return 0;
}

---

子串分值

---

分析

可以發現題目中有唯一的要求，所以我們考慮使用貢獻法。

那么，接下來我們要如何來劃分呢？

這個簡單，我們通過26個英文字母來劃分，因為f函數是求貢獻和，所以我們每次只求單個字符的貢獻，最后加起來就一定是貢獻和。

但是如果這道題是要我們判斷區間內存在個數為1的字符的區間的數量，顯然就無法直接用貢獻法求解了，需要進一步的分析。

---

代碼

// 貢獻法，枚舉26個字母，貢獻求和
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
char s[N];
int n, l[N], r[N];
LL idx;
LL find(char x)
{int m = 0; LL idx = 0;for(int i = 1; i <= n; i++)if(s[i] == x)l[i] = m, m = i;m = n + 1;for(int i = n; i >= 1; i--)if(s[i] == x)r[i] = m, m = i;for(int i = 1; i <= n; i++){if(s[i] == x){int left = i - l[i] - 1, right = r[i] - i - 1;idx += ((LL)left + 1) * (right + 1);}}return idx;
}int main()
{scanf("%s", s + 1);for(int i = 1; s[i]; n = i++);for(char x = 'a'; x <= 'z'; x++)idx += find(x);printf("%lld", idx);return 0;
}