首页 > 其他分享 >Codeforces 983 D Arkady and Rectangles 题解

Codeforces 983 D Arkady and Rectangles 题解

时间:2022-12-25 22:00:27浏览次数:65  
标签:Arkady end dscx dscy int 题解 begin 983 mx

题目链接

挺有意思的数据结构题,题面看着像个板子,其实还是有不少学问的。

平面上一堆矩形的题目常见套路就是对\(x\)轴扫描线,\(y\)轴线段树维护,这题也不例外。我们先对坐标离散化。题目中输入的是坐标系中的顶点的坐标,为了方便维护,我们需要转换成"格子"的坐标。注意,是先离散化再转换,如果先转换再离散化会出现下面的错误:

然后从左到右扫描线,对于每一列,我们想找出这一列中所有最后仍存在、且没有被标记过的颜色,把它们计入答案,并把这些颜色都做上标记,以后不再统计。那么我们需要同时维护两堆东西:当前存在的所有颜色和当前存在的所有没标记过的颜色。一个没标记过的颜色应该被统计,当且仅当当前列存在一个位置被这个颜色覆盖,且覆盖这个位置的所有颜色中没有编号比这个颜色大的。假设现在往扫描线中加入一个颜色,它覆盖的纵坐标区间是[l,r]。我们平时做线段树区间修改[l,r]的时候会访问\(logn\)个不相交的区间,且它们的并为[l,r]。这题里我们对线段树上的每个区间维护一个set(f集合),加入一个覆盖[l,r]的颜色时就把这个颜色加入所有访问到的\(logn\)个区间的set里。再对每个区间维护一个set表示所有没标记的颜色(g集合),加入元素的时候和上一个set一样,如果标记了一个颜色就把这个set中的对应颜色都删了就行。

对于线段树上的某一个节点k,它的\(g\)集合里只有最大的一个元素可能计入答案。设这个元素为x,它能计入答案的充要条件是:从k到线段树根的所有节点的f集合的所有元素都\(\le x\);且\(k\)子树中存在一个叶子\(p\)使得从\(p\)到\(k\)路径上所有节点的f集合中的所有元素都\(\le x\)。

然后对线段树中的每个点k维护\(mx_k\)表示它的子树中到现在为止满足上面说的所有条件的最大的可能被计入答案的值(在往上pushup的时候还要经受上方节点f集合中元素的考验);\(mnlim_k\)表示子树中最优的叶子\(p\)(也就是p到k的路径上所有点f集合元素的最大值最小)。如果搞清楚了以上定义,如何pushup已经显然了。具体见代码。

时间复杂度\(O(nlog^2n)\)。

点击查看代码
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define x1 x114
#define y1 y114
#define x2 x514
#define y2 y514

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

void chmax(int &x,int y){if(x<y) x=y;}

int n,x1[100010],y1[100010],x2[100010],y2[100010];
vector <pair <pii,pii> > op[200010];
vector <int> dscx,dscy;

namespace st
{
  int n2=1,mx[800010],mnlim[800010];
  set <int> all[800010],cand[800010];
  void pushUp(int k,bool isLeaf)
  {
    if(isLeaf)
    {
      if(cand[k].empty()) mx[k]=-1;
      else mx[k]=(*cand[k].rbegin()==*all[k].rbegin() ? *cand[k].rbegin():-1);
      if(all[k].empty()) mnlim[k]=-1;else mnlim[k]=*all[k].rbegin();
    }
    else
    {
      int curlim=(all[k].empty() ? -1:*all[k].rbegin());
      mnlim[k]=min(mnlim[k+k+1],mnlim[k+k+2]);chmax(mnlim[k],curlim);
      mx[k]=-1;
      if(mx[k+k+1]>=curlim) chmax(mx[k],mx[k+k+1]);if(mx[k+k+2]>=curlim) chmax(mx[k],mx[k+k+2]);
      if(!cand[k].empty()&&*cand[k].rbegin()>=mnlim[k]) chmax(mx[k],*cand[k].rbegin());
    }
  }
  void upd(int k,int lb,int ub,int tlb,int tub,int w,int val)
  {
    if(ub<tlb||tub<lb) return;
    if(tlb<=lb&&ub<=tub)
    {
      if(w==1) all[k].insert(val),cand[k].insert(val);
      else
      {
        all[k].erase(val);
        if(cand[k].find(val)!=cand[k].end()) cand[k].erase(val);
      }
      pushUp(k,lb==ub);
      return;
    }
    upd(k+k+1,lb,(lb+ub)/2,tlb,tub,w,val);upd(k+k+2,(lb+ub)/2+1,ub,tlb,tub,w,val);
    pushUp(k,0);
  }
  void del(int k,int lb,int ub,int tlb,int tub,int val)
  {
    if(ub<tlb||tub<lb) return;
    if(tlb<=lb&&ub<=tub)
    {
      if(cand[k].find(val)!=cand[k].end()) cand[k].erase(val);
      pushUp(k,lb==ub);
      return;
    }
    del(k+k+1,lb,(lb+ub)/2,tlb,tub,val);del(k+k+2,(lb+ub)/2+1,ub,tlb,tub,val);
    pushUp(k,0);
  }
}

