【cdq分治】HDOJ 5324 Boring Class

#include <iostream>
#include <queue> 
#include <stack> 
#include <map> 
#include <set> 
#include <bitset> 
#include <cstdio> 
#include <algorithm> 
#include <cstring> 
#include <climits>
#include <cstdlib>
#include <cmath>
#include <time.h>
#define maxn 50005
#define maxm 10000005
#define eps 1e-7
#define mod 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#define lowbit(x) (x&(-x))
#define mp make_pair
#define ls o<<1
#define rs o<<1 | 1
#define lson o<<1, L, mid 
#define rson o<<1 | 1, mid+1, R
#define pii pair<int, int>
#pragma comment(linker, "/STACK:16777216")
typedef long long LL;
typedef unsigned long long ULL;
//typedef int LL;
using namespace std;
LL qpow(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base;base=base*base;b/=2;}return res;}
LL powmod(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base%mod;base=base*base%mod;b/=2;}return res;}
// head

int tree[maxn];
int yy[maxn];
int dp[maxn];

struct node
{
    int x, y, id;
    node(int x = 0, int y = 0, int id = 0) : x(x), y(y), id(id) {}
}tp[maxn];

vector<int> vec;
pii p[maxn];
int ta[maxn];
int tb[maxn];
int n, m;

void add(int x, int v)
{
    for(int i = x; i > 0; i -= lowbit(i)) tree[i] = max(tree[i], v);
}

int query(int x, int N)
{
    int res = 0;
    for(int i = x; i <= N; i += lowbit(i)) res = max(res, tree[i]);
    return res;
}

int cmp(node a, node b)
{
    if(a.x != b.x) return a.x < b.x;
    else if(a.y != b.y) return a.y > b.y;
    else return a.id < b.id;
}

void cdq(int L, int R)
{
    if(L == R) {
        dp[L]++;
        return;
    }
    int mid = (L + R) >> 1;
    cdq(mid+1, R);
    
    int cnt = 0;
    for(int i = L; i <= R; i++) {
        yy[++cnt] = p[i].second;
        tp[cnt] = node(p[i].first, p[i].second, i);
    }
    sort(yy+1, yy+cnt+1);
    int tcnt = unique(yy+1, yy+cnt+1) - yy - 1;

    for(int i = 1; i <= cnt; i++) tp[i].y = lower_bound(yy+1, yy+tcnt+1, tp[i].y) - yy;
    
    for(int i = 1; i <= cnt; i++) tree[i] = 0;
    sort(tp+1, tp+cnt+1, cmp);
    for(int i = 1; i <= cnt; i++) {
        if(tp[i].id <= mid) dp[tp[i].id] = max(dp[tp[i].id], query(tp[i].y, cnt));
        else add(tp[i].y, dp[tp[i].id]);
    }

    cdq(L, mid);
}

void work()
{
    for(int i = 1; i <= n; i++) scanf("%d", &ta[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &tb[i]);
    for(int i = 1; i <= n; i++) p[i] = mp(ta[i], tb[i]);

    memset(dp, 0, sizeof dp);
    cdq(1, n);
    
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, dp[i]);
    vec.clear();
    int pos = 1, tx = INF, ty = -INF;
    for(int k = 1; k <= ans; k++) {
        int tt = ans - k + 1;
        for(int i = pos; i <= n; i++) if(dp[i] == tt && p[i].first <= tx && p[i].second >= ty) {
            pos = i+1;
            tx = p[i].first;
            ty = p[i].second;
            vec.push_back(i);
            break;
        }
    }
    printf("%d
", (int)vec.size());
    for(int i = 0; i < vec.size(); i++) printf("%d%c", vec[i], i == (int)vec.size() - 1 ? '
' : ' ');
}

int main()
{
    while(scanf("%d", &n) != EOF) {
        work();
    }
    
    return 0;
}