2019年CCPC网络赛 HDU 6703 array【权值线段树】_weixin_30488313的博客-程序员资料

技术标签: 数据结构与算法  


题目大意:给出一个n个元素的数组A,A中所有元素都是不重复的[1,n]。
有两种操作:
1.将pos位置的元素+1e7
2.查询不属于[1,r]中的最小的>=k的值。
强制在线。

题解
因为数组中的值唯一,且在1到n的范围内,而询问的r和k也在1到n的范围内。 所以对于任意一个被操 作1修改过的值都不会成为询问的答案,而询问的结果也必然在k到n+1的范围内。 因为没有被修改过 值是唯一的,所以可以建立权值线段树,维护权值区间内的值所在下标的最大值而询问则转化为不小 于k的值里面,下标超过r的最小权值是多少。 如何处理询问呢,一种较为暴力的解法是直接在线段树上 询问权值在k到n+1的范围内第一个下标超过r的权值是多少。但复杂度可能会被卡,需要减枝。 再加上 一个额外的判断就可以了,就是在递归查询完左子树内存不存在大于r的下标之后,如果不存在,则先 看一下右子树内的下标的最大值是否大于r。如果不大于r,则不必再进入右子树内查询,否则答案一定 在右子树内。在进左子树之前也利用同样的判断条件来判断是否有必要进入左子树,这样做可以保证单 次查询的复杂度是O(log n) 的。 而对于操作1,则等价于修改某个权值的下标为无穷大。操作复杂度也 是O(log n )的。 综上所述,得到了一个复杂度为O( m * log n )的在线算法,可以较快地通过此题。

/*HDU 6703 array
权值线段树 在线处理
2019/08/27 12:00
*/
#pragma GCC optimize(3,"Ofast","inline")      //G++
#pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include <functional>
#define TEST freopen("in.txt","r",stdin);
#define mem(a,x) memset(a,x,sizeof(a))
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull; // %llu
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod=1e9+7;
const int INF = 1e6+5;
const int maxn = 1e5+5;
int n,q;
struct node
{
    int l,r,pos;    //建立权值线段树 维护区间下标最大值
} t[4*maxn];
int a[maxn];
void build(int l,int r,int o)   //一颗大树由此而生
{
    t[o].l=l;
    t[o].r=r;
    if(l==r)
    {
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,o<<1);
    build(mid+1,r,o<<1|1);
}
void pushup(int o)          //自如其名 pushup
{
    t[o].pos=max(t[o<<1].pos,t[o<<1|1].pos);
}
void add(int o,int x,int pos)   //添加操作 维护区间下标最大值
{
    if(t[o].l==t[o].r&&t[o].l==x)
    {
        t[o].pos=pos;
        return ;
    }
    int mid=(t[o].l+t[o].r)>>1;
    if(x<=mid)
        add(o<<1,x,pos);
    else
        add(o<<1|1,x,pos);
    pushup(o);
}
int qurey(int o,int l,int r,int ask)
{
    if(t[o].l==t[o].r)      //到叶子节点判读答案是否成立
    {
        if(t[o].pos>ask)
            return t[o].l;
       else
           return INF;
    }
    if(t[o].l==l&&t[o].r==r)        //在当期节点区间时 需要根据左右子树的pos值判读下一步往哪边走(剪枝)
    {
        if(t[o<<1].pos>ask)
        {
            return qurey(o<<1,l,(l+r)>>1,ask);
        }
        else if(t[o<<1|1].pos>ask)
        {
            return qurey(o<<1|1,(l+r)>>1|1,r,ask);
        }
       else
           return INF;
    }
    int mid=(t[o].l+t[o].r)>>1;         //熟悉的操作
    if(r<=mid)
    {
        return qurey(o<<1,l,r,ask);     //锁定区间
    }
    else if(l>mid)
    {
        return qurey(o<<1|1,l,r,ask);   //还是锁定区间
    }
    else
    {
        return min(qurey(o<<1,l,mid,ask),qurey(o<<1|1,mid+1,r,ask));        //锁定区间 答案即可能在左子树也可能在右子树 所以取左右子树中最小的值(有可能左子树返回INF)
    }
}
void init()     //输入
{

    scanf("%d%d",&n,&q);
    build(1,1+n,1);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        add(1,a[i],i);
    }
    add(1,n+1,INF);
}
void solve()        //解决
{
    int op,last=0;      //在线处理
    while(q--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            int pos;
            scanf("%d",&pos);
            pos^=last;
            add(1,a[pos],INF);
        }
        else
        {
            int r,k;
            scanf("%d%d",&r,&k);
            r^=last,k^=last;
            last=qurey(1,k,n+1,r);
            printf("%d\n",last);
        }
    }
}
int main()
{
//    TEST
    int T;
    scanf("%d",&T);
    while(T--)
    {
        mem(t,0);
        init();
        solve();
    }
}
View Code

 

转载于:https://www.cnblogs.com/shuaihui520/p/11419780.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30488313/article/details/101389018

智能推荐

基于dvaJS + react 快速构建项目_weixin_45522694的博客-程序员资料

