今天，我們回顧回顧曾經的知識。

1.二分

還記得當初的二分嗎？

1.一開始的二分

就像下面這個故事：

有一只老鼠，躲在10個大瓷瓶后面。你的任務就是抓住這只老鼠，但在抓的過程會導致你選擇的大瓷瓶成為分子碎片。

如果挨個攻擊，最壞的情況是大瓷瓶全部打碎，那樣你的媽媽會很生氣的。（洛西：真可怕。）

所以，你可以每次把正中間的大瓷瓶打碎，若沒打到，老鼠發出的“吱吱”聲會提醒你老鼠在哪里。

2.現在的二分的特點

1.單調性

想必你知道一點吧！假如我們有變量mid，l，r，k，d。每一行的第k大的最大值不超過d等價于每一行都至少有m-k+1個<=d的數字。

單調性如下：

若mid可以，[mid,r]顯然是可以的，[l,mid]卻不一定，因為所有行的第k大的最大值<=100，所有行的第k大的最大值也一定可以<=101

?2.雙指針

雙指針，就是同時使用兩個指針，在序列、鏈表結構上指向的是位置，在樹、圖結構中指向的是節點，通過或同向移動，或相同移動來維護、統計信息。

3.前綴和差分

1.差分思想

其實，差分是把“區間操作”轉化為“兩點操作”，大大加快了速度。這也就是一些復雜的題要用適合的算法。

2.舉例

假設有一個序列a,它的差分數組b定義為：

b[1]=a[1]

b[i]=a[i]-a[l-1](2<=l<=n)

4.代碼題

題目描述

靈夢有?n?個單詞想要背，但她想通過一篇文章中的一段來記住這些單詞。

文章由?m?個單詞構成，她想在文章中找出連續的一段，其中包含最多的她想要背的單詞（重復的只算一個）。并且在背誦的單詞量盡量多的情況下，還要使選出的文章段落盡量短，這樣她就可以用盡量短的時間學習盡可能多的單詞了。

輸入格式

第?1?行一個數?n，接下來?n?行每行是一個長度不超過?10?的字符串，表示一個要背的單詞。

接著是一個數?m，然后是?m?行長度不超過?10?的字符串，每個表示文章中的一個單詞。

輸出格式

輸出文件共?2?行。第?1?行為文章中最多包含的要背的單詞數，第?2?行表示在文章中包含最多要背單詞的最短的連續段的長度。

#include<bits/stdc++.h>
using namespace std;
map<string,bool> tar;
map<string,int> cnt;
string s[100005];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){string str;cin>>str;tar[str]=1;}int ans=0,len,m;cin>>m;for(int i=1,j=1;i<=m;i++){cin>>s[i];if(tar[s[i]]){cnt[s[i]]++;}if(cnt[s[i]]==1){ans++;len=i-j+1;}while(j<=i){if(cnt[s[j]]==1){break;}if(cnt[s[j]]>=2){cnt[s[j]]--;j++;}if(!tar[s[j]]){j++;}}len=min(len,i-j+1);}cout<<ans<<endl<<len;return 0;
}