APIO2018 新家

Wesley13
• 阅读 366

[TOC]

###APIO2018 新家 题目传送门

###题意 五福街是一条笔直的道路,这条道路可以看成一个数轴,街上每个建筑物的坐标都可以用一个整数来表示。小明是一位时光旅行者,他知道在这条街上,在过去现在和未来共有 $n$ 个商店出现。第 $i$ 个商店可以使用四个整数 $x_i$, $t_i$, $a_i$, $b_i$描述,它们分别表示:商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行,选择一个合适的时间,住在五福街上的某个地方。他给出了一份他可能选择的列表,上面包括了 $q$ 个询问,每个询问用二元组(坐标,时间)表示。第 $i$ 对二元组用两个整数 $l_i$, $y_i$描述,分别表示选择的地点 $l_i$和年份$y_i$ 。

现在,他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为:在居住的年份,离居住点最远的商店类型到居住点的距离。类型 $t$ 的商店到居住点的距离定义为:在指定的年份,类型 $t$ 的所有营业的商店中,到居住点距离最近的一家到居住点的距离。我们说编号为 $i$ 的商店在第 $y$ 年在营业当且仅当 $a_i \leq y \leq b_i$。注意,在某些年份中,可能在五福街上并非所有 $k$ 种类型的商店都有至少一家在营业。在这种情况下,不方便指数定义为−1。你的任务是帮助小明求出每对(坐标,时间)二元组居住的不方便指数。 $(1 \leq n,q \leq 3*10^5 , 1 \leq x_i,a_i,b_i \leq 10^9 , 1 \leq t_i \leq k , a_i \leq b_i , 1 \leq l_i,y_i \leq 10^8)$

###题解 首先很容易想到的是我们可以把一个商店在时间$[l,r]$营业改为在时间$l$处插入和在时间$r$处删除。这样我们就有了一个大致的算法:将所有的操作按照时间排序,然后顺序地按照时间进行插入,并用某种数据结构动态维护贡献,最后对于每组询问输出答案。 然后我们考虑如何去维护这个贡献。首先无解的情况是比较好判的,我们就可以直接略过了。然后我们考虑这个答案的计算方法,实际上就是找一段最短的长度$ans$,使得$[x-ans,x+ans]$这段区间中涵盖了所有的商店,这个显然是可以二分答案来解决的。于是问题就转化成为了二分答案之后查询区间不同的数字是否等于$k$。然后继续转化问题,我们记录每一个商店的前驱(即这一种商店上一次出现的位置)如果一种商店在区间$[l,r]$中出现了,并且这种商店也在$[r+1,inf]$中出现了,那么这种商店在$[r+1,inf]$这段区间中,每一个数的前驱必定$\geq l$,如果在$[l,r]$中没有出现过,那么在$[r+1,inf]$区间里面,前驱的最小值一定$\leq l$。知道了这个,我们相当于吧问题转化成为了区间询问前驱的最小值。这样实际上我们就已经可以做掉这道题目了,开一个$set$维护每一个商店的前驱(为了方便,在0和inf的两个位置都插入所有种类的商店),然后开一个线段树维护前驱的最小值,每次二分答案之后在线段树上$Check$,总共的复杂度为$O(nlog^2(n))$。 然后实际上这题还可以继续优化,我们会发现我们在计算答案的时候,即用到了二分,又用到了线段树。然而实际上,线段树和二分往往是可以并在一起的(雾,然后我们就可以在线段树上直接进行二分。原本二分的时候,我们如果即$[i,inf]$这段区间的前驱最小值为$Mn$,相当于是在找一个最大的位置$i$,满足$Mn+i \leq 2*x$,所以我们直接在线段树上二分即可,方法是这样的: 假设当前区间为$[l,r]$

  • 如果$x$在$[mid+1,r]$的范围内,那么说明$i$也一定在$[mid+1,r]$范围内,直接递归右子树即可。
  • 如果$x$在$[l,mid]$的范围内,那么$i$在左右两个区间都有可能存在,然后判断当前的$mid+1$是否满足$Mn+i \leq 2*x$的条件,如果满足则往右子树递归,否则往左子树递归。 这样做的复杂度就是$O(nlog(n))$的了。

