Input

首先行二个正整数N,代表稻草人的个数

接下去N行,第i行(1<=i<=N)包括1个由空格分隔的整数Xi和Yi,表示第i个稻草人的坐标

7)【三种音讯情势】

HINT

拥有满足要求的境地由下图所示:

 统计 1

1<=N<=2*10^5

0<=Xi<=10^9(1<=i<=N)

0<=Yi<=10^9(1<=i<=N)

Xi(1<=i<=N)互差别。

Yi(1<=i<=N)互分歧。

 

  试一试粉字会不会太意外

  正解竟然是CDQ?作者又没看出来……真TM菜。

  如同那种平面上点关系计数问题都是分治来做?很有道理啊。

  想到了分治之后照旧蛮好搞驾驭的。

  先随便把某一维分治,小编那里拿y举例。

  按y分治后,答案就分三种情况:

    1.在同一边的,显明的递归处理。

    2.不在同一边的。那么自然是左下角在下半边,右上角在上半边。

  大家只必要考虑气象2的答案计数。

  肯定是要枚举一个角。为了便利枚举右上角。

  答案受到上、下一些的范围。

  1.上半部分:

    那一个点受同在上半部分的、x,y坐标都低于它的点约束。

    若是您可以保证x有序递增,那么就只有y坐标的牢笼了。

    想转手就很明白,它只受它右边第四个这么的点(x’,y’)的范围。

    因为总括答案要过中线,你下半有些的点的y肯定小于y’的。

    所以下半部分的点x过了x’就是违规了。

    那么,找到往右边第贰个y‘小于y的点
-> 单调栈。

    只需要在上半部分维护2个y递增的干瘪栈就可以化解这几个约束。

  2.下半部分:

    下半局地的点合法,不考虑上半片段的点的界定以来,要满意如下条件:

    在它右上角没有点(横坐标在x以前)。

    既然如此,对于五个进献点(x1,y1)和(x2,y2),若(x1<y1),则一定有(y1>y2)。

    维护二个y单调递减的事物即可。

    因为它的操作唯有加点和删栈顶,所以也叫单调栈。

  最后总括答案的时候,在底下的单调栈内二分找到大于x’的点有微微个就可以了。

  CDQ传下去的时候y有序,传上来的时候x有序。

  窝的CDQ又进第三版辣辣辣辣!

  看来手写二分比lower_bound快啊。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <cstring>
#define LL long long int
#define dob double
using namespace std;

const int N = 200010;
int n,m,tot1,tot2;LL Ans;
struct Data{
  int x,y;
  bool operator <(const Data &i)const{
    return y<i.y;
  }
}scr[N],st1[N],st2[N],t[N];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

/*
CDQ按上下(y)分治。传下去时y有序,传上去时x有序。
枚举上半部分的点,求它的贡献?
1.考虑上半部分的限制
这个点受左边y坐标小于它的点约束,且只考虑往左边第一个点x'就可以了。
因为你要越中线。过了x'就是不合法。
找到左边第一个y小于它的点 -> 单调栈。
在上半部分维护一个y递增的单调栈即可。
2.考虑下半部分的限制
下半部分的点合法,它在y以内的右上角一定没有点。
画出合法曲线,发现它的y是单调递减的。
随便维护一个单调递减,找的时候二分/lower_bound一下就好。
上下要一起枚举一起加点,因为"在y以内的右上角"。
*/

inline void insert1(Data Is){//下半部分,单调递减栈
  while(tot1 && st1[tot1]<Is)tot1--;
  st1[++tot1]=Is;
}

inline void insert2(Data Is){
  while(tot2 && Is<st2[tot2])tot2--;
  st2[++tot2]=Is;
}

//二分找下半部分x比nx大的点数
inline int getl(int nx){
  int l=1,r=tot1,ans=r+1;
  while(l<=r){
    int mid=(l+r)>>1;
    if(st1[mid].x>nx)ans=mid,r=mid-1;
    else l=mid+1;
  }
  return ans;
}

inline int calc(Data Is){
  insert2(Is);
  if(tot2==1)return tot1;
  if(!tot1)return 0;
  Data Ls=st2[tot2-1];
  int l=getl(Ls.x);
  return tot1-l+1;
}

inline void CDQ(int l,int r){
  if(l==r)return;
  int mid=(l+r)>>1;
  CDQ(l,mid);CDQ(mid+1,r);
  int i=l,j=mid+1,k=l;
  tot1=0;tot2=0;
  while(i<=mid && j<=r){
    if(scr[i].x<scr[j].x){
      insert1(scr[i]);
      t[k++]=scr[i++];
    }
    else{
      Ans+=calc(scr[j]);
      t[k++]=scr[j++];
    }
  }
  while(i<=mid)t[k++]=scr[i++];
  while(j<=r){
    Ans+=calc(scr[j]);
    t[k++]=scr[j++];
  }
  for(k=l;k<=r;++k)scr[k]=t[k];
}

int main()
{
  n=gi();
  for(int i=1;i<=n;++i){
    scr[i].x=gi();scr[i].y=gi();
  }
  sort(scr+1,scr+n+1);
  CDQ(1,n);
  printf("%lld\n",Ans);
  return 0;
}

  

