[2015hdu多校联赛补题]hdu5324 Boring Class

题目链接：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)

  1 /*
  2  * Problem: hdu5324 Boring Class 
  3  * Author:  SHJWUDP
  4  * Created Time:  2015/8/3 星期一 21:14:55
  5  * File Name: 233.cpp
  6  * State: Accepted
  7  * Memo: 多维变量的后缀区间查询
  8  */
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <algorithm>
 13 
 14 using namespace std;
 15 
 16 const int INF=0x7f7f7f7f;
 17 
 18 const int MaxA=5e4+7;
 19 
 20 struct Node {
 21     int x, y, id;
 22     bool operator<(const Node & rhs) const {
 23         return y<rhs.y;
 24     }
 25 };
 26 struct Hash : vector<int> {    //离散化
 27     void prepare() {
 28         sort(begin(), end());
 29         erase(unique(begin(), end()), end());
 30     }
 31     int get(int x) {
 32         return lower_bound(begin(), end(), x)-begin()+1;
 33     }
 34 };
 35 struct Fenwick {
 36     int n;
 37     vector<pair<int, int> > c;
 38     void init(int n) {
 39         this->n=n;
 40         c.assign(n+1, make_pair(0, -INF));
 41     }
 42     int lowbit(int x) {
 43         return x & -x;
 44     }
 45     void modify(int x, pair<int, int> v) {
 46         while(x<=n) {
 47             c[x]=v; x+=lowbit(x);
 48         }
 49     }
 50     void update(int x, pair<int, int> v) {
 51         while(x<=n) {
 52             c[x]=max(c[x], v); x+=lowbit(x);
 53         }
 54     }
 55     pair<int, int> query(int x) {
 56         pair<int, int> res(0, -INF);
 57         while(x>0) {
 58             res=max(res, c[x]); x-=lowbit(x);
 59         }
 60         return res;
 61     }
 62 } fw;
 63 
 64 int n;
 65 vector<Node> arr, tmp;
 66 vector<pair<int, int> > dp;    //dp[i].pair(以i开头的最长子序列长度， -子序列中下一个位置)
 67 void dc(int l, int r) {
 68     if(l==r) return;
 69     int m=(l+r)>>1;
 70     dc(m+1, r);
 71     for(int i=l; i<=r; i++) tmp[i]=arr[i];
 72     sort(tmp.begin()+l, tmp.begin()+m+1);
 73     sort(tmp.begin()+m+1, tmp.begin()+r+1);
 74     int pr=r;
 75     for(int i=m; i>=l; i--) {
 76         int cid=tmp[i].id;
 77         while(pr>m && tmp[pr].y>=tmp[i].y) {
 78             fw.update(tmp[pr].x, make_pair(dp[tmp[pr].id].first+1, -tmp[pr].id));//将第二维大于当前点的都加到树状数组里面
 79             pr--;
 80         }
 81         dp[cid]=max(dp[cid], fw.query(tmp[i].x));
 82     }
 83     for(int i=m+1; i<=r; i++) fw.modify(tmp[i].x, make_pair(0, -INF));//用完树状数组后清空
 84     dc(l, m);
 85 }
 86 int main() {
 87 #ifndef ONLINE_JUDGE
 88     freopen("in", "r", stdin);
 89     //freopen("out", "w", stdout);
 90 #endif
 91     while(~scanf("%d", &n)) {
 92         arr.resize(n+1); tmp.resize(n+1);
 93         Hash hash;
 94         for(int i=1; i<=n; i++) {
 95             scanf("%d", &arr[i].x);
 96             arr[i].id=i;
 97             hash.push_back(arr[i].x);
 98         }
 99         hash.prepare();
100         for(int i=1; i<=n; i++) arr[i].x=hash.get(arr[i].x);
101         hash.clear();
102         for(int i=1; i<=n; i++) {
103             scanf("%d", &arr[i].y);
104             hash.push_back(arr[i].y);
105         }
106         hash.prepare();
107         for(int i=1; i<=n; i++) arr[i].y=hash.get(arr[i].y);
108 
109         fw.init(n+1);
110         dp.assign(n+1, make_pair(1, -INF));
111         dc(1, n);
112         pair<int, int> ans(0, -INF);
113         int stPos;
114         for(int i=1; i<=n; i++) {
115             if(dp[i]>ans) {
116                 ans=dp[i]; stPos=i;
117             }
118         }
119         printf("%d
", ans.first);
120         printf("%d", stPos);
121         for(int i=-ans.second; i!=INF; i=-dp[i].second) printf(" %d", i);
122         printf("
");
123     }
124     return 0;
125 }

hdu5324