int main()
{
  fileio();

  cin>>n;
  rep(i,n)
  {
    scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
    dscx.pb(x1[i]);dscx.pb(x2[i]);dscy.pb(y1[i]);dscy.pb(y2[i]);
  }
  sort(dscx.begin(),dscx.end());dscx.erase(unique(dscx.begin(),dscx.end()),dscx.end());
  sort(dscy.begin(),dscy.end());dscy.erase(unique(dscy.begin(),dscy.end()),dscy.end());
  rep(i,n)
  {
    x1[i]=lower_bound(dscx.begin(),dscx.end(),x1[i])-dscx.begin();x2[i]=lower_bound(dscx.begin(),dscx.end(),x2[i])-dscx.begin();
    y1[i]=lower_bound(dscy.begin(),dscy.end(),y1[i])-dscy.begin();y2[i]=lower_bound(dscy.begin(),dscy.end(),y2[i])-dscy.begin();
    --x2[i];--y2[i];
    op[x1[i]].pb(mpr(mpr(y1[i],y2[i]),mpr(1,i)));
    op[x2[i]+1].pb(mpr(mpr(y1[i],y2[i]),mpr(-1,i)));
  }

  while(st::n2<dscy.size()) st::n2*=2;
  rep(i,st::n2*2+3) st::mx[i]=st::mnlim[i]=-1;
  int ans=1;
  rep(i,dscx.size())
  {
    rep(j,op[i].size()) st::upd(0,0,st::n2-1,op[i][j].fi.fi,op[i][j].fi.se,op[i][j].se.fi,op[i][j].se.se);
    while(st::mx[0]>-1)
    {
      ++ans;
      int val=st::mx[0];
      st::del(0,0,st::n2-1,y1[val],y2[val],val);
    }
  }
  cout<<ans<<endl;

  termin();
}

标签:Arkady,end,dscx,dscy,int,题解,begin,983,mx
From: https://www.cnblogs.com/legendstane/p/codeforces-983-d-Arkady-and-Rectangles-solution.html

相关文章

  • CF732D Exams 题解
    题目链接题目分析:首先可以发现,如果当前第\(i\)天可以完成所有考试,那么第\(i+1\)天一定也可以。因此,答案具有单调性。考虑二分,将原问题转换为判定性问题。判定是否......
  • AT_jag2018summer_day2_a 10^N+7 题解
    题目传送门题目大意有三个非负整数$x,y,z$,找到符合以下条件的最小非负整数\(n\);$n\{\rm\mod}\10^1+7\=\x$$n\{\rm\mod}\10^2+7\=\y$$n\{\rm\mo......
  • CF864C Bus 题解
    题目传送门题目大意一辆汽车从\(0\)到\(a\)往返\(k\div2\)次(也就是去算一次,回算一次);原来有\(b\)升油,每行驶一单位距离消耗一升油,在\(f\)有加油站(可以加满油......
  • UVA13197 Cuberoot This 题解
    题目传送门题目大意求满足\(x^3\bmodp=a\)且\(x<p\)的数\(x\),升序输出。解题思路在\(0\)到\(p-1\)的范围内,查找满足条件的\(x\);值得注意的是,输出要留意:最......
  • AT_joi2022_yo1a_d 箱と鍵 (Boxes and Keys) 题解
    题目传送门题目大意给定一个长度为\(n\)的数组\(a\)和一个长度为\(m\)的数组\(b\),求\(a\)中有多少个数在\(b\)中出现过。解题思路数据比较小,可以直接暴力:......
  • CF1735A Working Week 题解
    题目传送门题目大意一周有\(n\)天,有三天休息日,其中第\(n\)天一定休息。现需要安排剩下的两个休息日,要求:不能使得休息日相邻。这两个休息日将\(n-1\)天分成三......
  • AT_mujin_pc_2018_b セキュリティ 题解
    题目传送门题目大意房间原有\(A\)人,+表示进来一个人,-表示出去一个人;求是否有一个时间,房间内的人数为\(0\)。解题思路按题意进行模拟:首先判断\(A\)是否等于零,......
  • AT_pakencamp_2021_day2_c Participants 3 题解
    题目传送门题目大意找出没有参加第\(1\)天的比赛,但是参加了第\(2\)天的比赛人的ID。解题思路从第一次比赛人员的ID中,查找是不是没有有第二次比赛人员的ID。如......
  • UVA694 The Collatz Sequence 题解
    题目传送门题目大意根据题目中的规定生成序列,问有多少次计算;注意输入以“\(\-1\)\(\-1\)”结尾。解题思路按照题目中所说的进行模拟。在保证\(a\)不大于\(l\)......
  • CF317A Perfect Pair 题解
    题目传送门题目大意给定一对数\(x\)和\(y\),允许把其中的一个数换成\(x+y\),问把\(x\)或\(y\)变成大于或等于\(m\)的数,需要几次操作。解题思路首先可以判断......