您现在的位置是:首页 > 正文

【Codeforces Round #397】Codeforces 765F Souvenirs【解法二】

2024-04-01 02:37:56阅读 4

解法一(线段树)见这里
我们维护一棵线段树,树上每个结点用平衡树维护含有的元素,并且维护这个区间中的一个值和这个区间右边的另一个值的差的最小值。按区间的左端点从右往左扫描,每次用 ai 对区间 (i,n] 进行覆盖,询问的时候直接询问区间 (l,r] 最小值。
覆盖的时候一般来说需要递归到底,但是这样复杂度还不如暴力。一个重要的剪枝是维护之前已经遍历的区间的前缀最小值【因为递归的过程本来就是前缀实现的】,如果当前区间没有比这个值更优的解,就不再修改,直接返回。
不难发现线段树套平衡树也可以用主席树实现。

#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
const int maxn=2000010,oo=0x3f3f3f3f;
int rd()
{
    int x=0;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
set<int> s[maxn];
vector<int> qry[maxn],v[maxn];
int mn[maxn],a[maxn],l[maxn],r[maxn],ans[maxn],
n,q;
void build(int u,int L,int R)
{
    mn[u]=oo;
    for (int i=L;i<=R;i++) s[u].insert(a[i]);
    if (L==R) return;
    int mid=(L+R)>>1;
    build(u<<1,L,mid);
    build(u<<1|1,mid+1,R);
}
int query(int u,int L,int R,int l,int r)
{
    if (l<=L&&R<=r) return mn[u];
    int mid=(L+R)>>1;
    int ret=oo;
    if (l<=mid) ret=min(ret,query(u<<1,L,mid,l,r));
    if (r>mid) ret=min(ret,query(u<<1|1,mid+1,R,l,r));
    return ret;
}
void modify(int u,int L,int R,int l,int r,int x,int &res)
{
    set<int>::iterator i1=s[u].lower_bound(x),i2;
    if (i1!=s[u].begin())
    {
        i2=i1;
        i2--;
    }
    if ((i1==s[u].end()||*i1-x>=res)&&(i1==s[u].begin()||x-*i2>=res))
    {
        res=min(res,query(u,L,R,l,r));
        return;
    }
    /*if (l<=L&&R<=r)
    {
        if (i1!=s.end()) mn[u]=min(mn[u],*it-x);
        if (i1!=s.begin()) mu[u]=min(mn[u],x-*it);
        v[u].push_back(x);
    }*/
    if (L==R)
    {
        mn[u]=min(mn[u],abs(a[L]-x));
        res=min(res,mn[u]);
        return;
    }
    int mid=(L+R)>>1;
    if (l<=mid) modify(u<<1,L,mid,l,r,x,res);
    if (r>mid) modify(u<<1|1,mid+1,R,l,r,x,res);
    mn[u]=min(mn[u<<1],mn[u<<1|1]);
}
int main()
{
    int res;
    n=rd();
    for (int i=1;i<=n;i++) a[i]=rd();
    q=rd();
    for (int i=1;i<=q;i++)
    {
        l[i]=rd();
        r[i]=rd();
        qry[l[i]].push_back(i);
    }
    build(1,1,n);
    for (int i=n-1;i;i--)
    {
        res=oo;
        modify(1,1,n,i+1,n,a[i],res);
        for (vector<int>::iterator it=qry[i].begin();it!=qry[i].end();++it)
            ans[*it]=query(1,1,n,i+1,r[*it]);
    }
    for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
}

网站文章

  • Hibernate自动建表

    Hibernate自动建表

    在使用&lt;property name="hibernate.hbm2ddl.auto" value="create" /&gt; 这个语句自动建表屡试无果后我决定学习另一种看起来比较麻烦的方法来进...

    2024-04-01 02:37:50
  • freebsd编译生成freenas系统

    1. 安装完成freebsd 2. 安装svn :pkg_add -r subversion 3. 安装nanobsd :pkg_add -r nano 4. 安装cdrtools:pkg_add -r cdrtools 5. 重启freebsd系统:reboot 6. mkdir -p /usr/local/freenas 7.取得freebsd的编译源码:svn co https:

    2024-04-01 02:37:43
  • HTML5前端开发之基础篇

    HTML5前端开发之基础篇

    前端开发工程师实际上是负责IT系统工程的,实际上就是负责信息化系统的设计、建设,包括设备、系统、数据库、应用系统的建设的。说白了,你前期就是个做网页的,但是后期会慢慢变得越来越厉害,自己写网站,做各种动画游戏不再话下,喜欢哪个女生,分分钟在网页上给你画出来花。会了这些害怕追不到妹子么?是不是很流弊?   等你进入公司后,一般来说都是这么分工的: 1.产品需求: 由产品经理给出需求文档

    2024-04-01 02:37:01
  • gocv图片读取并展示

    gocv 图片操作读取原图image := gocv.IMRead("image/img.png",gocv.IMReadColor)读取灰度图image = gocv.IMRead("image/i...

    2024-04-01 02:36:53
  • QT样式表设置 之 QComboBox下拉框样式 热门推荐

    /* 未下拉时,QComboBox的样式 */ QComboBox { border: 1px solid gray; /* 边框 */ border-radius: 3px; /* 圆角 */ padding: 1px 18px 1px 3px; /* 字体填衬 */ color: #000; font: normal normal 15px...

    2024-04-01 02:36:16
  • 关于强化学习不可行动作处理问题

    关于强化学习不可行动作处理问题

    在强化学习学习过程中,往往存在这样一种问题:总的动作空间很大,但是在特定状态下有些动作不可行,如何处理?例如:迷宫问题中当智能体处于迷宫边缘(1,1),此时采取向左或者向上的动作都会超出迷宫边缘。在现...

    2024-04-01 02:36:08
  • HttpWebRequest介绍

    HttpWebRequest和HttpWebResponse类是用于发送和接收HTTP数据的最好选择。它们支持一系列有用的属性。这两个类位于System.Net命名空间,默认情况下这个类对于控制台程序来说是可访问的。请注意,HttpWebRequest对象不是利用new关键字通过构造函数来创建的,而是利用工厂机制(factory mechanism)通过Create()方法来创建的。另

    2024-04-01 02:35:21
  • 如何使用Spark计算共同好友?

    如何使用Spark计算共同好友?

    文章目录写在前面描述计算MapReduce计算共同好友job1的mapper类job1的Reducer类job1的客户端job2的Mapper类job2的Reducer类job2的客户端写在前面你们好...

    2024-04-01 02:35:13
  • EtherCAT从站调试测试

    EtherCAT从站调试测试

    这是我从设计EtherCAT从站到调试过程中所遇到的一些问题记录。 1.Pin65引脚一定要接地 设计之初在刚上电时连接网线,网口指示灯不亮,也一直Twin不上,怀疑LAN9252未正常工作,最后检查...

    2024-04-01 02:35:05
  • oracle11g、10g同时安装数据导入导出无法识别数据库版本问题

    oracle11g、10g同时安装数据导入导出无法识别数据库版本问题

    案例:同一台机器、同一个windows用户下面同时安装了oracle10g/oracle11g 使用导入导出命令时候出现错误。 如下:导出11g数据库中的数据,出现如下错误 虽然安装了oracle11g,但其无法找到11g的版本信息(红色框中所示)。 原因为:由于先安装的11g,后安装的10g。在写入环境变量的时候10g的环境变量在前,在寻找版本信息的时候直接找到的10g的信息,导

    2024-04-01 02:34:58