poj 2528 线段树成段更新+离散化-程序员宅基地

技术标签: struct  query  数据结构学习  

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<sstream>
#include<string>
#include<climits>
#include<stack>
#include<set>
#include<bitset>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#define iinf 2000000000
#define linf 1000000000000000000LL
#define dinf 1e200
#define eps 1e-5
#define all(v) (v).begin(),(v).end()
#define sz(x)  x.size()
#define pb push_back
#define mp make_pair
#define lng long long
#define sqr(a) ((a)*(a))
#define pii pair<int,int>
#define pll pair<lng,lng>
#define pss pair<string,string>
#define pdd pair<double,double>
#define X first
#define Y second
#define pi 3.14159265359
#define ff(i,xi,n) for(int i=xi;i<=(int)(n);++i)
#define ffd(i,xi,n) for(int i=xi;i>=(int)(n);--i)
#define ffl(i,r) for(int i=head[r];i!=-1;i=edge[i].next)
#define cc(i,j) memset(i,j,sizeof(i))
#define two(x)			((lng)1<<(x))
#define N 11111
#define M 1000000
#define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
#define Mod  n
#define Pmod(x) (x%Mod+Mod)%Mod
using namespace std;
typedef vector<int>  vi;
typedef vector<string>  vs;
typedef unsigned int uint;
typedef unsigned lng ulng;
template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;}
template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;}
template<class T> inline T Min(T x,T y){return (x>y?y:x);}
template<class T> inline T Max(T x,T y){return (x<y?y:x);}
template<class T> T gcd(T a,T  b){return (a%b)==0?b:gcd(b,a%b);}
template<class T> T lcm(T a,T b){return a*b/gcd(a,b);}
template<class T> T Abs(T a){return a>0?a:(-a);}
template<class T> inline T lowbit(T n){return (n^(n-1))&n;}
template<class T> inline int countbit(T n){return (n==0)?0:(1+countbit(n&(n-1)));}
template<class T> inline bool isPrimeNumber(T n)
{if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
struct ps
{
    int id,val;
}s[2*N];
int le[N],ri[N],clo[N<<4],n,ncase,y,cnt;
bool in[N];
bool cmp(ps p,ps q)
{
    return p.val<q.val;
}
inline void pushdown(int rt)
{
    if(clo[rt])
    {
        clo[rt<<1]=clo[rt<<1|1]=clo[rt];
        clo[rt]=0;
    }
}
void update(int L,int R,int color,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        clo[rt]=color;
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(rt);
    if(L<=mid)  update(L,R,color,lson);
    if(R>mid) update(L,R,color,rson);
}
void query(int l,int r,int rt)
{
    if(clo[rt])
    {
        if(!in[clo[rt]])
        in[clo[rt]]=1,cnt++;
        return ;
    }
    int mid=(l+r)>>1;
    if (l==r) return ;
    query(lson);
    query(rson);
}
int main()
{
   scanf("%d",&ncase);
   while(ncase--)
   {
       scanf("%d",&n);
       y=0;
       ff(i,1,n)
       {
           scanf("%d",&s[i*2-1].val);
           s[i*2-1].id=i;
           scanf("%d",&s[i*2].val);
           s[i*2].id=i;
       }
       sort(s+1,s+2*n+1,cmp);
       s[0].val=-iinf;
       cc(le,0);
       ff(i,1,2*n)
       {
           if(s[i].val==s[i-1].val)
           {
               if(le[s[i].id])
               ri[s[i].id]=y;
               else
               le[s[i].id]=y;
           }
           else
           if(i>=2&&s[i].val>s[i-1].val+1)
           {
               y+=2;
                if(le[s[i].id])
               ri[s[i].id]=y;
               else
               le[s[i].id]=y;
           }
           else
           { y+=1;
                if(le[s[i].id])
               ri[s[i].id]=y;
               else
               le[s[i].id]=y;
           }
       }
       cc(clo,0);
       cc(in,0);
       cnt=0;
       ff(i,1,n)
       update(le[i],ri[i],i,1,y,1);
       query(1,y,1);
       printf("%d\n",cnt);
   }
    return 0;
}

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

智能推荐

CentOS7修改时区的正确方式-跟老韩学Linux运维系列_老韩Linux DevOps的博客-程序员宅基地

CentOS7操作系统修改时区的正确方式1、查看当前系统时间[root@laohan-docker-demo01 shell]# dateThu Apr 29 08:38:36 EDT 2021[root@laohan-docker-demo01 shell]# date -RThu, 29 Apr 2021 08:39:14 -0400[root@laohan-docker-demo01 shell]# 2、查看当前时区设置[root@laohan-docker-demo01 shell

flume启动失败:org.apache.flume.ChannelException: Put queue for MemoryTransaction of capacity 10000 full-程序员宅基地

flume.conf配置报错日志信息:跪求大神解决!_org.apache.flume.channelexception: put queue for memorytransaction of capaci

微信小程序封装wx.request方法-程序员宅基地

wx.request 是一个异步的方法success回调函数的作用域发生了改变,所以this的指向不是当前函数两种方法可以改变this的指向:一种通过中间变量that。另一种通过ES6箭头函数改变this作用域使用 promise,promise可以解决异步嵌套的问题,简单的异步请求可以不使用promisepromise.then((res)=>{c..._wx.request是方法吗

示波器你用对了吗?很多人不知道的概念-程序员宅基地

测量一个沿率为4ns的波形,选择可以测量1ns波形不失真的示波器去测量更保险些,那如何选择示波器,以及示波器本身是可以测量的,那你该如何设置,才能保证采集的波形不失真?在设计中查看信号的..._us/div

ceph 查找 rbd image 存储位置_ceph rbdimage osd-程序员宅基地

环境:centos7.6, ceph luminiousceph 同时提供对象存储、块存储、文件存储三种接口,但本质上都是对象存储,也就是说一个rbd image 实际上包含了多个对象(默认情况下是 iamge_size/4M)查看 pg 对应的 osdceph pg dumpceph pg map 3.5d查看 pool 中的 image[root@ansible002 ~]# rbd list k8skubernetes-dynamic-pvc-0f4455a2-f96a-11e9-9_ceph rbdimage osd

Verilog HDL作业1_1-程序员宅基地

Verilog HDL作业1目录Verilog HDL作业1目录作业要求Quartus RTL电路图仿真波形代码块作业要求信号定义: 信号名称 方向 位宽 说明 CLK 输入 1 输入时钟信号 RST 输入 1 输入复位清零信号,异步高电平有效 CNT 输出 3 输出计数值信号计数器特征: 该计数器特征为,从0计数到5,然后又

随便推点

AWS的RDS开启慢查询日志到cloudwatch中_aws cloudwatch querytime-程序员宅基地

在AWS的RDS中开启慢查询并能够直接在提控制台提供的Cloudwatch里查询的到信息需要满足以下几点:slow_query_log:要创建慢速查询日志,请设置为 1。默认值为 0general_log:要创建常规日志,请设置为 1。默认值为 0。long_query_time:要防止在慢速查询日志中记录快速运行的查询,请指定需要记录的最短查询运行时间值,以秒为单位。默认值为 10 秒;最小值为 0。如果 log_output = FILE,则可以指定精确到微秒的浮点值。如果 log_out._aws cloudwatch querytime

java中RandomAccessFile随机文件读写,文件追加和部分读取-程序员宅基地

全栈工程师开发手册 (作者:栾鹏) java教程全解RandomAccessFile是Java中输入,输出流体系中功能最丰富的文件内容访问类,它提供很多方法来操作文件,包括读写支持,与普通的IO流相比,它最大的特别之处就是支持任意访问的方式,程序可以直接跳到任意地方来读写数据。如果我们只希望访问文件的部分内容,而不是把文件从头读到尾,使用RandomAccessFile将会带来更简洁的

java.lang.ClassNotFoundException: antlr.Recognition.Exception的解决方案-程序员宅基地

错误:原因是少了下面这个包:antlr-2.7.6.jar注意:antlr-2.7.2.jar和antlr-2.7.6.jar的区别:antlr-2.7.2.jar:是struts的包antlr-2.7.6.jar:是hibernate用来做HQL查询用的包。转载于:https://www.cnblogs.com/zgrlbq/p/3402252.htm..._java antlr/recognitionexception

java代码修改linux环境中文件的权限_java liunx环境修改文件权限-程序员宅基地

记录一段代码,java代码修改linux环境中文件的权限package com.baxixiaomi.study.leetcode.test01;import org.apache.log4j.Logger;import java.io.File;import java.io.IOException;import java.nio.file.Files;import java.ni..._java liunx环境修改文件权限

java调整导出xls列顺序_EasyExcel根据筛选列导出(中间不空列,顺序可调整)-程序员宅基地

使用EasyExel根据筛选列导出的方式在官方文档就有一个“根据参数只导出指定列”的例子,但这个例子我测了一下导出来的Excel是这样的。 “名字”和“生日”中间这里却空出来了一列,但如果按前端显示了哪些字段才需要进行导出,而且顺序也要按前端展示的一样(前端实现了拖拽还有筛选指定显示哪些字段,因此导出的格式也要一致...),这个官方文档给出的例子似乎不太满足,于是我写了一个利用不创建对象+反射的方..._easyexcel 顺序

再见,HttpClient!再见,Okhttp!_程序员闪充宝的博客-程序员宅基地

作者:元人部落来源:www.cnblogs.com/bryan31/p/13359376.html1.背景 因为业务关系,要和许多不同第三方公司进行对接。这些服务商都提供基于http的ap..._forest和okhttp