bzoj3110（线段树套线段树、树状数组套线段树）_三角形数阵　线段树-程序员宅基地

技术标签： 基本算法  acm  

http://www.lydsy.com/JudgeOnline/problem.php?id=3110
题意：
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

tip：

线段树套线段树，外面是权值，每个节点上的线段树是位置，
比如，如果在1~4位置加入5 就是把整个线段树中有5的log个节点，
每个节点的1~4这log区间上++。。。。
然后每次询问的时候，二分答案，
比如权值二分到3就是求1~3中有多少个在询问的区间里，还是log个节点，
每个节点跑log个得到对应区间上的个数总和

这样会ｔｌｅ＆＆　ｍｌｅ，代码如下：

/*
线段树套线段树，外面是权值，每个节点上的线段树是位置，
比如，如果在1~4位置加入5 就是把整个线段树中有5的log个节点，
每个节点的1~4这log区间上++。。。。
然后每次询问的时候，二分答案，
比如权值二分到3就是求1~3中有多少个在询问的区间里，还是log个节点，
每个节点跑log个得到对应区间上的个数总和

*/

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long LL;
const int maxn = 3e7+10;
const int maxm = 50000*4+10;
int root[maxm],N,Q;
struct pos_Tree{
    int lon,ron,add;
    unsigned int _size;
    void init(){
        lon = ron  = add = _size = 0;
    }
};

class segment_tree{
public:
    pos_Tree tree[maxn];LL cnt;
    void push_down(int k,int m,int l,int r){
        if(tree[k].add == 0)    return ;
        if(tree[k].lon == 0){
            cnt++;tree[k].lon = cnt;//tree[cnt].l = l;tree[cnt].r = (l+r)/2;
            tree[cnt]._size = (m-(m/2))*tree[k].add;tree[cnt].add = tree[k].add;
        }
        else    tree[tree[k].lon]._size +=(m-(m/2))*tree[k].add,tree[tree[k].lon].add += tree[k].add;
        if(tree[k].ron == 0){
            cnt++;tree[k].ron = cnt;//tree[cnt].l = (l+r)/2+1;tree[cnt].r = r;
            tree[cnt]._size = (m/2)*tree[k].add;tree[cnt].add = tree[k].add;
        }
        else    tree[tree[k].ron]._size +=(m/2)*tree[k].add,tree[tree[k].ron].add += tree[k].add;
        tree[k].add = 0;
    }
    void push_up(int k,int ln,int rn){
        tree[k]._size = tree[ln]._size+tree[rn]._size;
    }
    void _insert(int &k,int L,int R,int l,int r,int rt){
        if(k == 0){
            cnt++;tree[cnt].init();k = cnt;//tree[k].l = l;tree[k].r = r;
        }
        if(L <= l && R >= r){
            tree[k].add++;tree[k]._size += r-l+1;
            return ;
        }
        push_down(k,r-l+1,l,r);
        int m = (l+r)>>1;
        if(m >= L)  _insert(tree[k].lon,L,R,lson);
        if(m < R)   _insert(tree[k].ron,L,R,rson);
        push_up(k,tree[k].lon,tree[k].ron);
    }
    LL query(int k,int L,int R,int l,int r,int rt){
        if(l >= L && r <= R){
            return tree[k]._size;
        }
        push_down(k,r-l+1,l,r);
        //cout <<" k = "<<k<<endl;
        int m = (l+r)/2;
        LL ans = 0;
        if(m >= L && tree[k].lon)  ans += query(tree[k].lon,L,R,lson);
        if(m < R && tree[k].ron)   ans += query(tree[k].ron,L,R,rson);
        return ans;
    }
}pos_tree;//区间线段树

void build(int l,int r,int rt){
    root[rt] = 0;
    if(l == r)  return ;
    int m = (l+r)>>1;
    build(lson);
    build(rson);
}

void val_insert(int a,int b,int pos,int l,int r,int rt){
    if(pos >= l && pos <= r){
        pos_tree._insert(root[rt],a,b,1,N,1);
    }
    if(l == r)   return ;
    int m = (l+r)>>1;
    if(pos <= m)    val_insert(a,b,pos,lson);
    else    val_insert(a,b,pos,rson);
}

