A simple Blog for wyx I've been down the bottle hoping.
4553: [Tjoi2016&Heoi2016]序列 数据结构模板题
发表于: | 分类: Oi | 评论:0 | 阅读:54

我也不知道为啥TJ考了一道什么数据结构都能做的数据结构模板题23333333

我们令 $f_i$ 表示到达第 $i$ 个位置时的最长子序列是多长,那么显然有

$f_i = \max{f_j }+1$

这个的前提当然是 $Max_j \le a_i$ 而且 $a_j \le Min_i$

$Max_i,Min_i$ 表示 $i$ 位置能够取到的最大/小值

然后就有了以下几个做法

1.树套树

我们把两个属性看成是平面内的一个点,那么一次查询就是查询一个矩形内部的权值的最大值,这个东西是显然可以用线段树套线段树来做的,常数飞起,但是在BZ上确实是可以过的

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int MAX = 1e5;
const int N = 1e5+5;
const int M = 105*N;
using namespace std;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int tr[M], sz, root[N<<2], ls[M], rs[M];

inline void change(int &k,int l,int r,int pos,int val) {
    if(!k) k = ++sz;
    if(l==r) {
        tr[k] = max(tr[k], val);
        return;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) change(ls[k], l, mid, pos, val);
    else change(rs[k], mid+1, r, pos, val);
    tr[k] = max(tr[ls[k]], tr[rs[k]]);
}

inline int Ask(int k,int l,int r,int x,int y) {
    if(!k) return 0;
    if(x <= l && r <= y) return tr[k];
    int mid = (l+r) >> 1;
    int ans = 0;
    if(x <= mid) ans = max(ans, Ask(ls[k],l,mid,x,y));
    if(y > mid) ans = max(ans, Ask(rs[k],mid+1,r,x,y));
    return ans;
}

inline void change(int k,int l,int r,int x,int y,int val) {
    change(root[k], 1, MAX, x, val);
    if(l==r) return;
    int mid = (l+r) >> 1;
    if(y <= mid) change(k<<1,l,mid,x,y,val);
    else change(k<<1|1,mid+1,r,x,y,val);
}

inline int ask(int k,int l,int r,int x,int y) {
    if(r==y)  return Ask(root[k], 1, MAX, 1, x);
    int mid = (l+r) >> 1;
    if(y <= mid) return ask(k<<1,l,mid,x,y);
    else return max(ask(k<<1,l,mid,x,mid), ask(k<<1|1,mid+1,r,x,y));
}

int F[N], Min[N], Max[N], a[N];

int main() {
//  freopen("heoi2016_seq.in","r",stdin);
//  freopen("heoi2016_seq.out","w",stdout);
    freopen("tt.in","r",stdin);
    int n = read(), m = read();
    for(int i=1;i<=n;++i) a[i] = Min[i] = Max[i] = read();
    for(int i=1;i<=m;++i) {
        int x = read(), y = read();
        Min[x] = min(Min[x], y);
        Max[x] = max(Max[x], y);
    }
//  for(int i=1;i<=n;++i) cout << Min[i] << " " << Max[i] << endl;
    for(int i=1;i<=n;++i) {
        int tmp = ask(1,1,MAX,a[i],Min[i]);
        change(1,1,MAX,Max[i],a[i],tmp+1);
        F[i] = tmp + 1;
    }
    for(int i=1;i<=n;++i) cout << i << " " << F[i] << endl;
    int ans = 0;
    for(int i=1;i<=n;++i) ans = max(ans, F[i]);
    cout << ans << endl;
}

  1. kd-tree

和上面的思路是一样的,只不过维护的数据结构变成了kdtree,注意到数据是卡了不重构的kdtree的,我的代码在cogs上是可以过的,不知道为什么在BZ上过不了TAT

#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e5+5;
const int M = 1e5+5;
using namespace std;

