Codeforces - 1191F - Tokitsukaze and Strange Rectangle - 组合数学

https://codeforces.com/contest/1191/problem/F

看了一下题解的思路，感觉除了最后一段以外没什么启发。

首先离散化x加快速度，免得搞多一个log。其实y不需要离散化。

规定无穷大就是xn+1这个很好理解嘿嘿。（反正开多了5个不怕）

注意到其实从上往下一行一行扫过去，每次必须新增的元素才是新的集合，那很容易想到一个不重不漏的办法就是每次计算“以点p[i]为加进去的新点中的结束的集合”，那么假设一开始p[i]的左侧有cntl个点，那么显然有(cntl+1)条线在p[i]的左侧，而p[i]的右侧有cntr个点，也是(cntr+1)条线。

这个cntl显然就是query(1,p[i].x-1)，而右侧则是query(p[i].x+1,p[i+1].x-1)，因为不能包含同y的下一个点p[i+1]，而其中，上面的点选法也会产生区别。

那么每层加入一个正无穷也就是xn+1就可以了。

溢出这种现在我不会错的了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

struct Point {

    int x, y;

    bool operator<(const Point &p)const {

        return y == p.y ? x<p.x: y>p.y;

        //y从上到下，x从左到右

    }

} p[200005];

int x[200005];

int y[200005];

ll sum;

const int MAXM = 200000;

int st[(MAXM << 2) + 5];

inline void push_up(int o) {

    st[o] = st[o << 1] + st[o << 1 | 1];

}

void build(int o, int l, int r) {

    if(l == r) {

        st[o] = 0;

    } else {

        int m = (l + r) >> 1;

        build(o << 1, l, m);

        build(o << 1 | 1, m + 1, r);

        push_up(o);

    }

}

void update(int o, int l, int r, int x, int v) {

    if(l == r) {

        //不是加，是赋值，同x的点是没有差别的

        st[o] = v;

        return;

    } else {

        int m = (l + r) >> 1;

        if(x <= m)

            update(o << 1, l, m, x, v);

        else if(x >= m + 1)

            update(o << 1 | 1, m + 1, r, x, v);

        push_up(o);

    }

}

int query(int o, int l, int r, int a, int b) {

    if(b < a)

        return 0;

    else if(a <= l && r <= b) {

        return st[o];

    } else {

        int m = (l + r) >> 1;

        int ans = 0;

        if(a <= m)

            ans = query(o << 1, l, m, a, b);

        if(b >= m + 1)

            ans += query(o << 1 | 1, m + 1, r, a, b);

        return ans;

    }

}

int vx[200005], vxtop;

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

    //freopen("Yinku.out", "w", stdout);

#endif // Yinku

    while(~scanf("%d", &n)) {

        for(int i = 1; i <= n; i++) {

            scanf("%d%d", &p[i].x, &p[i].y);

            x[i] = p[i].x;

            y[i] = p[i].y;

        }

        sort(x + 1, x + 1 + n);

        int xn = unique(x + 1, x + 1 + n) - (x + 1);

        sort(y + 1, y + 1 + n);

        int yn = unique(y + 1, y + 1 + n) - (y + 1);

        for(int i = 1; i <= n; i++) {

            p[i].x = lower_bound(x + 1, x + 1 + xn, p[i].x) - x;

            p[i].y = lower_bound(y + 1, y + 1 + yn, p[i].y) - y;

            //从1开始分配新的坐标

            //printf("(%d,%d)\n", p[i].x, p[i].y);

        }

        sort(p + 1, p + 1 + n);

        //扫描线

        sum = 0;

        build(1, 1, xn + 1);

        int beg = 1, cur = 1;

        while(beg <= n) {

            vxtop = 0;

            while(p[cur].y == p[beg].y) {

                update(1, 1, xn + 1, p[cur].x, 1);

                vx[++vxtop] = p[cur].x;

                /*

                //点是不会重合的，那包含这个最左侧的点的都是全新集合

                int cntl = query(1, 1, xn, 1, p[cur].x - 1);

                //在这个点的左侧有cntl个x不同的点，那就有cntl+1个位置

                //sum += (cntl + 1); X

                //是以这个点为右侧边界的，所以右侧没得选 X

                */

                //该层y中是以这个x点为右侧边界，但是两个x点之间的上层y也是可选的

                cur++;

            }

            vx[++vxtop] = xn + 1;

            for(int i = 1; i <= vxtop - 1; i++) {

                //该层最右端的新点为vx[i]的数量

                int cntl = query(1, 1, xn + 1, 1, vx[i] - 1);

                int cntr = query(1, 1, xn + 1, vx[i] + 1, vx[i + 1] - 1);

                sum += 1ll * (cntl + 1) * (cntr + 1);

            }

            beg = cur;

        }

        printf("%lld\n", sum);

    }

}

偶尔用下树状数组，把一些多余操作去掉之后的最快的做法。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

struct Point {

    int x, y;

    bool operator<(const Point &p)const {

        return y == p.y ? x<p.x: y>p.y;

        //y从上到下，x从左到右

    }

} p[200005];

int x[200005];

ll _sum;

const int MAXM = 200005;

bool cntx[MAXM + 5];

int bit[MAXM + 5];

int upper;

inline int sum(int x) {

    int res = 0;

    while(x) {

        res = res + bit[x];

        x -= x & -x;

    }

    return res;

}

inline void update(int x) {

    if(cntx[x])

        return;

    else {

        cntx[x] = true;

        while(x <= upper) {

            bit[x] += 1;

            x += x & -x;

        }

    }

}

inline int range_sum(int x, int y) {

    return sum(y) - sum(x - 1);

}

int *vx=x,vxtop;

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

    //freopen("Yinku.out", "w", stdout);

#endif // Yinku

    while(~scanf("%d", &n)) {

        memset(cntx, false, sizeof(cntx));

        for(int i = 1; i <= n; i++) {

            scanf("%d%d", &p[i].x, &p[i].y);

            x[i] = p[i].x;

        }

        sort(x + 1, x + 1 + n);

        int xn = unique(x + 1, x + 1 + n) - (x + 1);

        for(int i = 1; i <= n; i++) {

            p[i].x = lower_bound(x + 1, x + 1 + xn, p[i].x) - x;

            //从1开始分配新的坐标

            //printf("(%d,%d)\n", p[i].x, p[i].y);

        }

        sort(p + 1, p + 1 + n);

        //扫描线

        _sum = 0;

        upper = xn + 1;

        int beg = 1, cur = 1;

        while(beg <= n) {

            vxtop = 0;

            while(p[cur].y == p[beg].y) {

                update(p[cur].x);

                vx[++vxtop] = p[cur].x;

                //该层y中是以这个x点为右侧边界，但是两个x点之间的上层y也是可选的

                cur++;

            }

            vx[++vxtop] = xn + 1;

            for(int i = 1; i <= vxtop - 1; i++) {

                //该层最右端的新点为vx[i]的数量

                int cntl = range_sum(1, vx[i] - 1);

                int cntr = range_sum(vx[i] + 1, vx[i + 1] - 1);

                _sum += 1ll * (cntl + 1) * (cntr + 1);

            }

            beg = cur;

        }

        printf("%lld\n", _sum);

    }

}

巴特西

Codeforces - 1191F - Tokitsukaze and Strange Rectangle - 组合数学 - 扫描线

最新文章

热门文章