CF1190D Tokitsukaze and Strange Rectangle-白红宇

CF1190D Tokitsukaze and Strange Rectangle

阅读量：4700 次

发布时间：2019-06-09

本文共 1342 字，大约阅读时间需要 4 分钟。

很简单的一个题目

由于向上是无限延伸的，所以我们从上往下考虑，然后对于每个\(x\)坐标，我们只用管它是否出现过。

统计答案就是按每个\(y\)坐标来统计，

如果只有一个点，直接计算当前出现的所有\(x\)的本质不同的区间覆盖的方案数就行了

但是现在有一个问题，对于同一个\(y\)坐标，\(x\)坐标可能不同，也就是可能有多个点，会算重。

然后我们选区间一定是要包含这一排中至少一个点，也就是去掉那些不合法的就行了。

~~好像讲的不清楚，但是我也没办法。~~

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        using namespace std;#define rg register#define lowbit(i) (i&(-i))void read(int &x){    char ch;bool ok;    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}const int maxn=1e6+10,N=1e6;int n,m,now,t[maxn],f[maxn];map
         
          mp;long long ans;struct oo{int x,y;}a[maxn];bool vis[maxn];bool cmp(oo a,oo b){return a.y==b.y?a.x
          
           b.y;}void add(int x){for(rg int i=x;i<=now;i+=lowbit(i))f[i]++;}int get(int x){int ans=0;for(rg int i=x;i;i-=lowbit(i))ans+=f[i];return ans;}long long C(int x){return 1ll*x*(x-1)/2;}int main(){ read(n); for(rg int i=1;i<=n;i++){ read(a[i].x),read(a[i].y); t[++m]=a[i].x,t[++m]=a[i].y; } sort(a+1,a+n+1,cmp),sort(t+1,t+m+1); for(rg int i=1;i<=m;i++)if(t[i]!=t[i-1])mp[t[i]]=++now; for(rg int i=1;i<=n;i++)a[i].x=mp[a[i].x],a[i].y=mp[a[i].y]; for(rg int i=1,j;i<=n;i=j){ j=i+1;int tot=get(now); while(a[j].y==a[i].y)j++; for(rg int k=i;k