最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球即时：Codeforces 1774 G Segment Covering 题解 (观察性质，倍增)

来源：博客园


(资料图片仅供参考)

题目链接

为什么这题是要求偶数方案数与奇数方案数的差，而不是直接求总方案数呢？这时候就应该往一个偶方案和一个奇方案抵消的方向去想。对于一个线段i，我们称它是不好的，当且仅当存在线段j使得\(x_i\le x_j\le y_j\le y_i\)，也就是它包含一个别的线段；否则称这个线段是好的。我们来观察一个单独的询问[l,r]。首先只有完全包含在(l,r)内的线段才能被选。我们先固定所有被选的不好的线段，令它们的集合为S。再固定所有没被S中任意一条线段包含的好线段中，有哪些被选。剩下还没被决定选不选的线段都是被S中至少一条线段包含的好线段，注意到这种线段至少有一条，也就是此时的奇数方案数与偶数方案数相等。因此，当有不好的线段被选进答案时，不对最终答案产生贡献。所以我们可以直接把所有的不好的线段删掉，是不影响最后答案的。这一步排个序就能做到。

接下来所有的线段就是两两不包含的了。对于一个询问[l,r]，必须存在左端点为l的线段和右端点为r的线段，否则无解。我们从完全处于[l,r]内部的线段中取出左端点最小的3个，从左到右依次称为A,B,C。其中A是必选的。发现如果C也被选且A与C有交，那B选不选都是一样的，也就是这种情况奇偶方案数相等。因此可以像上面删不好的线段一样把C也删掉(仅限此次询问)。接下来可以不断地把接下来最左的线段作为C，如果与A有交就把它删掉，直到C的左端点大于A的右端点为止。这时发现B也变成必选的了，不然中间会有一段填不上。所以可以令A=现在的B，B=现在的C，重复这个过程，直到无线段可取为止。

我们先把所有线段按左端点大小排序。对每个线段i处理出\(nxt_i\)表示完全在i右侧的最靠左的线段编号。对于一个询问[l,r]，我们拿出此区间内最靠左的两个线段，并不断地用倍增跳它们的nxt数组，直到超出[l,r]的范围为止。根据上面描述的过程，跳nxt过程中走到的位置都是必选的，而没走到的都会在上面"把C删掉"的步骤中被删掉。如果最靠左的这两个线段最终跳到的位置都不能覆盖r，或者它们跳到相同的一个线段上(这说明中间有一段没覆盖上，画个图就知道了)，那就是无解。否则可以根据跳到的线段总数判断答案是1还是-1。区间内只有1条或0条线段可取的情况要特判一下。

时间复杂度\(O(nlogn)\)。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define pb push_back#define mpr make_pairvoid 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;int n,q,nxt[200010][23];vector  v,inters;map  isl,isr;void initInters(){  vector  bds;  rep(i,v.size()) bds.pb(v[i].fi-1),bds.pb(v[i].se);  sort(bds.begin(),bds.end());bds.erase(unique(bds.begin(),bds.end()),bds.end());  rep(i,bds.size()-1) inters.pb(mpr(bds[i]+1,bds[i+1]));}int main(){  fileio();  cin>>n>>q;  int x,y;  rep(i,n)  {    scanf("%d%d",&x,&y);    v.pb(mpr(x,y));  }  sort(v.begin(),v.end(),[](pii xx,pii yy){if(xx.fi!=yy.fi) return xx.fi>yy.fi;return xx.se nv;  int curmn=2e9;  rep(i,v.size())  {    if(curmn<=v[i].se) continue;    curmn=v[i].se;nv.pb(v[i]);  }  v=nv;  sort(v.begin(),v.end());  rep(i,v.size()) isl[v[i].fi]=isr[v[i].se]=1;  initInters();  rep(i,v.size()-1)  {    int lb=i+1,ub=v.size()-1,mid;    while(lbv[i].se) ub=mid;      else lb=mid+1;    }    if(v[lb].fi<=v[i].se) lb=0;    nxt[i][0]=lb;  }  rep(i,20) rep(j,v.size())  {    if(nxt[j][i]==0) nxt[j][i+1]=0;    else nxt[j][i+1]=nxt[nxt[j][i]][i];  }  //rep(i,v.size()) cout<y)    {      puts("0");      continue;    }    if(pos+1==v.size()||v[pos+1].se>y)    {      if(v[pos].fi==x&&v[pos].se==y) puts("998244352");      else puts("0");      continue;    }    int pos2=pos+1,ans=2;    if(v[pos2].fi>v[pos].se)    {      puts("0");      continue;    }    for(int i=19;i>=0;--i) if(nxt[pos][i]>0&&v[nxt[pos][i]].se<=y) ans+=(1<=0;--i) if(nxt[pos2][i]>0&&v[nxt[pos2][i]].se<=y) ans+=(1<

关键词： 就知道了 时间复杂度