int last;
bool flag;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct poi {
    int x, y, val;
    poi (int _x=0,int _y=0,int _val=0) :x(_x), y(_y), val(_val){}
    bool operator < (const poi &z) const {
        if(flag) return x ^ z.x ? x < z.x : y < z.y;
        else return y ^ z.y ? y < z.y : x < z.x;
    }
}tmp[N];

int top;

struct kdtree {
    int ch[2], x[2], y[2], size, val;
    poi z;
}tr[M];

inline void updata(int k) {
    tr[k].size = 1;
    if(tr[k].ch[0]) {
        int p = tr[k].ch[0];
        tr[k].x[0] = min(tr[k].x[0], tr[p].x[0]);
        tr[k].x[1] = max(tr[k].x[1], tr[p].x[1]);
        tr[k].y[0] = min(tr[k].y[0], tr[p].y[0]);
        tr[k].y[1] = max(tr[k].y[1], tr[p].y[1]);
        tr[k].size += tr[p].size ;
        tr[k].val = max(tr[k].val, tr[p].val);
    }
    if(tr[k].ch[1]) {
        int p = tr[k].ch[1];
        tr[k].x[0] = min(tr[k].x[0], tr[p].x[0]);
        tr[k].x[1] = max(tr[k].x[1], tr[p].x[1]);
        tr[k].y[0] = min(tr[k].y[0], tr[p].y[0]);
        tr[k].y[1] = max(tr[k].y[1], tr[p].y[1]);
        tr[k].size += tr[p].size ;
        tr[k].val = max(tr[k].val, tr[p].val);
    }
}

queue <int> q;

inline void DFS(int &k) {
    if(tr[k].ch[0]) DFS(tr[k].ch[0]);
    q.push(k); tmp[++top] = tr[k].z;
    if(tr[k].ch[1]) DFS(tr[k].ch[1]);
    k = 0;
}

inline void build(int &k,int L,int R,bool t) {
    if(L > R) return;
    flag = t;
    k = q.front(); q.pop();
    tr[k].ch[0] = tr[k].ch[1] = 0;
    tr[k].size = 1;
    int mid = (L+R) >> 1;
    nth_element(tmp+L+1,tmp+mid+1,tmp+R+1);
    tr[k].z = tmp[mid]; tr[k].val = tmp[mid].val;
    tr[k].x[0] = tr[k].x[1] = tmp[mid].x;
    tr[k].y[0] = tr[k].y[1] = tmp[mid].y;
    build(tr[k].ch[0], L, mid-1, t^1);
    build(tr[k].ch[1], mid+1, R, t^1);
    updata(k);
}

inline void rebuild(int &k) {
    top = 0;
    DFS(k);
    build(k, 1, top, 0);
}

inline void insert(int &k,poi a,bool t) {
    static int sz = 0;
    flag = t;
    if(!k) {
        k = ++sz;
        tr[k].x[0] = tr[k].x[1] = a.x;
        tr[k].y[0] = tr[k].y[1] = a.y;
        tr[k].z = a;
        tr[k].size = 1;
        tr[k].val = a.val;
        return;
    }
    if(a < tr[k].z) insert(tr[k].ch[0], a, t^1);
    else insert(tr[k].ch[1], a, t^1);
    updata(k);
    bool tt = false;
    if(tr[k].ch[0] && tr[tr[k].ch[0]].size * 5 > tr[k].size * 4) tt = 1;
    if(tr[k].ch[1] && tr[tr[k].ch[1]].size * 5 > tr[k].size * 4) tt = 1;
    if(tt)rebuild(k);
}

inline int ask(int k,int x1,int y1,int x2,int y2) {
    if(!k) return 0;
    if(tr[k].x[0] >= x1 && tr[k].x[1] <= x2 && tr[k].y[0] >= y1 && tr[k].y[1] <= y2) return tr[k].val;
    if(tr[k].x[1] < x1 || tr[k].x[0] > x2 || tr[k].y[1] < y1 || tr[k].y[0] > y2) return 0;
    int tmp = max(ask(tr[k].ch[0], x1, y1, x2, y2), ask(tr[k].ch[1], x1, y1, x2, y2));
    if(tr[k].z.x >= x1 && tr[k].z.x <= x2 && tr[k].z.y >= y1 && tr[k].z.y <= y2) tmp = max(tmp, tr[k].z.val);
    return tmp;
}