int _in(int mid,int l,int r,int rt){
    if(l == r && l == mid)  return root[rt];
    int m = (l+r)>>1;
    if(mid <= m)  return _in(mid,lson);
    else    return _in(mid,rson);

}

LL check(int L,int R,int posa,int posb,int l,int r,int rt){
    if(L <= l && R >= r){
        if(root[rt] == 0)   return 0;
        LL ans = pos_tree.query(root[rt],posa,posb,1,N,1);
        return ans ;
    }
    LL ans = 0;
    int m = (l+r)>>1;
    if(m >= L)  ans += check(L,R,posa,posb,lson);
    if(m < R)   ans += check(L,R,posa,posb,rson);
    return ans;
}

int bs(int posa,int posb,int c){
    int l = 1,r = N,ans = 100000000;
    while(l <= r){
        int mid = (l+r)>>1;
        LL pp = check(1,mid,posa,posb,1,N,1);
        if( pp >= c){
   //1~mid权值中到了c个就是可能得解，多了就缩小范围
            if(_in(mid,1,N,1))//mid是否是出现了得权值
                ans = min(ans,mid);
            r = mid-1;
        }
        else    l = mid+1;
    }
    return ans;
}
int op,a,b,c;
void sov(){
    pos_tree.cnt = 0;
    for(int i = 1;  i<= Q ; i++){
        scanf("%d",&op);
        if(op == 1){
            scanf("%d%d%d",&a,&b,&c);
            if(a > b)   swap(a,b);
            c = N-c+1;
            val_insert(a,b,c,1,N,1);
        }
        else{
            scanf("%d%d%d",&a,&b,&c);
            if(a > b)   swap(a,b);
            printf("%d\n",N-bs(a,b,c)+1);
        }
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(~scanf("%d%d",&N,&Q)){
        build(1,N,1);
        sov();
    }
    return 0;
}
/*
7 100
1 1 5 2
1 2 7 3
1 3 5 2
1 1 1 1
2 1 3 2
2 1 3 3
2 1 3 7
2 1 7 5
2 1 7 7
2 2 3 2
2 1 1 1
2 1 1 2
2 3 5 3
2 3 4 5
2 1 5 2
2 2 7 2
2 3 5 2
2 2 2 1
*/

tle版本（树状数组套线段树）：

改成树状数组，ｍｌｅ问题解决,时间复杂度仍然有logloglog

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long LL;
const int maxn = 3e7+10;
const int maxm = 50000+10;
int root[maxm],N,Q;
struct pos_Tree{
    int lon,ron,add;
    unsigned int _size;
    void init(){
        lon = ron  = add = _size = 0;
    }
};

class segment_tree{
public:
    pos_Tree tree[maxn];LL cnt;
    void push_down(int k,int m,int l,int r){
        if(tree[k].add == 0)    return ;
        if(tree[k].lon == 0){
            cnt++;tree[k].lon = cnt;//tree[cnt].l = l;tree[cnt].r = (l+r)/2;
            tree[cnt]._size = (m-(m/2))*tree[k].add;tree[cnt].add = tree[k].add;
        }
        else    tree[tree[k].lon]._size +=(m-(m/2))*tree[k].add,tree[tree[k].lon].add += tree[k].add;
        if(tree[k].ron == 0){
            cnt++;tree[k].ron = cnt;//tree[cnt].l = (l+r)/2+1;tree[cnt].r = r;
            tree[cnt]._size = (m/2)*tree[k].add;tree[cnt].add = tree[k].add;
        }
        else    tree[tree[k].ron]._size +=(m/2)*tree[k].add,tree[tree[k].ron].add += tree[k].add;
        tree[k].add = 0;
    }
    void push_up(int k,int ln,int rn){
        tree[k]._size = tree[ln]._size+tree[rn]._size;
    }
    void _insert(int &k,int L,int R,int l,int r,int rt){
        if(k == 0){
            cnt++;tree[cnt].init();k = cnt;//tree[k].l = l;tree[k].r = r;
        }
        if(L <= l && R >= r){
            tree[k].add++;tree[k]._size += r-l+1;
            return ;
        }
        push_down(k,r-l+1,l,r);
        int m = (l+r)>>1;
        if(m >= L)  _insert(tree[k].lon,L,R,lson);
        if(m < R)   _insert(tree[k].ron,L,R,rson);
        push_up(k,tree[k].lon,tree[k].ron);
    }
    LL query(int k,int L,int R,int l,int r,int rt){
        if(l >= L && r <= R){
            return tree[k]._size;
        }
        push_down(k,r-l+1,l,r);
        //cout <<" k = "<<k<<endl;
        int m = (l+r)/2;
        LL ans = 0;
        if(m >= L && tree[k].lon)  ans += query(tree[k].lon,L,R,lson);
        if(m < R && tree[k].ron)   ans += query(tree[k].ron,L,R,rson);
        return ans;
    }
}pos_tree;//Çø¼äÏ߶ÎÊ÷

int lowbit(int x){
    return x&(-x);
}

void add(int pos,int a,int b){
    for(int i = pos ; i <= N ;i += lowbit(i)){
        pos_tree._insert(root[i],a,b,1,N,1);
    }
}

LL check(int pos,int posa,int posb){
    LL sum = 0;
    for(int i = pos; i>0 ;i-=lowbit(i)){
        sum += pos_tree.query(root[i],posa,posb,1,N,1);
    }
    return sum;
}

int bs(int posa,int posb,int k){
    int l = 1,r = N;
    while(l <= r){
        int mid = (l+r)>>1;
        LL cm = check(mid,posa,posb);//1~mid
        LL cm1 = check(mid-1,posa,posb);//1~mid-1
        if(cm >= k &&  cm1 < k){
            return mid;
        }
        else if(cm >= k)  r = mid-1;
        else    l = mid+1;  //cm<k&&cm1<k

    }
}
int op,a,b,c;
void sov(){
    pos_tree.cnt = 0;
    for(int i = 1;  i<= Q ; i++){
        scanf("%d",&op);
        if(op == 1){
            scanf("%d%d%d",&a,&b,&c);
            c = N-c+1;
            if(a > b)   swap(a,b);
            add(c,a,b);
        }
        else{
            scanf("%d%d%d",&a,&b,&c);
            if(a > b)   swap(a,b);
            printf("%d\n",N-bs(a,b,c)+1);
        }
    }
}



int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(~scanf("%d%d",&N,&Q)){

        sov();
    }
}

