P4392 [BOI2007]Sound 静音问题 题解

用树状数组维护区间最值，然后求和即可。

//P4392 [BOI2007]Sound 静音问题
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int INF=0x7f7f7f7f,MAXN=1000005;
struct Bit
{
	int mx,mn;
}tr[MAXN];
int n,m,c,x,a[MAXN];
vector<int> ans;
#define lowbit(x) ((x)&-(x))
void add(int x,int c)
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		tr[i].mx=max(tr[i].mx,c);
		tr[i].mn=min(tr[i].mn,c);
	}
	return;
}
bool sum(int l,int r)
{
	int maxx=-INF,minn=INF;
	while(l<=r)
	{
		while(r-lowbit(r)>=l)
		{
			maxx=max(maxx,tr[r].mx);
			minn=min(minn,tr[r].mn);
			r-=lowbit(r);
		}
		maxx=max(maxx,a[r]);
		minn=min(minn,a[r]);
		r--;
	}
	return abs(maxx-minn)<=c;
}
int main()
{
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=n;i++)
	{
		tr[i].mx=-INF;
		tr[i].mn=INF;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		add(i,a[i]);
	}
	for(int i=1;i<=n-m+1;i++)
	{
		if(sum(i,i+m-1))
		{
			ans.push_back(i);
		}
	}
	if(ans.empty())
	{
		printf("NONE\n");
	}
	else 
	{
		for(int u:ans)
		{
			printf("%d\n",u);
		}
	}
	return 0;
}
/*
 * 洛谷
 * https://www.luogu.com.cn/problem/P4392
 * C++20 -O0
 * 2022.10.8
 */