题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5324
题意：给你一个二维的序列，让你找出最长的第一维升第二维降的子序列（如果多个答案，输出字典序最小）
解：考虑从后往前dp，在u点你需要知道u点之后的比u的第一维小，第二维大的dp最大值
可以用分治枚举u点之后比u的第一维大的点，然后用树状数组查询比u的第二维小的点中dp最大的
具体是：
dp[i]表示以 i 开头的最长子序列，从后往前更新。
更新u点时有u.dp=max(v.dp)+1；v满足v.x<=u.x，v.y>=u.y，且v的在序列中的u的后面
我们用分治枚举u后面y值比u.y大的点v，然后把以v.x为序号v.dp为值插入树状数组中，就可以O(logN)查询到v.x<=u.x的dp最大值了
总时间复杂度：O(N*logN*logN)
/*
* Problem: hdu5324 Boring Class
* Author: SHJWUDP
* Created Time: 2015/8/3 星期一 21:14:55
* File Name: 233.cpp
* State: Accepted
* Memo: 多维变量的后缀区间查询
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int INF=0x7f7f7f7f; const int MaxA=5e4+; struct Node {
int x, y, id;
bool operator<(const Node & rhs) const {
return y<rhs.y;
}
};
struct Hash : vector<int> { //离散化
void prepare() {
sort(begin(), end());
erase(unique(begin(), end()), end());
}
int get(int x) {
return lower_bound(begin(), end(), x)-begin()+;
}
};
struct Fenwick {
int n;
vector<pair<int, int> > c;
void init(int n) {
this->n=n;
c.assign(n+, make_pair(, -INF));
}
int lowbit(int x) {
return x & -x;
}
void modify(int x, pair<int, int> v) {
while(x<=n) {
c[x]=v; x+=lowbit(x);
}
}
void update(int x, pair<int, int> v) {
while(x<=n) {
c[x]=max(c[x], v); x+=lowbit(x);
}
}
pair<int, int> query(int x) {
pair<int, int> res(, -INF);
while(x>) {
res=max(res, c[x]); x-=lowbit(x);
}
return res;
}
} fw; int n;
vector<Node> arr, tmp;
vector<pair<int, int> > dp; //dp[i].pair(以i开头的最长子序列长度， -子序列中下一个位置)
void dc(int l, int r) {
if(l==r) return;
int m=(l+r)>>;
dc(m+, r);
for(int i=l; i<=r; i++) tmp[i]=arr[i];
sort(tmp.begin()+l, tmp.begin()+m+);
sort(tmp.begin()+m+, tmp.begin()+r+);
int pr=r;
for(int i=m; i>=l; i--) {
int cid=tmp[i].id;
while(pr>m && tmp[pr].y>=tmp[i].y) {
fw.update(tmp[pr].x, make_pair(dp[tmp[pr].id].first+, -tmp[pr].id));//将第二维大于当前点的都加到树状数组里面
pr--;
}
dp[cid]=max(dp[cid], fw.query(tmp[i].x));
}
for(int i=m+; i<=r; i++) fw.modify(tmp[i].x, make_pair(, -INF));//用完树状数组后清空
dc(l, m);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
while(~scanf("%d", &n)) {
arr.resize(n+); tmp.resize(n+);
Hash hash;
for(int i=; i<=n; i++) {
scanf("%d", &arr[i].x);
arr[i].id=i;
hash.push_back(arr[i].x);
}
hash.prepare();
for(int i=; i<=n; i++) arr[i].x=hash.get(arr[i].x);
hash.clear();
for(int i=; i<=n; i++) {
scanf("%d", &arr[i].y);
hash.push_back(arr[i].y);
}
hash.prepare();
for(int i=; i<=n; i++) arr[i].y=hash.get(arr[i].y); fw.init(n+);
dp.assign(n+, make_pair(, -INF));
dc(, n);
pair<int, int> ans(, -INF);
int stPos;
for(int i=; i<=n; i++) {
if(dp[i]>ans) {
ans=dp[i]; stPos=i;
}
}
printf("%d\n", ans.first);
printf("%d", stPos);
for(int i=-ans.second; i!=INF; i=-dp[i].second) printf(" %d", i);
printf("\n");
}
return ;
}
hdu5324