cf573 1d Tokitsukaze and Strange Rectangle

2019-07-17 by fffasttime·0评论

题意：给定平面上的一些坐标点，现在用U形区域\(l<=y<=r, x>=h\)框出这些点的子集，问这样的子集有多少个。

比较显然的扫描线计数的题。拿个树状数组维护左区间有多少个点，一行扫过去统计就行了。点出现同一行的情况会麻烦点，但也不难处理。

```
    #include <iostream>
```
```
    #include <cstdio>
```
```
    #include <cmath>
```
```
    #include <cstring>
```
```
    #include <algorithm>
```
```
    using namespace std;
```
```
    const int maxn=200010;
```
```
    typedef long long ll;
```
```
    struct Node{
```
```
    	int x,y;
```
```
    	bool operator<(const Node &v){
```
```
    		if (y==v.y) return x<v.x;
```
```
    		return y>v.y;
```
```
    	}
```
```
    }p[maxn];
```
```
 
```
```
    int dr[maxn];
```
```
 
```
```
    int tr[maxn];
```

    void add(int p, int x){for(;p<maxn;p+=p&-p)tr[p]+=x;}

    ll sum(int p){ll ret=0;for(;p;p-=p&-p)ret+=tr[p];return ret;}

```
 
```
```
    bool used[maxn];
```
```
 
```
```
    int main(){
```
```
    	int n; cin>>n;
```
```
    	for (int i=0;i<n;i++){
```
```
    		int x,y;
```
```
    		scanf("%d%d",&x,&y);
```
```
    		p[i]=(Node){x,y};
```
```
    		dr[i]=x;
```
```
    	}
```
```
    	sort(dr,dr+n);
```
```
    	sort(p,p+n);
```
```
    	int n1=unique(dr,dr+n)-dr;
```

    	for (int i=0;i<n;i++) p[i].x=lower_bound(dr,dr+n1,p[i].x)-dr+1;

```
    	ll ans=0;
```
```
    	for (int i=0;i<n;){
```
```
    		int r=i;
```

    		while (r<n && p[r+1].y==p[r].y) r++;

```
    		int u;
```
```
    		for (int j=i;j<=r;j++){
```
```
    			u=p[j].x;
```
```
    			if (!used[u]){
```
```
    				used[u]=1;
```
```
    				add(u,1);
```
```
    			}
```
```
    		}
```
```
    		u=maxn-1;
```
```
    		for (int j=r;j>=i;j--){
```

    			ans+=(sum(u-1)-sum(p[j].x)+1)*(sum(p[j].x-1)+1);

```
    			u=p[j].x;
```
```
    		}
```
```
    		i=r+1;
```
```
    	}
```
```
    	cout<<ans<<'\n';
```
```
    	return 0;
```
```
    }
```

发表评论取消回复