题解 | #数字游戏#

G.空调遥控 不一样的解法 题目说当且仅当|a[i]-K|<=p时才能保证这个队员被满足，也就是说输入一个温度a[i],k在a[i]-p到a[i]+p这个区间内都会使这个队员被满足。。。

那我们就想到了什么？线段树啊！！用线段树维护区间的最大值,每输入一个温度a[i]就让a[i]-p和a[i]+p这个区间全部+1,而且这个线段树只需要update也不需要建树不需要查询,最后输出tree[1]就好了。

附上AC代码：(注:比赛的时候tree[node<<1|1]给我写成tree[node<<1]|1了然后调不过心态崩了,就没写)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int add[3650000];
int tree[3650000];
int l,r;
void push_down(int node)
{
    if(!add[node])    return;
    add[node<<1] += add[node];
    add[node<<1|1]+=add[node];
    tree[node<<1]+=add[node];
    tree[node<<1|1]+=add[node];
    add[node] = 0;
}
void update(int start,int end,int node)
{
    if(l<=start&&r>=end)
    {
        tree[node]++;
        add[node]++;
        return;
    }
    push_down(node);
    int mid = (start+end)>>1;
    if(l<=mid) update(start,mid,node<<1);
    if(r>mid)  update(mid+1,end,node<<1|1);
    tree[node] = max(tree[node<<1],tree[node<<1|1]);
}

int main()
{
    int n,p,x;
    scanf("%d%d",&n,&p);
    for(int i = 1;i<=n;++i)
    {
        scanf("%d",&x);
        l = max(1,x-p);
        r = x+p;
        update(1,1000002,1);
    }
    cout<<tree[1]<<endl;
    return 0;
}