把一个人看成二维平面上的一个点,把一个K[i]看成左上角为(0,+max),右下角为(K[i],K[i])的一个矩阵,那么可以很好地描述人对于询问是否合法(我也不知道他怎么想到这东西的)

然后把一组询问排序,按照K[i]从小到大依次处理,定义一个取点的方式为尽量取纵坐标小的点,那么可以构造出一种方案使得对于每一块区域不能取的点的最大纵坐标递减

(我也不知道他怎么想到这东西的)

单调栈维护每一块被取过的点的最大纵坐标,那么随着K[i]的增大,区域会被合并

二维平面数点,主席树

#include<cstdio>
#include<algorithm>
using namespace std;
int N,n,cnt,tree[10000005],sz[200005],h[200005],stack[200005],K[200005],root[500005],ls[10000005],rs[10000005];
struct node{
int x,y;
}e[1000005];
bool cmp(node a,node b){
return a.x<b.x;
}
void insert(int pre,int &now,int l,int r,int ID){
now=++cnt;
tree[now]=tree[pre]+1;
ls[now]=ls[pre];
rs[now]=rs[pre];
if (l==r) return;
int mid=(l+r)>>1;
if (ID<=mid) insert(ls[pre],ls[now],l,mid,ID);
else insert(rs[pre],rs[now],mid+1,r,ID);
}
int query_K(int pre,int now,int l,int r,int K){
if (l==r) return l;
int mid=(l+r)>>1;
int ANS=tree[rs[now]]-tree[rs[pre]];
if (ANS>=K) return query_K(rs[pre],rs[now],mid+1,r,K);
else return query_K(ls[pre],ls[now],l,mid,K-ANS);
}
int query(int pre,int now,int l,int r,int K){
if (!now) return 0;
if (l==r) return tree[now]-tree[pre];
int mid=(l+r)>>1;
if (K<=mid) return tree[rs[now]]-tree[rs[pre]]+query(ls[pre],ls[now],l,mid,K);
else return query(rs[pre],rs[now],mid+1,r,K);
}
int main(){
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%d%d",&e[i].x,&e[i].y);
sort(e+1,e+n+1,cmp);
N=n+1;
int head=1;
for (int i=1; i<=N; i++){
root[i]=root[i-1];
while (head<=n && e[head].x==i) insert(root[i],root[i],1,N,e[head++].y);
}
int q;
scanf("%d",&q);
while (q--){
int m;
scanf("%d",&m);
for (int i=1; i<=m; i++) scanf("%d",&K[i]);
sort(K+1,K+m+1);
int top=0;
for (int i=1; i<=m; i++){
while (top && h[top]<K[i]) top--;
int Sz=sz[top];
Sz+=query(root[K[stack[top]]],root[K[i]],1,N,K[i])-K[i];
if (Sz<0){
printf("0\n");
break;
}
else if (i==m){
printf("1\n");
break;
}
int H=query_K(root[K[stack[top]]],root[K[i]],1,N,Sz-sz[top]);
while (H>h[top] && top){
top--;
H=query_K(root[K[stack[top]]],root[K[i]],1,N,Sz-sz[top]);
}
stack[++top]=i;
sz[top]=Sz;
h[top]=H;
}
}
return 0;
}

  

最新文章

  1. 使用vlc进行二次开发做自己的播放器
  2. C/C++学习链接
  3. jquery用append添加按钮之后,按钮监听无法使用的解决方法
  4. 如何让Android字体自适应屏幕分辨率
  5. memcached全面剖析–3. memcached的删除机制和发展方向
  6. Android Service与Activity之间通信的几种方式
  7. JSON对象与JSON数组的长度和遍历方法
  8. 关于Redis的一些常识
  9. [Kafka] - Kafka基本概念介绍
  10. 2020: [Usaco2010 Jan]Buying Feed, II
  11. HTTP架构介绍(1) Web服务器和代理服务器
  12. java基础常见面试题,这是一篇超长的随笔!!!
  13. 神经网络MPLClassifier分类
  14. VMware卸载有残留,再安装时报错提示MSI Failed
  15. Mac安装6.1.2版本Elasticsearch及优化配置实践
  16. Eclipse支持文件UTF-8编码
  17. Configuration Error: deployment source &#39;SocietyManage:war exploded&#39; is not valid
  18. spring学习总结(一)_Ioc基础(中)
  19. Content-type详解
  20. learning scala ide tools install

热门文章

  1. c# 视频播放
  2. sql 2008 中不能创建数据库关系图
  3. C# 报表和打印等
  4. RK3288开发过程中遇到的问题点和解决方法之Kernel
  5. Json字符串与js数组互相转换
  6. Zero to One书摘
  7. Html.Action Html.RenderAction Html.Partial Html.RenderPartial Url.Action Html.ActionLink 大括号和小括号区别
  8. [论文理解] CornerNet: Detecting Objects as Paired Keypoints
  9. opencv中mat矩阵如何debug
  10. python_85_sys模块