ac版本：

超时？不用二分答案，在线段树上，直接判断大的数够不够，不够的话，往左跑看加上多少左边的可以到达要求个，够的话就往右递归，看最小的范围（ｌ==r）时候，ac代码：

/*
线段树套线段树，外面是权值，每个节点上的线段树是位置，
比如，如果在1~4位置加入5 就是把整个线段树中有5的log个节点，
每个节点的1~4这log区间上++。。。。
然后每次询问的时候，
每个节点跑log个得到对应区间上的个数总和

*/

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef long long LL;
const int maxn = 3e7+10;
const int maxm = 50000*4+10;
int root[maxm],N,Q;
struct pos_Tree{
    int lon,ron,add;
    unsigned int _size;
    void init(){
        lon = ron  = add = _size = 0;
    }
};

class segment_tree{
public:
    pos_Tree tree[maxn];LL cnt;
    void push_down(int k,int m,int l,int r){
        if(tree[k].add == 0)    return ;
        if(tree[k].lon == 0){
            cnt++;tree[k].lon = cnt;//tree[cnt].l = l;tree[cnt].r = (l+r)/2;
            tree[cnt]._size = (m-(m/2))*tree[k].add;tree[cnt].add = tree[k].add;
        }
        else    tree[tree[k].lon]._size +=(m-(m/2))*tree[k].add,tree[tree[k].lon].add += tree[k].add;
        if(tree[k].ron == 0){
            cnt++;tree[k].ron = cnt;//tree[cnt].l = (l+r)/2+1;tree[cnt].r = r;
            tree[cnt]._size = (m/2)*tree[k].add;tree[cnt].add = tree[k].add;
        }
        else    tree[tree[k].ron]._size +=(m/2)*tree[k].add,tree[tree[k].ron].add += tree[k].add;
        tree[k].add = 0;
    }
    void push_up(int k,int ln,int rn){
        tree[k]._size = tree[ln]._size+tree[rn]._size;
    }
    void _insert(int &k,int L,int R,int l,int r,int rt){
        if(k == 0){
            cnt++;tree[cnt].init();k = cnt;//tree[k].l = l;tree[k].r = r;
        }
        if(L <= l && R >= r){
            tree[k].add++;tree[k]._size += r-l+1;
            return ;
        }
        push_down(k,r-l+1,l,r);
        int m = (l+r)>>1;
        if(m >= L)  _insert(tree[k].lon,L,R,lson);
        if(m < R)   _insert(tree[k].ron,L,R,rson);
        push_up(k,tree[k].lon,tree[k].ron);
    }
    LL query(int k,int L,int R,int l,int r,int rt){
        if(l >= L && r <= R){
            return tree[k]._size;
        }
        push_down(k,r-l+1,l,r);
        //cout <<" k = "<<k<<endl;
        int m = (l+r)/2;
        LL ans = 0;
        if(m >= L && tree[k].lon)  ans += query(tree[k].lon,L,R,lson);
        if(m < R && tree[k].ron)   ans += query(tree[k].ron,L,R,rson);
        return ans;
    }
}pos_tree;//区间线段树

