2015 多校联赛 ——HDU5289（二分+ST）

Assignment

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 148    Accepted Submission(s): 71

Problem Description

Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the
ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.

Input

In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means the maximum difference between abilities of staff in a group is less
than k. The second line contains n integers:a[1],a[2],…,a[n](0<=a[i]<=10^9),indicate the i-th staff’s ability.

Output

For each test，output the number of groups.

Sample Input

2
4 2
3 1 2 4
10 5
0 3 4 5 2 1 6 7 8 9

Sample Output

5
28

Hint

First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]

给n个数的序列，找出其中有多少[i , j] 满足最大值和最小值的差小于k

枚举左端，

if(last>0&&abs(num[i-1]-num[last])<k)，last记录的是右端最近不满足情况的那个数，假设 i-1到last不满足条件，则说明在i-1<=  x  <=last-1必定有  num[x] - num[last] >= k.    所以判断第i个数时先判断i-1，num[i-1]-num[last])<k 则说明必定存在i<=  x  <=last-1不满足条件，则跳过过这次i判断. （感觉这不是什么正常套路）

官方解：

1. 枚举左端，二分右端，ST求最值

2. 用单调队列维护最值

如果没这个判断则超时，数据真大 - - ！！

<span style="font-size:18px;">#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>

using namespace std;

long long num[101000];

long long s(long long i)
{
    return (1+i)*i/2;
}

int main()
{
    int t, n, k, minx, maxx, last;
    long long int re;
    //freopen("1002.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        re = 0;
        scanf("%d%d", &n, &k);
        for(int i=1; i<=n; i++)
        {
            scanf("%I64d", num+i);
        }
        last = -1;
        for(int i=1; i<=n; i++)
        {
            if(last>0&&abs(num[i-1]-num[last])<k)
            {
                continue;
            }
            minx = num[i];
            maxx = num[i];
            int j;
            for(j=i+1; j<=n; j++)
            {
                if(abs(num[j]-minx)>=k || abs(num[j]-maxx)>=k)
                {
                    break;
                }
                else
                {
                    if(num[j]<minx) minx = num[j];
                    if(num[j]>maxx) maxx = num[j];
                }
            }
            if(last<0)
            {
                re += s(j-i);
                last = j;
            }
            else if(j>last)
            {
                re += (s(j-i) - s(last-i));
                last = j;
            }
        }
        cout<<re<<endl;
    }
    return 0;
}<

RMQ:

#include <cstdio>
#include <iostream>

using namespace std;

int p[200005];
int dp1[200005][30],dp2[200005][30];

void RMQ_init(int n)
{
    for(int i=1; i<=n; i++)
    {
        dp1[i][0]=p[i];
        dp2[i][0]=p[i];
    }
    for(int j=1; (1<<j)<=n; j++)
    {
        for(int i=1; i+(1<<j)-1<=n; i++)
        {
            dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
            dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
        }
    }
}

int rmq(int x,int y)
{
    int k=0;
    while((1<<(k+1))<=y-x+1)k++;
    return max(dp1[x][k],dp1[y-(1<<k)+1][k])-min(dp2[x][k],dp2[y-(1<<k)+1][k]);
}

int main()
{
    int T,n,k;
    //freopen("1002.txt","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(int i = 1; i <= n; i++)
            scanf("%d",&p[i]);

        long long int num = 0;
        RMQ_init(n);

        int temp = 1;
        for(int i = 1; i <= n; i++)
        {
           while(rmq(temp,i) >= k && temp <i)
            temp++;
           num += (i-temp+1);
        }
        printf("%I64d\n",num);
    }
    return 0;