题解 CF1190D

扫描线板子题？

首先离散化是理所当然的，因为这个矩形无上界，我们考虑按排序，从上往下枚举。（其实也算是出题人的暗示）

接下来的问题是如何统计下界为的矩形数量，事实上我们只关心矩形的和,自然而然想到枚举,枚举什么？？枚举和会让复杂度爆炸。

考虑如何优化，（当然是换个东西枚举）
我们选择枚举相同的点，对于一个点，在左侧的点会对产生贡献，在右侧的点会对产生贡献。但是我们发现这样有重复的矩形！

仔细思考一波，事实上不同的产生的矩形是不同的，对于一个点，只有在(这里)到之间的还没有被统计过。这样我们只需要统计右侧的点和到之间的点的数量，再根据乘法原理得到答案就行了。

萌新：统计要枚举啊。

神犇：出门左转树状数组。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=200010;
const ll INF=2147483647;
struct node
{
    ll x,y;
}a[maxn];
node r[maxn];
bool cmpy(node x,node y)
{
    if(x.y == y.y)return x.x < y.x;
    return x.y > y.y;
}
ll n,ix[maxn],iy[maxn],totx,toty,cnt[maxn],tot,res;
bool vis[maxn];
ll lowbit(ll x)
{
    return x & (-x);
}
void update(ll x)
{
    while(x <= n)
    {
        cnt[x]++;
        x += lowbit(x);
    }
    return;
}
ll qry(ll x)
{
    ll tem = 0;
    while(x)
    {
        tem += cnt[x];
        x -= lowbit(x);
    }
    return tem;
}
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
        cin>>a[i].x>>a[i].y;
        ix[i] = a[i].x;
        iy[i] = a[i].y;
    }
    sort(ix + 1,ix + n + 1);
    sort(iy + 1,iy + n + 1);
    totx = unique(ix + 1,ix + n + 1) - ix - 1;
    toty = unique(iy + 1,iy + n + 1) - iy - 1;
    for(int i = 1;i <= n;i++)
    {
        a[i].x = lower_bound(ix + 1,ix + totx + 1,a[i].x) - ix;
        a[i].y = lower_bound(iy + 1,iy + toty + 1,a[i].y) - iy;
    }
    //for(int i = 1;i <= n;i++)cout<<i<<" "<<a[i].x<<" "<<a[i].y<<endl;
    sort(a + 1,a + n + 1,cmpy);
    for(int i = 1;i <= n;i++)
    {
        if(i < n && a[i].y == a[i + 1].y)
        {
            if(!vis[a[i].x])
            {
                update(a[i].x);
                vis[a[i].x] = 1;
            }
            continue;
        }
        if(!vis[a[i].x])
        {
            update(a[i].x);
            vis[a[i].x] = 1;
        }
        ll pos = i;
        while(a[pos - 1].y == a[pos].y && pos > 1)pos--;
        ll item = 0;
        for(int j = pos;j <= i;j++)
        {
            res += 1ll * (qry(n) - qry(a[j].x - 1))*(qry(a[j].x) - qry(item));
            //cout<<j<<" "<<res<<"\n";
            item = a[j].x;
        }
    }
    cout<<res;
    return 0;
}

后记:这道题考场并没能直接A掉，主要是前面的题耗时太长，看来以后还要加强基础题的训练。