void build(int l,int r,int rt){
    root[rt] = 0;
    if(l == r)  return ;
    int m = (l+r)>>1;
    build(lson);
    build(rson);
}

void val_insert(int a,int b,int pos,int l,int r,int rt){
    if(pos >= l && pos <= r){
        pos_tree._insert(root[rt],a,b,1,N,1);
    }
    if(l == r)   return ;
    int m = (l+r)>>1;
    if(pos <= m)    val_insert(a,b,pos,lson);
    else    val_insert(a,b,pos,rson);
}


LL check(int posa,int posb,int num,int l,int r,int rt){
    if(l == r) return l;
    int m = (l+r)>>1,ans;
    LL n1 = (root[rt*2+1] == 0)?0:pos_tree.query(root[rt*2+1],posa,posb,1,N,1);
    if(n1 < num)    ans = check(posa,posb,num-n1,lson);
    else   ans = check(posa,posb,num,rson);
    return ans;
}


int op,a,b,c;
void sov(){
    pos_tree.cnt = 0;
    for(int i = 1;  i<= Q ; i++){
        scanf("%d",&op);
        if(op == 1){
            scanf("%d%d%d",&a,&b,&c);
            if(a > b)   swap(a,b);
            val_insert(a,b,c,1,N,1);
        }
        else{
            scanf("%d%d%d",&a,&b,&c);
            if(a > b)   swap(a,b);
            printf("%d\n",check(a,b,c,1,N,1));
        }
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(~scanf("%d%d",&N,&Q)){
        build(1,N,1);
        sov();
    }
    return 0;
}
/*
7 100
1 1 5 2
1 2 7 3
1 3 5 2
1 1 1 1
2 1 3 2
2 1 3 3
2 1 3 7
2 1 7 5
2 1 7 7
2 2 3 2
2 1 1 1
2 1 1 2
2 3 5 3
2 3 4 5
2 1 5 2
2 2 7 2
2 3 5 2
2 2 2 1
*/
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/zjy2015302395/article/details/72822778

智能推荐

Hadoop 基础系列一Hadoop 系列之 1.0 和2.0 架构-程序员宅基地

文章浏览阅读449次。精选30+云产品，助力企业轻松上云！>>> Hado..._hadoop1.0和2.0项目结构

ROS基础教程学习笔记1-安装并配置ROS环境_接下来首先source一下新生成的setup.*sh文件:-程序员宅基地

文章浏览阅读270次。首先是安装ROS，我所用的ubuntu16.04，所安装的ROS是kinetic版本，安装请参考：ubuntu16.04安装ROS1.管理环境变量在前面的安装过程中，配置亮环境，此时来查看ROS环境是否配置成功：export | grep ROS植入命令之后会出现如下信息：如果没有就需要重新输入添加环境变量的命令。2.创建ROS工作空间通过创建ros工作站，也..._接下来首先source一下新生成的setup.*sh文件:

以Apollo为例学习/分析自动驾驶运动规划算法_apollo古月居-程序员宅基地

文章浏览阅读5.4k次，点赞16次，收藏171次。一、Lattice(Frenet)二、EM三、Opt(OSQP)/IPOPT汇总四、Hybrid A*/圆弧Lattice以上算法结合感知决策等框架，是否能覆盖大多数场景？L2/L4，辅助驾驶、矿区、环卫、Robotaxi、泊车、无人接驳车、农用、Robobus、物流配送、Robotruck新势力、Tier1、计算平台？工业界的仿真、量产、数据？..._apollo古月居

矩阵乘法 求斐波那契数列_矩阵乘法算波拉契法吗-程序员宅基地

文章浏览阅读731次。先简单介绍一下矩阵乘法求斐波那契数列的原理f(n) 是第n项的值。f(1)= 1; f(2) =1;f(n)= f(n-1) + （n-2)下面的介绍是我从网上查到了，收益匪浅。分两步推导： 问题的求解就变成的解决，而幂的求可用二分法来求。二分法可用递归和非递归来求：下面是代码：定义矩阵struct matrix //定义2*2的矩阵&nb_矩阵乘法算波拉契法吗

