题解 P4392 【[BOI2007]Sound 静音问题】

· · 题解

超级树状数组

对于大部分oier来说，码线段树是一件十分困难的事情，对于这一个OB的算法又不得不去学习

而对于另一种友好的树形结构——树状数组就特别好码，可惜的是只能去求区间的和，以及单点修改

真的是这样吗？树状数组不是什么鸡肋，其实可以和线段树有一样的操作，对于区间的最大最小，是可以手动维护的

void add(int p,int x)//添加一个数（不能修改）
{
    for(;p<=n;p+=p&(-p))
    {
        c[p].mx=max(c[p].mx,x);//维护区间的最大以及最小
        c[p].mn=min(c[p].mn,x);
    }
}

之后求和就好了

bool sum(int l,int r)
{
    int mx=-0x7f7f7f7f,mn=0x7f7f7f7f;
    while(l<=r)
    {
        for(;r-(r&(-r))>=l;r-=r&(-r))//标配
        {
            mx=max(c[r].mx,mx);
            mn=min(c[r].mn,mn);
        }
        mx=max(mx,a[r]);
        mn=min(mn,a[r]);
        r--;//不是所有区间都已处理，所以会多次维护
    }
    if(abs(mx-mn)<=ci)
    return true;
    return false;
}

a下这到题目只需要上述两个操作

下面ac代码

#include<bits/stdc++.h>
using namespace std;
struct tree{
    int mx=-0x7f7f7f7f,mn=0x7f7f7f7f,a;
}c[1100101];
int n,m,ci,ans[1000001],a[1000001],cnt;
void add(int p,int x)
{
    for(;p<=n;p+=p&(-p))
    {
        c[p].mx=max(c[p].mx,x);
        c[p].mn=min(c[p].mn,x);
    }
}
bool sum(int l,int r)
{
    int mx=-0x7f7f7f7f,mn=0x7f7f7f7f;
    while(l<=r)
    {
        for(;r-(r&(-r))>=l;r-=r&(-r))
        {
            mx=max(c[r].mx,mx);
            mn=min(c[r].mn,mn);
        }
        mx=max(mx,a[r]);
        mn=min(mn,a[r]);
        r--;
    }
    if(abs(mx-mn)<=ci)
    return true;
    return false;
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&ci);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&a[i]);
        add(i,a[i]);
    }
    for(int i=1;i<=n-m+1;i++)
    {
        if(sum(i,i+m-1))
        ans[++cnt]=i;
    }
    for(int i=1;i<=cnt;i++)
    {
        printf("%d\n",ans[i]);
    }
    if(cnt==0)
    cout<<"NONE";
}

其实怎么做的原因，手动模拟一下树状数组的维护操作就可以知道

其实我们还可以进行区间修改以及查询

void add(int c[],int p,int x)
{
    while(p<=n)
    {
        c[p]+=x;
        p+=p&(-p);
    }
}
void modify(int l,int r,int x)//区间修改（l——r的每一个数加上x）
{
    add(d1,l,x);
    add(d1,r+1,-x);
    add(d2,l,x*(l-1));
    add(d2,r+1,-x*r);
}
int sum_(int c[],int p)
{
    int s=0;
    while(p)
    {
        s+=c[p];
        p-=p&(-p);
    }
    return s;
}
int query(int l,int r)//区间求和（l——r）
{
    return r*sum_(d1,r)-sum_(d2,r)-((l-1)*sum_(d1,l-1)-sum_(d2,l-1));//想一想，为什么（huaji）
}

那么我们就用简单易懂的树状数组代替了线段树，由于代码量少，认真思考一两分钟就可以得出原因的代码，就不多加阐述

在考场上，面对功能极度全面的线段树O（Ologn），以及代码量少的树状数组O（nlognlogn），加以权衡

其实想要详细解释，可以去看洛谷日报22期，有说明和图的