A simple Blog for wyx I've been down the bottle hoping.
4825: [Hnoi2017]单旋 线段树
发表于: | 分类: Oi | 评论:0 | 阅读:59

我去了 我服了这题了……考试的时候肯定稳妥50滚粗了……

从下午两点想到晚上七点然后发现了一个非常显而易见的性质,然后巧妙的避开了所有需要维护原树的东西23333333,累死我了……

首先通过撕烤容易发现一次单旋只会让除了他右子树的所有点的深度+1,右子树的点的深度是不会变的

一种非常简单易懂但是暴力的方法就是我们可以记录一下每个节点的父亲和两个儿子,由于每次修改的次数非常少所以是可以这样维护的,至于维护子树的深度我们可以用 $ETT$ 大力维护一波

珍爱生命,我们还是写点好写的吧……

容易发现这两个点到根的路径都是直♂的。我们下面以最小值为例吧,最小值是没有左儿子的,然后他可能会有右子树,如何定位他的右子树呢?考虑他的父亲节点,我们中序遍历这个splay他的父亲节点一定是在中序遍历中一定是第一个深度小于他且值大于他的数字。有了这个性质这题就非常好做了……我们可以用一个线段树维护一下每个权值对应点在splay中的深度,对于一个插入显然会插在前驱和后继中深度较大的那个点的下方,而对于一个提根我们只需要先把这个点删掉,然后找到第一个权值 $x$ 使得 $depth_x >= depth_i$,删除一个点则对应着所有点的深度都-1

还有一个小问题就是如果你直接二分的去找这几个东西的话复杂度是 $O(n\log^2(n))$, 我们可以维护一个区间从左到右的第一个权值和从右到左的第一个权值,这样就能做到 $O(n\log(n))$ 了

比$ETT$ 好写但是也没好写到哪里去……
开始的时候区间修改写挂了……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
const int N = 1e5+5;
const int M = N << 2;
int n, m;


__attribute__((always_inline)) char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}

__attribute__((always_inline)) int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc())) if(ch == EOF) return -1;
    for(D=ch-'0'; isdigit(ch=getc());) D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}
#define RG register
namespace io
{
    const int MaxBuff = 1 << 20;
    const int Output = 1 << 24;
    char B[MaxBuff], *S = B, *T = B;
    //#define getc() getchar()
    #define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
    char Out[Output], *iter = Out;
    __attribute__((always_inline)) void flush()
    {
        fwrite(Out, 1, iter - Out, stdout);
        iter = Out;
    }
}

template<class Type> __attribute__((always_inline)) void print(RG Type x, RG char ch = '\n')
{
    using namespace io;
    if(!x) *iter++ = '0';
    else
    {
        if(x < 0) *iter++ = '-', x = -x;
        static int S2[100]; RG int t = 0;
        while(x) S2[++t] = x % 10, x /= 10;
        while(t) *iter++ = '0' + S2[t--];
    }
    *iter++ = ch;
}



struct data {
    int x, id;
    bool operator < (const data &z) const {
        return x < z.x;
    }
} b[N];

int tr[M], Min[M], Max[M], cnt[M], lazy[M];

inline void updata(int k) {
    tr[k] = min(tr[k<<1], tr[k<<1|1]);
    cnt[k] = cnt[k<<1] + cnt[k<<1|1];
    if(cnt[k<<1]) Min[k] = Min[k<<1]; 
    else Min[k] = Min[k<<1|1];
    if(cnt[k<<1|1]) Max[k] = Max[k<<1|1];
    else Max[k] = Max[k<<1];
}

inline void down(int k,int l,int r) {
    if(!lazy[k] || l == r)  return;
    int tmp = lazy[k]; lazy[k] = 0;
    if(cnt[k<<1]) {
        tr[k<<1] += tmp;
        Min[k<<1] += tmp;
        Max[k<<1] += tmp;
        lazy[k<<1] += tmp;
    }
    if(cnt[k<<1|1]) {
        tr[k<<1|1] += tmp;
        Min[k<<1|1] += tmp;
        Max[k<<1|1] += tmp;
        lazy[k<<1|1] += tmp;
    }
}

inline int find_pre(int k,int l,int r,int pos) {
    if(r == pos) return Max[k];
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(pos <= mid) return find_pre(k<<1,l,mid,pos);
    int tt = find_pre(k<<1|1,mid+1,r,pos);
    if(tt > 0) return tt;
    else return Max[k<<1];
}