python 发送邮件报错问题解决--[SSL: WRONG_VERSION_NUMBER] wrong version number (_ssl.c:1056)_ssl.sslerror: [ssl: wrong_version_number] wrong ve-程序员宅基地

文章浏览阅读3.3w次，点赞5次，收藏10次。报错信息如下[SSL: WRONG_VERSION_NUMBER] wrong version number (_ssl.c:1056)主要是下面两种连接邮件服务器的误操作引起的（是否开启了TLS）smtplib.SMTP(self.host, self.port, timeout=300) 【TLS 禁用时使用】或smtplib.SMTP_SSL(self.host, self...._ssl.sslerror: [ssl: wrong_version_number] wrong version number (_ssl.c:1056)

移动端支付界面制作（小兔鲜项目）_html移动端好看的支付界面-程序员宅基地

文章浏览阅读1.1k次。代码.html<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>确认订单</title> <link rel="stylesheet" href="./l_html移动端好看的支付界面

随便推点

ACM论文投稿时常用的几项操作_settopmatter-程序员宅基地

文章浏览阅读2.3w次，点赞36次，收藏102次。一、我们发现ACM的latex模板中会有ACM Reference Format信息，如下：投稿时，可以使用如下的方法将其去掉，在 \documentclass[sigconf]{acmart}下面直接添加这几行即可去掉\settopmatter{printacmref=false} % Removes citation information below abstract\re..._settopmatter

ios内嵌H5滑动不流畅、白屏解决方案_ios h5 卡-程序员宅基地

文章浏览阅读2.5k次。1.最外层div加上 -webkit-overflow-scrolling属性，解决ios滑动不流畅.div {-webkit-overflow-scrolling: touch;}2.外层div里面的所有元素添加 -webkit-transform: translateZ(0px)属性，解决滑动时出现的空白（即图片不显示）.div > * {-webkit-transform:..._ios h5 卡

numpy.random.seed, torch.manual_seed使用_args.seed % 2**32-程序员宅基地

文章浏览阅读1.1k次。numpy.random.seed, torch.manual_seed使用_args.seed % 2**32

把android assets文件夹内的文件存储到sd卡中_android 将assert文件写入sd卡中-程序员宅基地

文章浏览阅读1.1k次。原文：http://mobile.51cto.com/aprogram-387591.htm/**_android 将assert文件写入sd卡中

Android---动画机制(二)---属性动画_android 属性动画 缩放代码-程序员宅基地

文章浏览阅读434次。属性动画是3.0推出的新特性,和View动画不同,他对对象进行了扩展,属性动画可以对任何对象做动画.在Animator框架中使用最多的就是AnimatorSet和ObjectAnimator配合,使用ObjectAnimator进行更精细化控制,只控制一个对象的属性值,使用多个ObjectAnimator组合到AnimatorSet中形成一个动画. 在这里说明,动画默认的时间间隔是300ms,默认_android 属性动画 缩放代码

系统日志的重要性_系统日志作用-程序员宅基地

文章浏览阅读5.5k次。系统日志的重要性　　与一个简单的算法不同，一个合格的系统不仅仅要求具有运行的高效和计算的准确，同时又必须兼顾稳定性、可靠性。其次，对于开发人员来说，又必须具有可拓展性和可维护性。各方面都必须很完善，这样的一个系统才能称得上是一个合格完美的系统。简单的站在开发人员的角度分析，比较重视的是系统的可维护性，毕竟开发人员直面的是系统的代码实现。一个代码结构冗杂、模块设计混乱、命名“异想天开”的系统对于..._系统日志作用

推荐文章

热门文章

相关标签