差分和前缀和刷题

中位数图

好题指数：四星

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

输入：第一行为两个正整数n和b

输出：输出中位数为b的连续子序列的个数

分析：这道题关键点是在于如何快速判断一个子序列中的中位数为b，对每一个子序列进行排序肯定不是最好的做法。假如一个连续子序列中的中位数为b，由于子序列的长度一定是奇数(2n+1)，也就是说只需要剩下有n个比b小，n个数比b大（因为是不重复的）。这就是问题的关键，也就是我们并不关心一个数的具体大小，而是只关心一个数比b大还是比b小，所以我们不妨对于比b大的数赋值为1，等于b的元素赋值为0，小于b的元素赋值为-1，因为只需要判断包含b并且和为0的子序列个数有多少，而子序列的和就自然用到前缀和去处理。

第二个问题就是如果直接使用两重for循环会超时（因为限定时间为1s，而n最大时1e5)。所以同样要换个思路。这里的优化的思路其实和上面的思路差不多，那就是关注问题的本质而不是关注问题的细节，什么是问题的本质呢，也就是我们只需要在idx(b的索引)两边找到一个前缀和相同的两个索引（s[r]==s[l-1]），关键在于我们只在乎个数，而不在乎具体是哪两个索引相等，如果我们跑去关注到底是哪两个索引，那肯定要枚举所有的情况然后去判断，就肯定会超时，这跟上面是一样的，如果我们去关注是具体的值而不是跟b的大小，也没有办法优化。所以一定要关注本质到底是什么。那么其实就是在idx左边找(l-1)分奇偶用哈希表存储个数，右边对应去哈希表查询。为什么要分奇偶呢？因为长度要是奇数个，也就是(r-l为偶数)那么r-(l-1)为奇数。这里有个细节，如果用数组去模拟哈希表的话要注意，存放的值是有正负的，但是索引一定要是正的，所以要加n

代码实现：

#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=1e5+10;
int a[N],s[N];
int ji[2*N],ou[2*N];
int main()
{
    js;int idx;
   int n,b;cin>>n>>b;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        if(x>b)a[i]=1;
        else if(x==b)a[i]=0,idx=i;
        else a[i]=-1;
    }
    //前缀和
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    int res=0;
    //用两重for循环去找会超时
    //所以换个思路其实就是找奇偶相反的前缀和相等的坐标对
    //s[r]-s[l-1]==0->s[r]==s[l-1];
    for(int i=0;i<idx;i++)
    {
        if(i%2==0)ou[s[i]+n]++;
        else ji[s[i]+n]++;
    }
    for(int i=idx;i<=n;i++)
    {
        if(i%2==0)res+=ji[s[i]+n];
        else res+=ou[s[i]+n];
    }
    cout<<res;
}

得到的经验：1.首先关注本质而不是细节 2.对于子序列（连续）问题的优化的关键往往是将区间转化为两个索引来降维

二分

好题指数：三星

我们刚刚学了二分查找——所谓二分查找就是在一堆有序数里找某个符合要求的数。在学完二分查找之后如果让你玩猜数游戏（裁判选定一个目标数字，你说一个数裁判告诉你是高了还是低了直到你猜到那个数）的话，显然你会用二分的方式去猜。

但是不是每一个玩猜数游戏的人都知道二分是最好，甚至一个健忘的玩家都有可能在得到裁判回答的下一个瞬间就忘了他之前问了什么以及裁判的回答），而现在更可怕的是，这个告诉你猜的数是高还是低的裁判他也很健忘，他总是薛定谔的记得这个目标数字，也就是说他的回答有可能出错。我们已经不关心这个不靠谱的游戏本身了，我们更关心裁判这个薛定谔的记得到底有几个是记得……

现在给出这个健忘的玩家的所有猜测和裁判的所有回答，问裁判最多能有多少次是记得目标数字的，即裁判的回复是符合情况的。

输入：

第一行包含一个正整数n，表示裁判的回答数（也是玩家的猜数次数）。

接下来n行，首先是猜的数，然后是一个空格，然后是一个符号。符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。

输出：包含一个正整数，为裁判最多有多少个回答是正确的。

分析：这道题第一个难点就在于如何求最多的正确次数，很明显由于目标数字其实是随意的，所以这道题其实是问存不存在一个数字能满足最多的回答情况，或者说是问所有的数字中，满足情况最多的数字的个数是多少。所以我们就不能从回答的真假性出发，而是认定每一句话都是正确的情况下，哪些数字满足。

比如说5 ‘.’就是只有5满足，8 ‘+’就是小于8的数字都满足，那么每一个数字每满足一条就给他对应加1，这就相当于了在一个区间快速加减一个数，就转化成了差分的问题。但新的问题是，一共有-inf~inf这么多个数，肯定不可能开数组去做，所以肯定得离散化，所以使用map来存储。

那么最后一个问题就是我们不可能遍历所有数然后求最值，但是事实上，我们也不需要，因为map中没有记录的值那一定是0，什么意思呢？就比如map[1]=2 map[5]=-1 那么对于s[1]=map[1]+s[0]，那么s[2]=s[1]+map[0]但是map[0]没有记录就说明他是0，说明s[2]=s1同样的道理，1-5之间的所有数（也就是相邻两个记录的数之间都是一样的）那我们只关注最大的值是多少，不关注具体是哪一个，所以我们只需要遍历map就可以解决问题了。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int inf=INT_MAX;
map<int,int>M;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;char ch;cin>>x>>ch;
        if(ch=='.')M[x]++,M[x+1]--;
        else if(ch=='+')M[-inf]++,M[x]--;
        else M[x+1]++,M[inf]--;
    }
    int res=0;int h=0;
    for(auto x:M)
    {
        h+=x.second;
        res=max(res,h);
    }
    cout<<res;
}