###Code:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+500;
const int Inf=1e9+7;
int n,nq,tot,c,sptot,k;
int srt[N<<2],cnt[N<<1];
multiset<int>S[N<<1];
typedef multiset<int>::iterator Sit;
struct Opt {
  int opt;
  int x,t,tp,idx,ans;
  bool operator < (const Opt &rhs) const {
    return t==rhs.t?opt<rhs.opt:t<rhs.t;
  }
}p[N<<2];
bool Cmp(Opt a,Opt b) {
  return a.idx<b.idx;
}

struct Set {
  priority_queue<int,vector<int>,greater<int> >Q,Del;
  int Top() {
    while(!Del.empty()&&Q.top()==Del.top()) {
      Q.pop();Del.pop();
    }
    return Q.empty()?c+1:Q.top();
  }
}q[N<<1];

namespace Seg {
  int Mn[N<<4],pos[N<<4];
#define ls(o) o<<1
#define rs(o) o<<1|1
  void Build(int o,int l,int r) {
    Mn[o]=Inf;
    if(l==r) {
      pos[o]=srt[l];
      return ;
    }
    int mid=(l+r)>>1;
    Build(ls(o),l,mid);Build(rs(o),mid+1,r);
    pos[o]=pos[ls(o)];
  }
  void Modify(int o,int l,int r,int ps,int v) {
    if(l==r) {
      Mn[o]=srt[v];
      return ;
    }
    int mid=(l+r)>>1;
    if(ps<=mid) Modify(ls(o),l,mid,ps,v);
    else Modify(rs(o),mid+1,r,ps,v);
    Mn[o]=min(Mn[ls(o)],Mn[rs(o)]);
    return ;
  }
  int Query(int o,int l,int r,int ps) {
    if(l==r) return Mn[o];
    int mid=(l+r)>>1;
    if(ps>mid) return Query(rs(o),mid+1,r,ps);
    else return min(Mn[rs(o)],Query(ls(o),l,mid,ps));
  }
  int Ask(int ps) {
    ps=srt[ps];
    int l=0,r=c+1;
    int o=1;
    while(l<r) {
      int mid=(l+r)>>1;
      if(ps>=pos[rs(o)]) o=rs(o),l=mid+1;
      else {
        if(pos[rs(o)]+Mn[rs(o)]+1<=2*ps) o=rs(o),l=mid+1;
        else o=ls(o),r=mid;
      }
    }
    int Min=Query(1,0,c+1,l+1);
    int ret=max(srt[l],2*ps-Min);
    return ret-ps;
  }
}

void Init() {
  c=0;
  for(int i=1;i<=tot;i++) {
    srt[++c]=p[i].x;
  }
  sort(srt+1,srt+1+c);
  c=unique(srt+1,srt+1+c)-srt-1;
  srt[0]=-Inf,srt[c+1]=Inf;
  for(int i=1;i<=tot;i++) {
    p[i].x=lower_bound(srt+1,srt+1+c,p[i].x)-srt;
  }
  sort(p+1,p+1+tot);
  for(int i=1;i<=k;i++) {
    S[i].insert(0);
    S[i].insert(c+1);
    q[c+1].Q.push(0);
  }
  Seg::Build(1,0,c+1);
  Seg::Modify(1,0,c+1,c+1,0);
}

void Insert(int ps,int tp) {
  cnt[tp]++;sptot+=cnt[tp]==1;
  Sit it=S[tp].insert(ps);
  Sit nw=it;it--;
  q[ps].Q.push(*it);
  Seg::Modify(1,0,c+1,ps,q[ps].Top());
  q[*(++nw)].Del.push(*it);
  q[*(nw)].Q.push(ps);
  Seg::Modify(1,0,c+1,*(nw),q[*nw].Top());
  return ;
}

