BZOJ4237: 稻草人
单调栈 二分 分治    2016-10-19 23:34:03    190    0    5
jszyxw   单调栈 二分 分治

4237: 稻草人

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 456  Solved: 191
[Submit][Status][Discuss]

Description

JOI村有一片荒地,上面竖着N个稻草人,村民们每年多次在稻草人们的周围举行祭典。
有一次,JOI村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件:
田地的形状是边平行于坐标轴的长方形;
左下角和右上角各有一个稻草人;
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标,请你求出有多少遵从启示的田地的个数

 

Input

第一行一个正整数N,代表稻草人的个数
接下来N行,第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi,表示第i个稻草人的坐标

 

Output

输出一行一个正整数,代表遵从启示的田地的个数

 

Sample Input

4
0 0
2 2
3 4
4 3

Sample Output

3

HINT

 

所有满足要求的田地由下图所示:

 

1<=N<=2*10^5

0<=Xi<=10^9(1<=i<=N)

0<=Yi<=10^9(1<=i<=N)

Xi(1<=i<=N)互不相同。

Yi(1<=i<=N)互不相同。
 

Source

JOI 2013~2014 春季training合宿 竞技3 By PoPoQQQ

 

Solution

先将点按y轴排序,然后分治。

首先分治求出上下两块的答案,然后考虑左下角在下半部分,右上角在上半部分的答案

设左下角为(x1,y1),右上角为(x2,y2)

显然对于上部分有:对于所有横坐标在(x1,x2)的点,纵坐标≥y2

显然对于下部分有:对于所有横坐标在(x1,x2)的点,纵坐标≤y1

维护两个单调栈,枚举右上角,在单调栈上二分找符合条件的左下角即可

 

/*{{{*/
#include <bits/stdc++.h>

#define VAL(x) #x " = " << x << " "

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

string program_name = __FILE__;
string iput = program_name.substr(0, program_name.length() - 4) + ".in";
string oput = program_name.substr(0, program_name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }
 
template <class T> inline T &read(T &x) 
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) if (c == '-') f = -1;
    for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x *= f;
}
 
template <class T> void write(T x, char p = '\n') 
{
    register T tmp = 1;
    if (x < 0) putchar('-'), x = -x;
    while (x / tmp > 9) tmp *= 10;
    while (tmp) putchar(x / tmp + 48), x -= x / tmp * tmp, tmp /= 10;
    putchar(p);
}
/*}}}*/
 
const int mo = 1000000007;
const int oo = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
 
int n;
pii a[maxn];
pii b[maxn];

ll ans;

int top1, top2;
pii S[maxn], S2[maxn];

inline void find(int x, int l, int r)
{
    int mid;
    while (l <= r) {
        if (S2[mid = l + r >> 1].first < x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    ans += top2 - l + 1;
}

void Divide_and_Conquer(int l, int r)
{
    if (l == r)
        return;

    int mid = l + r >> 1;
    Divide_and_Conquer(l, mid);
    Divide_and_Conquer(mid + 1, r);

    top1 = top2 = 0;
    for (register int i = mid + 1, pos = l; i <= r; ++ i) {
        while (top1 && S[top1].second > a[i].second) -- top1;
        S[++ top1] = a[i];
        while (pos <= mid && a[pos].first < a[i].first) {
            while (top2 && S2[top2].second < a[pos].second) -- top2;
            S2[++ top2] = a[pos ++];
        }
        find(S[top1 - 1].first, 1, top2);
    }

    int cnt = l - 1;
    int p = l, q = mid + 1;

    while (p <= mid || q <= r) {
        if (q > r || (a[p] < a[q] && p <= mid))
            b[++ cnt] = a[p ++];
        else
            b[++ cnt] = a[q ++];
    }

    for (register int i = l; i <= r; ++ i)
        a[i] = b[i];
}

inline bool cmp_Y(const pii &x, const pii &y)
{
    return x.second < y.second;
}

void exec() 
{
    read(n);
    for (int i = 1; i <= n; ++ i) {
        read(a[i].first);
        read(a[i].second);
    }

    sort(a + 1, a + n + 1, cmp_Y);

    Divide_and_Conquer(1, n);

    write(ans);
}

/*{{{*/
int main() 
{
    //ios::sync_with_stdio(false);

    if (fopen(iput.c_str(), "r")) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }
 
    exec();

#ifdef DEBUG_STATUS
    cerr << "\nRunning Time: " << (double) clock() / CLOCKS_PER_SEC << endl;
#endif

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/

 

UOJ#55. 【WC2014】紫荆花之恋
190 人读过
立即登录, 发表评论.
没有帐号? 立即注册
5 条评论
文档导航