介绍dva 首先是一个基于 redux 和 redux-saga 的数据流方案,然后为了简化开发体验,dva 还额外内置了 react-router 和 fetch,所以也可以理解为一个轻量级的应用框架。特性1、易学易用,仅有 6 个 api,对 redux 用户尤其友好,配合 umi 使用后更是降低为 0 API2、elm 概念,通过 reducers, effects 和 subscr...

java子类继承父类的哪些方法_关于Java 的继承问题,子类会继承父类的哪些东西?-----转载..._ruigang.wang的博客-程序员资料

和C++类似,可以继承基类的公共属性和方法。在Java继承里,父类的属性还有方法在声明时,如果是public关键字即公共属性,则在子类继承时,这些属性和方法都会被子类继承。受保护的也可以继承但是私有的类属性成员和方法则无法继承。.子类继承父类的成员变量当子类继承了某个类之后,便可以使用父类中的成员变量,但是并不是完全继承父类的所有成员变量。具体的原则如下:1)能够继承父类的public和prote...

vs2010发布时去除msvcp100.dll和msvcr100.dll图解说明_微wx笑的博客-程序员资料

最近开发个程序,Copy到虚拟机环境中测试时提示缺少msvcr100.dll,于是想到编译时设置选项去除依赖。什么是 msvcr100.dll MS = Microsoft V = Visual C = C program language R = Run-time 100 = Version什么是 msvcp100.dllMS = Microsoft V = Visual CP = C++ 10

H.265/HEVC学习笔记:量化_Skyline_98的博客-程序员资料_hevc 量化

&nbsp; &nbsp; &nbsp; &nbsp; 量化是指将信号的连续取值(或者大量可能的离散取值)映射为有限多个离散幅值的过程,实现信号取值多对一的映射。在视频编码中,残差信号经过DCT后,变换系数往往具有较大的动态范围。因此对变换系数进行量化可以有效的减小信号的取值空间,进而获得更好的压缩效果。同时,由于多对一的映射机制,量化过程不可避免地会引入失真,它也是视频编码中产生失真的根本原因。&nbsp; &nbsp; &nbsp; &nbsp; 一个量化器可由其输入端的范围划分方式以及对应的输出值

Spring Security @PreAuthorize 权限控制的原理_PrinciplesMan的博客-程序员资料_spring security preauthorize

@PreAuthorize 注解,顾名思义是进入方法前的权限验证,@PreAuthorize 声明这个方法所需要的权限表达式,例如:@PreAuthorize("hasAuthority('sys:dept:delete')"),根据这个注解所需要的权限,再和当前登录的用户角色所拥有的权限对比,如果用户的角色权限集Set中有这个权限,则放行;没有,拒绝看代码:跟进hasAuthority方法但是,问题来了,这个用户的角色权限Set,是什么时候存入的,其流程如下:附上代码...

随便推点

mysql将图片写入数据库_xfworld的博客-程序员资料

  实现向MYSQL数据库中存储或提取图片文件 一些情况下,需要向数据库中存储一些2进制文件,比如图片文件等,这时候,向数据库存储数据不同于普通的字符串存储,我们需要对这个2进制文件使用JAVA处理2进制流的API进行处理,然后再进行存储。我们需要进行以下步骤来实现: 向数据库中存储文件的时候,一样使用标准SQL语句,如: insert into database (column1, co

VUE中如何将tiff图片显示在浏览器中_weixin_44227826的博客-程序员资料_vue geotiff

**VUE中如何将tiff图片显示在浏览器中**https://github.com/FireGuo/text.git下载tiff.js在index中引入 mounted() { //调用方法 this.loadImage('../../static/pictif.tif'); }, methods:{ loadImage(...

ABP-实体的创建_骗你学计算机的博客-程序员资料_abp 实体对象怎么创建double

首先配置好下载好的ABP框架后(详细看上一遍)前言:我们先不要急配置实体,首先得到一个接口我们在应用层创建一个文件夹persons(主要为来好区分,不用太乱)然后创建一个类PersonApplicaticationService,(命名后缀为 ApplicaticationService :为什么呢?按规矩来总有好处,因为ABP框架可以根据这个后缀名进行自动的依赖注入,这都是后...

GEE批量下载(以modis ndvi为例)_lwb-nju的博客-程序员资料_image.unitscale(-2000, 10000).reproject('epsg:4326

//研究区var roi = ee.FeatureCollection(".......").geometry();//重投影函数var re=function (image) {return image.reproject('EPSG:4326',null, 500);}//批量下载函数function exportImage(image, region, fileName) {Export.image.toDrive({image: image,descripti

Webpack 安装css-loader和style-loader报错_东西方集大成者的博客-程序员资料_webpack下载loader出错

这个Webpack版本冲突坑太多,安装个css-loader和style-loader也是一片祥和的红天。分析下原因吧,我安装css-loader和style-loader的时候直接使用了命令$ cnpm install css-loader style-loader导致报错ERROR in ./node_modules/[email protected]@css-loader/d...

推荐文章

热门文章

相关标签