练习赛补题----Gym - 101908C Pizza Cutter 树状数组+离散化

Grandpa Giuseppe won a professional pizza cutter, the kind of type reel and, to celebrate, baked a rectangle pizza to his grandchildren! He always sliced his pizzas into pieces by making cuts over continuous lines, not necessarily rectilinear, of two types: some begin at the left edge of the pizza, follow continuously to the right and end up in the right edge; other start on lower edge, follow continuously up and end up on the top edge. But Grandpa Giuseppe always followed a property: two cuts of the same type would never intersect. Here is an example with 4 cuts, two of each type, in the left part of the figure, which divide the pizza in 9 pieces.

It turns out that Grandpa Giuseppe simply loves geometry, topology, combinatorics and stuff; so, he decided to show to his grandchildren who could get more pieces with the same number of cuts if cross cuts of the same type were allowed. The right part of the figure shows, for example, that if the two cuts of the type that go from left to right could intercept, the pizza would be divided into 10 pieces.

Grandpa Giuseppe ruled out the property, but will not make random cuts. In addition to being one of the two types, they will comply with the following restrictions:

Two cuts have at most one intersection point and, if they have, it is because the cuts cross each other at that point;
Three cuts do not intersect in a single point;
Two cuts do not intersect at the border of the pizza;
A cut does not intercept a pizza corner.
Given the start and end points of each cut, your program should compute the number of resulting pieces from the cuts of Grandfather Giuseppe.

Input

The first line of the input contains two integers X

and Y, (1≤X,Y≤109), representing the coordinates (X,Y) of the upper-right corner of the pizza. The lower left corner has always coordinates (0,0). The second line contains two integers H and V, (1≤H,V≤105), indicating, respectively, the number of cuts ranging from left to right and the number of cuts ranging from bottom to top. Each of the following lines H contains two integers Y1 and Y2, a cut that intercepts the left side with y-coordinate Y1 and the right side at y-coordinate Y2. Each of the following V lines contains two integers X1 and X2, a cut that intercept the bottom side at x-coordinate X1 and the upper side at x-coordinate X2

.

Examples

Input

3 4
3 2
1 2
2 1
3 3
1 1
2 2
Output

13
Input

5 5
3 3
2 1
3 2
1 3
3 4
4 3
2 2
Output

19
Input

10000 10000
1 2
321 3455
10 2347
543 8765
Output

6

思路很清晰，队友已经推出来了，切割平面的总和是横：1+与这条线相交的线的数量+纵：1+与这条线相交线的数量+横的线的数量*纵的线的数量+1；
我傻逼的是我居然就想用二分求逆序数，其实不行的，因为遍历的时候每次把前面的y值放在一个数组里，这样不是有序的，我一直在无序的数组里二分的，笑了；每次排一下序必超时，只能用树状数组了，是log(n)的复杂度
因为边界x，y是10的九次，所以不能直接将出现的值映射到树状数组中，所以需要将值排序之后，重新编一下号，每次二分找一下该值对应的编号即可（也就是离散化一下）；

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 1e5 + 5;

typedef struct Node{
    int x,y;
    friend bool operator < (const Node &p,const Node &q){
        return p.x < q.x;
    }
}Node;
Node node[N];
int ans[N * 2];
int b[N * 2];
int cnt = 0;

void update(int pos,int val)
{
    while(pos <= cnt){
        ans[pos] += val;
        pos += pos&(-pos);
    }
}

int query(int pos)
{
    int res = 0;
    while(pos)
    {
        res += ans[pos];
        pos -= pos&(-pos);
    }
    return res;
}

int main()
{
    LL x,y;
    scanf("%d %d",&x,&y);
    int h,v;
    scanf("%d %d",&h,&v);
    for(int i = 0;i < h;++i){
        scanf("%d %d",&node[i].x,&node[i].y);
        b[cnt++] = node[i].x;
        b[cnt++] = node[i].y;
    }
    sort(b,b + cnt);
    int len = unique(b,b + cnt) - b;
    sort(node,node + h);
    //一直找错误，原来是这里(LL)(h * v)爆了
    LL sum = 1LL + h + v + (LL)h * (LL)v;
    for(int i = 0;i < h;++i){
        int pos = lower_bound(b,b + len,node[i].y) - b + 1;
        sum += (LL)(i - query(pos));
       // cout << i << " " << i - query(pos) << " " << pos << endl;
        update(pos,1);
    }
    cnt = 0;
    for(int i = 0;i < v;++i){
        scanf("%d %d",&node[i].x,&node[i].y);
        b[cnt++] = node[i].x;
        b[cnt++] = node[i].y;
    }
    sort(b,b + cnt);
    len = unique(b,b + cnt) - b;
    sort(node,node + v);
    memset(ans,0,sizeof(ans));
    for(int i = 0;i < v;++i){
        int pos = lower_bound(b,b + len,node[i].y) - b + 1;
        sum += (LL)(i - query(pos));
        //cout << i << " " << pos << " " << query(4) << endl;
        update(pos,1);
    }
    printf("%lld\n",sum);
    return 0;
}