inline int find_nxt(int k,int l,int r,int pos) {
    if(l == pos) return Min[k];
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(pos > mid) return find_nxt(k<<1|1,mid+1,r,pos);
    int tt = find_nxt(k<<1,l,mid,pos);
    if(tt > 0) return tt;
    else return Min[k<<1|1];
}

inline int get_pos_1(int k,int l,int r,int val) {
    if(l==r) return l;
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(cnt[k<<1] && tr[k<<1]<val) return get_pos_1(k<<1,l,mid,val);
    else return get_pos_1(k<<1|1,mid+1,r,val);
}

inline int get_pos_2(int k,int l,int r,int val) {
    if(l==r) return l;
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(cnt[k<<1|1] && tr[k<<1|1] < val) return get_pos_2(k<<1|1,mid+1,r,val);
    else return get_pos_2(k<<1,l,mid,val); 
}

inline pair<int,int> get_Min(int k,int l,int r) {
    if(l==r) return mp(tr[k], l);
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(cnt[k<<1]) return get_Min(k<<1,l,mid);
    else return get_Min(k<<1|1,mid+1,r);
}

inline pair<int,int> get_Max(int k,int l,int r) {
    if(l==r) return mp(tr[k], l);
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(cnt[k<<1|1]) return get_Max(k<<1|1,mid+1,r);
    else return get_Max(k<<1,l,mid);
}

inline void insert(int k,int l,int r,int pos,int val) {
    if(l==r) {
        tr[k] = Min[k] = Max[k] = val;
        cnt[k] = 1; return;
    }
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(pos <= mid) insert(k<<1,l,mid,pos,val);
    else insert(k<<1|1,mid+1,r,pos,val);
    updata(k);
}

inline void del(int k,int l,int r,int pos)  {
    if(l==r) {
        tr[k] = n;
        Min[k] = Max[k] = 0;
        cnt[k] = 0;
        return;
    }
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(pos <= mid) del(k<<1,l,mid,pos);
    else del(k<<1|1,mid+1,r,pos);
    updata(k);
}

inline void change(int k,int l,int r,int x,int y,int val) {
    if(!cnt[k]) return;
    if(l==x && r==y) {
        Min[k] += val;
        Max[k] += val;
        tr[k] += val;
        lazy[k] += val;
        return;
    }
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(y <= mid) change(k<<1,l,mid,x,y,val);
    else if(x > mid) change(k<<1|1,mid+1,r,x,y,val);
    else change(k<<1,l,mid,x,mid,val), change(k<<1|1,mid+1,r,mid+1,y,val);
    updata(k);
}

int opt[N], depth, a[N];

int main() {
//  freopen("splay.in","r",stdin);
//  freopen("splay.out","w",stdout);
    m = read();
    for(int i=0;i<m;++i) {
        opt[i] = read();
        if(opt[i] == 1) b[++n].x = read(), b[n].id = n;
    }
    sort(b+1,b+n+1);
    pair <int,int> tt;
    for(int i=1;i<=n;++i) a[b[i].id] = i;
    ++n; int cnt = 0;
    memset(tr, 0x3f, sizeof tr);
    for(int i=0;i<m;++i) {
        if(opt[i] == 1) {
            cnt ++;
            int tmp1 = find_pre(1, 0, n, a[cnt]);
            int tmp2 = find_nxt(1, 0, n, a[cnt]);
            insert(1, 0, n, a[cnt], max(tmp1,tmp2)+1);
            depth = max(tmp1, tmp2) + 1;
        }
        else if(opt[i] == 2 || opt[i] == 4) {
            tt = get_Min(1, 0, n);
            del(1, 0, n, tt.sec);
            int pos = get_pos_1(1, 0, n, tt.fir);
            change(1, 0, n, pos, n, 1);
            if(opt[i] == 4) 
                change(1, 0, n, 0, n, -1);
            else  insert(1, 0, n, tt.sec, 1);
            depth = tt.fir;
        } 
        else {
            tt = get_Max(1, 0, n);
            del(1, 0, n, tt.sec);
            int pos = get_pos_2(1, 0, n, tt.fir);
            change(1, 0, n, 0, pos, 1);
            if(opt[i] == 5) 
                change(1, 0, n, 0, n, -1);
            else  insert(1, 0, n, tt.sec, 1);   
            depth = tt.fir;
        }
        print(depth);
    }
    io::flush();
}


Title - Artist
0:00

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

TOP