void Delete(int ps,int tp) {
  cnt[tp]--;sptot-=cnt[tp]==0;
  Sit it=S[tp].find(ps);
  Sit tmp=it,nw=it;it--;
  q[ps].Del.push(*it);
  Seg::Modify(1,0,c+1,ps,q[ps].Top());
  q[*(++nw)].Del.push(*tmp);
  q[*nw].Q.push(*it);
  Seg::Modify(1,0,c+1,*(nw),q[*nw].Top());
  S[tp].erase(tmp);
}

int main() {
  scanf("%d%d%d",&n,&k,&nq);
  for(int i=1,x,t,a,b;i<=n;i++) {
    scanf("%d%d%d%d",&x,&t,&a,&b);
    p[++tot].opt=-1;p[tot].x=x;p[tot].tp=t;p[tot].t=a;p[tot].idx=Inf;
    p[++tot].opt=1;p[tot].x=x;p[tot].tp=t;p[tot].t=b;p[tot].idx=Inf;
  }
  for(int i=1,l,y;i<=nq;i++) {
    scanf("%d%d",&l,&y);
    p[++tot].opt=0;p[tot].x=l;p[tot].t=y;p[tot].idx=i;
  }
  Init();
  for(int i=1;i<=tot;i++) {
    if(p[i].opt==-1) Insert(p[i].x,p[i].tp);
    else if(p[i].opt==0) {
      if(sptot!=k) p[i].ans=-1;
      else p[i].ans=Seg::Ask(p[i].x);
    }
    else Delete(p[i].x,p[i].tp);
  }
  sort(p+1,p+1+tot,Cmp);
  for(int i=1;i<=nq;i++) {
    printf("%d\n",p[i].ans);
  }
  return 0;
}
点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
2年前
hdu2204 Eddy's爱好
原题:点击打开链接(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Facm.hdu.edu.cn%2Fshowproblem.php%3Fpid%3D2204)题意很明确了,即:给你一个正整数N,确定在1到N之间有多少个可以表示成M^K(K1)的数。本题目为容斥原
Stella981 Stella981
2年前
Codeforces 862B (二分图染色)
<题目链接(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fvjudge.net%2Fproblem%2FCodeForces862B)\题目大意:给出一个有n个点的二分图和n1条边,问现在最多可以添加多少条边使得这个图中不存在自环,重边,并且此图还是一个二
Stella981 Stella981
2年前
LeetCode 5073. 进击的骑士(Java)BFS
题目:5073\.进击的骑士(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcodecn.com%2Fcontest%2Fbiweeklycontest9%2Fproblems%2Fminimumknightmoves%2F)一个坐标可以从i
Stella981 Stella981
2年前
Search Insert Position
\toc\题目链接SearchInsertPositionLeetCode(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcode.com%2Fproblems%2Fsearchinsertposition%2F)注意点
Wesley13 Wesley13
2年前
UOJ#351. 新年的叶子 概率期望
原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ351.html题目传送门UOJ351(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fuoj.ac%2Fproblem%2F351)
Stella981 Stella981
2年前
Comet OJ
题意https://www.cometoj.com/contest/52/problem/C?problem\_id2416(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.cometoj.com%2Fcontest%2F52%2Fproblem%2FC%3Fprob
Stella981 Stella981
2年前
Codeforces Round #565 (Div. 3) C. Lose it!
链接:https://codeforces.com/contest/1176/problem/C(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fcodeforces.com%2Fcontest%2F1176%2Fproblem%2FC)题意:Youare
Stella981 Stella981
2年前
POJ 1195 Mobile phones(二维树状数组)
题目链接:http://poj.org/problem?id1195(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fpoj.org%2Fproblem%3Fid%3D1195)题意是有四种操作。当n0时:输入一个m表示初始化矩阵(m\m且值都为0)。
Stella981 Stella981
2年前
LOJ6500. 「雅礼集训 2018 Day2」操作(哈希+差分)
题目链接https://loj.ac/problem/6500(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Floj.ac%2Fproblem%2F6500)题解区间取反$01$串的经典套路是差分。我们令$b\_ia\_i\\{\\rmxor
Stella981 Stella981
2年前
85D Sum of Medians
传送门(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fcontest%2F85%2Fproblem%2FD)题目Inonewellknownalgorithmoffindingthe_k_\thorderst