int F[N], root, a[N], Min[N], Max[N];

int main() {
//  freopen("heoi2016_seq.in","r",stdin);
//  freopen("heoi2016_seq.out","w",stdout);
    freopen("tt.in","r",stdin);
    int n = read(), m = read();
    for(int i=1;i<=n;++i) a[i] = Min[i] = Max[i] = read();
    for(int i=1;i<=m;++i) {
        int x = read(), y = read();
        Min[x] = min(Min[x], y);
        Max[x] = max(Max[x], y);
    }
    for(int i=1;i<=n;++i) {
        int tmp = ask(root, 1, 1, a[i], Min[i]);
        F[i] = tmp + 1;
        insert(root, poi(Max[i], a[i], F[i]), 0);
    }
//  for(int i=1;i<=n;++i) cout << i << " " << F[i] << endl;
    int ans = 0;
    for(int i=1;i<=n;++i) ans = max(ans, F[i]);
    cout << ans << endl;
}

  1. $CDQ$ 分治

$i<j$

$Max_j \le a_i$

$a_j \le Min_i$

刚好三维,非常优雅,做的时候就可以用树状数组维护前缀最小值了

比树套树快40倍

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define lowbit(x) ((x)&(-x))
const int N = 1e5+5;
const int MAX = 1e5;
using namespace std;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int tr[N];

inline void updata(int x,int val) {
    while(x <= MAX) {
        tr[x] = max(tr[x], val);
        x += lowbit(x);
    }
}

inline int ask(int x) {
    int ans = 0;
    while(x) {
        ans = max(ans, tr[x]);
        x -= lowbit(x);
    }
    return ans;
}

inline void clear(int x) {
    while(x <= MAX) {
        tr[x] = 0;
        x += lowbit(x);
    }
}

int F[N], a[N], Min[N], Max[N];

struct data{
    int pos, val, Min, Max;
} stack1[N], stack2[N];
int top1, top2;

bool cmp1(const data &a,const data &b) {return a.Max < b.Max;}
bool cmp2(const data &a,const data &b) {return a.val < b.val;}

inline void solve(int L,int R) {
    if(L == R) {
        F[L] ++;
        return;
    }
    if(L > R) return;
    int mid = (L+R) >> 1;
    solve(L,mid);
    top1 = 0, top2 = 0;
    for(int i=L;i<=mid;++i) stack1[++top1] = (data) {i, a[i], Min[i], Max[i]};
    for(int i=mid+1;i<=R;++i) stack2[++top2] = (data) {i, a[i], Min[i], Max[i]};
    sort(stack1+1,stack1+top1+1,cmp1);
    sort(stack2+1,stack2+top2+1,cmp2);
    int LL = 1;
    for(int i=1;i<=top2;++i) {
        while(LL<=top1&&stack1[LL].Max<=stack2[i].val) {
            updata(stack1[LL].val, F[stack1[LL].pos]);
            LL ++;
        }
        int tt = ask(stack2[i].Min);
        F[stack2[i].pos] = max(F[stack2[i].pos], tt);
    }
    for(int i=1;i<=top1;++i) clear(stack1[i].val);
    solve(mid+1,R);
}


int main() {
//  freopen("heoi2016_seq.in","r",stdin);
//  freopen("heoi2016_seq.out","w",stdout);
    int n = read(), m = read();
    for(int i=1;i<=n;++i) a[i] = Min[i] = Max[i] = read();
    for(int i=1;i<=m;++i) {
        int x = read(), y = read();
        Min[x] = min(Min[x], y);
        Max[x] = max(Max[x], y);
    }
    solve(1, n);
    int ans = 0;
    for(int i=1;i<=n;++i) ans = max(ans, F[i]);
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP