本文共 2959 字，大约阅读时间需要 9 分钟。

今天做了多校训练的三道题。

首先做了 OO’s Sequence。

题目大概：

题目给出n个数（0--10000），f（l，r）函数会计算在区间 l 到  r之间的特殊数个数。特殊数是指，在 l 到 r区间内，没有该数的因数。

最终计算如下公式。n最多1e5.

思路：

看了下这个公式，直接计算显然不行，以为要用到10000以内的所有数的因数，所以可以先预处理，把10000以内的数的因数算出来。很容易想到枚举每个数，计算这个数是特殊数的区间个数，因为区间是连续的，我们可以把 i 这个数是特殊数的最大区间给计算出来，然后就可以计算出 i 这个数是特殊数的总和，那么枚举每n次，就可以把这个公式给算出来。这个题的关键就成了怎么求 i 这个数是特殊数的总和。那么就是怎么求没有 i 的因数的最大区间。直接由 i  向两边扩散是不行的，这样复杂度又回去了。因为我们提前已经计算出了所有数的因数，我们就可以在扫描一遍的时候，把所有数 i 的最大区间的左边界给算出来，也可以算出右边界，就是在扫描的时候，把每个出现的数在一个数组里记录一下，并且把这个数的位置记录下来，然后扫描到某个数 i 的时候，就可以把这个数的所有因数扫一遍看是否出现过，出现的最近的位置是什么，这样就在  可以承受  的时间下算出了所有数的边界。这样我们就可以在o（1）的复杂度下计算 i 这个数是特殊数的总和（r-i）*（i-l）。

感想：

这种类型的题，以前做过，当然大部分都在签到题的位置。能扫一遍把很多信息处理出来的前提，就是已知了很多信息，很多信息不用在扫的时候计算，这类问题可以这样o（n*k）的处理出一部分信息，k不大。

代码：

#include 
   
    using namespace std;const int maxn=1e5+10;const int mod=1e9+7;vector
    
     G[maxn];int a[maxn];int l[maxn],r[maxn],id[maxn];long long sum;void init(){    for(int m=1;m<=10000;m++)    {        G[m].push_back(1);        G[m].push_back(m);        for(int i=2;i<=sqrt(m);i++)        {            if(m%i==0)            {                G[m].push_back(i);                G[m].push_back(m/i);            }        }    }}int main(){    int n;    init();    /*    for(int i=1;i<=10;i++)    {        for(int j=0;j
     
      =1;i--)        {            int w=a[i];            int le=G[w].size();            int v=n+1;            for(int k=0;k
     
    
   

 第二道 Assignment

题目大概：

给出n个数，和一个数 k ，计算有多少个区间，使得区间内的数相差不超过k，区间连续。

n最大1e5，k和这n个数1e9.

思路：

这个题就是求有多少个区间最大值和最小值差小于k。因为题目要求区间连续，这个条件很关键，这样，计算起来就很轻松了。我们可以枚举右区间边界，然后，找出符合条件的最大的左区间边界，这样就可以计算出这个区间内符合条件的区间了。通过枚举样例显然发现，当枚举到 i 时，i 前面的区间都已经算出来了，那么，增加了一个数 i ，i 前面的所有符合条件的区间都可以增加1，变成一个新的区间，就是（r-l），当然还增加了一个新的区间，就是  r 本身，它时从无到有，显然，没增加一次右边界，都要进行一次计算（r-l+1）.那怎么才算是符合条件那，就是与区间最大值和最小值的差，不超过k。那这个题的关键就在维护某个区间的最大值和最小值，一开始我是用的multiset 维护，计算错了，后来换了两个双端队列维护。这里用什么都行，比如单调队列，线段树，都可以维护最值。这个题，只要维护好最值，按照推出的小公式计算求和，就解决了。

感想：

这道题和很多求区间最值的问题一样，都是会利用已经扫过去的数，来维护前面的最值，来计算后面的值。一般这种类型的题，用队列解决，最好了，扫到某个数，就入队，某个数不符合条件就出队。这样队列里存的就是符合条件的数。

代码：

#include 
   
    using namespace std;const int maxn=1e5+10;int n,k;int a[maxn];int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&k);        for(int i=0;i