— Logstash:做日志解析,统一成JSON输出给Elasticsearch。

Sample Input

4
0 0
2 2
3 4
4 3

音讯队列中间件是分布式系统中保护的组件,首要消除使用耦合,异步消息,流量削锋等难点。已毕高品质,高可用,可伸缩和最终一致性架构。是巨型分布式系统不可缺失的中间件。

Description

JOI村有一片荒地,上面竖着N个稻草人,村民们每年数十次在稻草人们的四周举办祭典。

有一回,JOI村的镇长听到了稻草人们的诱导,布署在荒郊中开垦一片田地。和启迪中的一样,田地要求满意以下原则:

田地的形状是边平行于坐标轴的长方形;

左下角和右上角各有三个稻草人;

田地的其中(不包涵边界)没有稻草人。

付给各种稻草人的坐标,请你求出有稍许听从启示的地步的个数

 

4237: 稻草人

Time Limit: 40 Sec  Memory Limit: 256 MB

 

Sample Output

3

 

Output

出口一行二个正整数,代表坚守启示的情境的个数


Elasticsearch:实时日记分析服务的宗旨技术,壹个schemaless,实时的多少存储服务,通过index协会数据,兼具强大的追寻和计算成效。

举行阅读:

      — 发布订阅(Pub/sub方式)

 

2)【应用场景】

 

 

参照文档:


Kibana:基于Elasticsearch的数额可视化组件,超强的多少可视化能力是成百上千商家采纳ELK
stack的主要原由。

RabbitMQ + PHP
(一)入门与安装

 

电商系统 日志收集系统

异步处理,应用解耦,流量削锋和新闻电视发表七个场景。

 

是一种 完毕壹个实时计算体系

 

作品地址

Kafka是一种高吞吐量的分布式公布订阅音信系统,它可以处理消费者规模的网站中的全数动作流数据。
那种动作(网页浏览,搜索和其余用户的走动)是在当代互联网上的累累社会效果的贰个关键因素。
那些数据一般是出于吞吐量的渴求而因而拍卖日志和日志聚合来搞定。
对于像Hadoop的一致的日记数据和离线分析系统,但又须要实时处理的限定,这是贰个实惠的消除方案。Kafka的目标是通过Hadoop的互动加载机制来统一线上和离线的音信处理,也是为了通过集群机来提供实时的费用。

— Kafka:接收用户日志的新闻队列。

RabbitMQ + PHP
(三)案例演示

 

1.
有个别语汇和技能

3.
宽广新闻队列中间件

1)【ActiveMQ 】     ActiveMQ
是Apache出品,最风靡的,能力强大的开源音信总线,对JAVA帮衬好

1)【概述】


 

RabbitMQ + PHP
(二)AMQP拓展安装

Zookeeper 分布式服务框架是 Apache
Hadoop
的多个子项目,它非常重若是用来缓解分布式应用中时常碰到的部分数目管理难题,如:统一命名服务、状态同步服务、集群管理、分布式应用配置项的军事管制等

4)【Kafka

ELK Static(网易kafka日志处理利用案例)

 


RabbitMQ的安装

3)【信息中间件示例】

3)【ZeroMQ

 

2)【RabbitMQ

 

1)Zookeeper注册中央
Storm集群

4)【日志系统】

 

号称史上最快的音讯队列,它实在类似于Socket的一多重接口,他跟Socket的区分是:普通的socket是端到端的(1:1的关联),而ZMQ却是可以N:M
的涉嫌,人们对BSD套接字的问询较多的是点对点的总是,点对点总是须求显式地成立连接、销毁连接、采纳情商(TCP/UDP)和处理错误等,而ZMQ屏蔽了那一个细节,让您的互联网编程更为不难。ZMQ用于node与node间的通讯,node可以是主机只怕是经过。

当下在生产环境,使用较多的消息队列有ActiveMQ,RabbitMQ,ZeroMQ,Kafka,MetaMQ,RocketMQ等

 

            a)每种音讯能够有八个买主
            
b)公布者和订阅者之间有时光上的依赖性。针对有些核心(Topic)的订阅者,它必须创设二个订阅者之后,才能消费公布者的新闻。
           c)为了消费音讯,订阅者必须有限支持运维的事态。

RabbitMQ + PHP
(一)入门与安装


RabbitMQ是风靡的开源新闻队列系统,用erlang语言开发。RabbitMQ是AMQP(高级音信队列协议)的规范落实。帮衬各类客户端,如:Python、Ruby、.NET、Java、JMS、C、PHP、ActionScript、XMPP、STOMP等,帮助AJAX,持久化。用于在分布式系统中蕴藏转载消息,在易用性、增加性、高可用性等方面突显不俗

5)【Zookeeper


 

 

    – 点对点(P2P模式) :
 
          
   a)各种信息唯有三个主顾(Consumer)(即只要被消费,音信就不再在音讯队列中)
             
 b)发送者和接收者之间在岁月上从未有过借助,约等于说当发送者发送了信息之后,不管接收者有没有正值运营,它不会影响到新闻被发送到队列
              c)接收者在功成名就接收消息之后需向队列应答成功

6)【storm

  1. 核感情想

RabbitMQ + PHP
(二)AMQP拓展安装


RabbitMQ + PHP
(三)案例演示