人物相关性分析 https://www.dotcpp.com/oj/problem2309.html
小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。
更准确的说，小明定义 Alice 和 Bob“同时出现”的意思是:在小说文本 中 Alice 和 Bob 之间不超过 K 个字符。
例如以下文本:
This is a story about Alice and Bob. Alice wants to send a private message to Bob. 假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是”Alice and Bob”
和”Bob. Alice”。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。 注意:
1. Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。
2. Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能
有字母。例如 Bobbi 並不算出现了 Bob。
思路：
最容易想到的是枚举Alice和Bob在文本出现次数，构成两个整数数组，接着二重遍历求解，时间复杂度O(n^2)。但字符串输入长度范围是1e6，如果出现
如AliceBob连续出现的极端情况，时间就达到1e10量级，超时(上界在1e8左右)。
如何由二重循环--->一重？一般有二分，哈希等方法。更进一步理解题意：观察某个首字母在 i 的Alice：与同时出现的Bob可能的范围在[ i - K - 3 , i + 5 + K ]。
而Alice的位置是单调递增的，所以同时出现的Bob其位置也是单调递增的，此时可以采用尺取法求解问题。尺取法通常是指对数组保存一对下标(起点，终点)，
然后根据实际情况交替推进两个端点直到得出答案的方法，类似一段区间缓慢向前移动。
解题思路：
首先分别求出Alice与Bob出现在文本中的位置，用下标 lp 保存第一次出现在可能范围的Bob，rp保存最后一次出现在范围的Bob，用 rp - lp + 1 即得到与
当前Alice同时出现的Bob的个数。
实现代码：
const int INF = 1e8;
int main()
{
/*输入*/
int K;
string str;
cin>>K;
getchar();
getline(cin,str); //输入带有空格的一行字符串
vector<int> alice,bob;
/*保存出现的位置*/
bob.push_back(-INF); /*统一计算*/
int pos = 0;
while( (pos = str.find("Bob",pos)) != string::npos ) //遍历Bob在str出现位置
{
bob.push_back(pos);
pos++;
}
bob.push_back(INF);
pos = 0;
while( (pos = str.find("Alice",pos))!=string::npos )
{
alice.push_back(pos);
pos++;
}
/*尺取法*/
int lp = 0, rp = 0;
int cize = alice.size();
long long ans = 0;
for( int i=0; i<cize; i++ )
{
while( bob[lp]<alice[i]-K-3 ) lp++;
while( bob[rp+1]<=alice[i]+K+5 ) rp++;
if( rp-lp+1 > 0 ) ans += rp - lp + 1;
}
cout<<ans<<endl;
return 0;
}
字串分值
对于一个字符串S，我们定义S的分值 f(S) 为S中七号出现一次的字符串个数。例如 f("aba") = 1，f("abc") = 3，f("aaa") = 0。
现给定一个字符串S[ 0, 1, ..., n-1 ]（长度为n），请你计算对于所有 S 的非空字串 S[ i, ..., j ]（i<=j<n），f(S[ i, ..., j ])的和是多少。
输入一行包含一个由小写字符组成的字符串S。
思路：
最简单的思路即枚举所有字串，优化方案是固定 i ，每次递增 j ，并用一个哈希表判断新的字符是否出现过，时间复杂度O(n^2)。
面临超时问题。观察字符串S = ababc
字串 f值
a 1
ab 2
aba 1
abab 0
ababc 1
b 1
ba 2
bab 1
babc 2
a 1
ab 2
abc 3
b 1
bc 2
c 1
其中加粗的表示分值项。按题意思路是求每行字符串的分值，不可避免的需要遍历所有字串。换个角度，最终目标是求分值和，我们可以求每个字符每列的分值。
如对第一个a，其分值是2。那么如何计算每个字符列分值和呢？观察第二个字符a，其计算分值的行是没有其他字符a的行，那么只要求其前一个a出现的位置 l 与后一个
a出现的位置 r ，那么该a的分值为( i - l )*( r - i )（其中 i 为这个a的下标，那么a的左边有 i - l种可能 × a右边有 r - i 种可能）。
实现代码：
#include<iostream>
#include<string>
using namespace std;
const int Max_N = 100000;
int last[26]; //last[i] : 字符 i+a 最近一次出现的位置
int pre[Max_N]; //pre[i]:i左侧第一个与str[i]位置相同的位置 默认-1
int nxt[Max_N]; //nxt[i]:i右侧第一个与str[i]位置相同的位置 默认 length(str长度)
int main()
{
string str;
cin>>str;
int length = str.length();
/*求pre[]:默认值为-1*/
for( int i=0; i<26; i++ ) last[i] = -1;
for( int i=0; i<length; i++ )
{
int x = str[i] - 'a';
pre[i] = last[x];
last[x] = i;
}
/*求nxt[]:默认值为length*/
for( int i=0; i<26; i++ ) last[i] = length;
for( int i=length-1; i>=0; i-- )
{
int x = str[i] - 'a';
nxt[i] = last[x];
last[x] = i;
}
/*求解*/
long long ans = 0;
for( int i=0; i<length; i++ )
{
ans += (i-pre[i])*(nxt[i]-i);
}
cout<<ans<<endl;
return 0;
}
字串分值和
思路：
与上一题类似，唯一变化的是 f 值的定义。仍然可以用求每个字符列值和的思路，稍有变化的是对于每个字符，其出现多次的分值为1而不是0。
比如aba，前一个a与后一个a总和分值为1，那么给哪一个字符加粗表示其为分值呢？我们可以认为规定一个：对于一个字串种多次出现的字符，我们
只给最左侧加粗即作为分值。
那么对于每个字符，只需要考虑其左侧第一个与其相同的位置而不用考虑右侧，因为对于右侧它的分值都为1。
实现代码：
#include<iostream>
#include<string>
using namespace std;
const int Max_N = 100000;
int last[26]; //last[i] : 字符 i+a 最近一次出现的位置
int pre[Max_N]; //pre[i]:i左侧第一个与str[i]位置相同的位置 默认-1
int main()
{
string str;
cin>>str;
int length = str.length();
/*求pre[]:默认值为-1*/
for( int i=0; i<26; i++ ) last[i] = -1;
for( int i=0; i<length; i++ )
{
int x = str[i] - 'a';
pre[i] = last[x];
last[x] = i;
}
long long ans = 0;
for( int i=0; i<length; i++ )
{
ans += (i-pre[i])*(length-i);
}
cout<<ans<<endl;
return 0;
}
修改数组 https://www.dotcpp.com/oj/problem2301.html
给定一个长度为 N 的数组 A = [A1, A2, · · · AN ]，数组中有可能有重复出现 的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,··· ,AN。
当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则 小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。 现在给定初始的 A 数组，请你计算出最终的 A 数组。
思路
一个简单的思路是模拟：用一个哈希表判断数子 A[ i ] 是否出现过，若出现则 A[ i ] 自增1。其问题仍然是时间复杂度：一个极端情况是A1到AN均为1，那么
时间复杂度有一次来到了O(n^2)。
那么能否一步求得A[ i ]的值呢？考虑维护以及存在整数的区间，如[1，3 ]，[ 17，25 ]，[27，27]
当处理Ai时：
查找是否有区间覆盖A[ i ]
若不存在，则A[ i ]不变
若存在则将A[ i ] 加入集合
将A[ i ]插入集合，处理可能导致的区间合并
那么问题就变成如何实现维护区间的高效数据结构/算法，以及如何更新维护的区间。
具体实现
可以用set<pair<int,int>>维护区间集合，其中pair<int,int>以左右区间端点形式表示区间。
用upper_bound解决是否有区间覆盖A[ i ]；而合并区间A，B可以先删去A，B，在加入A，B合并后的区间。
因为set是用平衡树实现，所以插入删除操作时间复杂度O(logN)，而查找upper_bound是用二分法实现，其时间复杂度也为O(logN)，最终实现的时间复杂度为O(NlogN)。
实现代码
#include<algorithm>
#include<utility>
#include<cstdio>
#include<set>
using namespace std;
typedef set< pair<int,int> > set_pair;
const int INF = 1e8;
const int Max_N = 100000;
int a[Max_N];
int main()
{
int N;
scanf("%d",&N);
for( int i=0; i<N; i++ ) scanf("%d",&a[i]);
set_pair set_;
set_.insert(make_pair(-INF,-INF));
set_.insert(make_pair(INF,INF)); //作为区间的两端 统一算法 关键是第一个值
set_.insert(make_pair(a[0],a[0]));
for( int i=1; i<N; i++ )
{
/* it.first是第一个>a[i]的区间 pre->first<=a[i](小于或等于)*/
set_pair::iterator it = set_.upper_bound(make_pair(a[i],INF));
set_pair::iterator pre = it; pre--;
if( pre->second>=a[i] )
{//有交集 否则pre->second<a[i]且pre->first<=a[i] 那么a[i]与pre无交集
a[i] = pre->second+1;//更新a[i]
}
if( a[i]==pre->second+1 && a[i]==it->first-1 )
{//合并两个区间
set_.insert(make_pair(pre->first,it->second));
set_.erase(pre); set_.erase(it);
}
else if( a[i]==pre->second+1 )
{//只与pre有交集
set_.insert(make_pair(pre->first,a[i]));
set_.erase(pre);
}
else if( a[i]==it->first-1 )
{//只与it有交集
set_.insert(make_pair(a[i],it->second));
set_.erase(it);
}
else
{//不与先有区间有交集
set_.insert(make_pair(a[i],a[i]));
}
}
for( int i=0; i<N; i++ )
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}