codeforces 1190D-Tokitsukaze and Strange Rectangle

灰太狼 2023-06-05 12:43 76阅读 0赞

传送门:QAQQAQ

题意:给你在坐标轴上的N个点,问你用一条横线和两条竖线所划分出的不同点集的个数(不包括空集)

1605368-20190805231602920-984257673.png

思路:在没想清楚的时候觉得这是一道水题:对于y轴排序,然后从下往上扫看上方x不同的个数s,ans+=(s+1)*s/2即可,但后来发现这样会重复考虑一些集合,即在当前点时这几个点关于x轴排序是连续的,删掉这个点后仍是连续的,所以我们在对于y轴扫描时要减去这些重复的集合

即我们对于Y轴排序,从上至下扫描,对于当前新加入的一层y,先加上(s+1)*s/2,再对于每一个x值寻找它们之间的空隙中原本存在了多少x,减去这些重复的集合tmp*(tmp+1)/2即可

在代码实现方面,我们用线段树维护x值l,r区间内现存在多少点,每当一层扫完,把原先不存在的x值update成1,若x存在就不要管它,注意sum维护的是当前不同的x轴的个数,而不是总点数

在更新答案方面,对于同一层的两个x之间query一下原有不同x值个数,减一下tmp*(tmp+1)/2即可,注意开头和结尾都要扫,而且线段树开到xn+1是为了防止越界

因为x,y<=1e9无法直接用线段树维护这么大一段区间,而n<=2e5,所以我们用常用技巧离散化一下即可

代码:(听说树状数组维护更方便,但我喜欢线段树啊……)

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll N=200005;
  5. const ll inf=2000000000;
  6. struct node{
  7. ll x,y;
  8. bool operator < (const node rhs) const{
  9. if(y==rhs.y) return x<rhs.x;
  10. return y>rhs.y;
  11. }
  12. }a[N];
  13. ll n,x[N],y[N],mx=-inf,vis[N];
  14. struct TREE{
  15. ll sum;
  16. }tree[N*4];
  17. void push_up(TREE &fa,TREE ls,TREE rs)
  18. {
  19. fa.sum=ls.sum+rs.sum;
  20. }
  21. void build(ll x,ll l,ll r)
  22. {
  23. if(l==r)
  24. {
  25. tree[x].sum=0;
  26. return;
  27. }
  28. ll mid=(l+r)>>1;
  29. build(x+x,l,mid);
  30. build(x+x+1,mid+1,r);
  31. push_up(tree[x],tree[x+x],tree[x+x+1]);
  32. }
  33. void update(ll x,ll l,ll r,ll pos)
  34. {
  35. if(l==r)
  36. {
  37. tree[x].sum=1;
  38. return;
  39. }
  40. ll mid=(l+r)>>1;
  41. if(pos>mid) update(x+x+1,mid+1,r,pos);
  42. if(pos<=mid) update(x+x,l,mid,pos);
  43. push_up(tree[x],tree[x+x],tree[x+x+1]);
  44. }
  45. ll query(ll x,ll l,ll r,ll L,ll R)
  46. {
  47. if(L>R) return 0;
  48. if(L<=l&&r<=R) return tree[x].sum;
  49. ll mid=(l+r)>>1;
  50. if(mid>=R) return query(x+x,l,mid,L,R);
  51. if(mid<L) return query(x+x+1,mid+1,r,L,R);
  52. return query(x+x,l,mid,L,R)+query(x+x+1,mid+1,r,L,R);
  53. }
  54. int main()
  55. {
  56. scanf("%lld",&n);
  57. for(ll i=1;i<=n;i++)
  58. {
  59. scanf("%lld%lld",&a[i].x,&a[i].y);
  60. x[i]=a[i].x; y[i]=a[i].y;
  61. }
  62. sort(x+1,x+n+1); sort(y+1,y+n+1);
  63. ll xn=unique(x+1,x+n+1)-x-1;
  64. ll yn=unique(y+1,y+n+1)-y-1;
  65. for(ll i=1;i<=n;i++)
  66. {
  67. a[i].x=lower_bound(x+1,x+xn+1,a[i].x)-x;
  68. a[i].y=lower_bound(y+1,y+yn+1,a[i].y)-y;
  69. }
  70. sort(a+1,a+n+1);
  71. build(1,1,xn+1);
  72. ll ans=0,sum=0;
  73. ll beg=1,now=1;
  74. memset(vis,0,sizeof(vis));
  75. while(beg<=n)
  76. {
  77. ll pre=0;
  78. while(a[beg].y==a[now].y&&now<=n)
  79. {
  80. ll tmp=query(1,1,xn+1,pre+1,a[now].x-1);
  81. ans-=tmp*(tmp+1)/2;
  82. pre=a[now].x;
  83. now++;
  84. }
  85. ll tmp=query(1,1,xn+1,pre+1,xn);
  86. ans-=tmp*(tmp+1)/2;
  87. while(beg<now)
  88. {
  89. if(!vis[a[beg].x])
  90. {
  91. sum++;
  92. vis[a[beg].x]=1;
  93. update(1,1,xn+1,a[beg].x);
  94. }
  95. beg++;
  96. }
  97. ans+=(sum+1)*sum/2;
  98. }
  99. cout<<ans<<endl;
  100. return 0;
  101. }

转载于:https://www.cnblogs.com/Forever-666/p/11253460.html

发表评论

表情:
评论列表 (有 0 条评论,76人围观)

还没有评论,来说两句吧...

相关阅读