A simple Blog for wyx I've been down the bottle hoping.
4864: [BeiJing 2017 Wc]神秘物质 Splay
发表于: | 分类: Oi | 评论:0 | 阅读:57

清晨的练手题【捂脸

对于前两个操作显然是随便搞搞就行了……

第三个操作必然对应着区间的最大值减去区间的最小值原因不用我说吧

第四个看起来非常玄妙,但是你自己想想就会发现只有相邻的两个元素可能对答案有贡献,原因是对于任意一个二元组$<Min,Max>$表示两个数字中较小的和较大的

显然再加入一个数字更新只会让$Min$更小或者$Max$更大,不会让$Max-Min$更小

然后就是傻*题了

不过有一些比较玄妙的细节可能需要注意一下,一个是哨兵节点的初始化问题,另外一个则是对于第四个操作,由于我们维护的是 $a_i-a_{i-1}$所以对于区间 $[L,R]$, $a_L-a_{L-1}$ 不在答案的集合中,我们提取的区间就是 $[L+1,R]$

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 2e5+5;
const int inf = 0x3f3f3f3f;
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 sz, fa[N];
int ch[N][2], val[N], Min[N], Max[N], ans[N], size[N], root, a[N], val2[N];

inline void updata(int k) {
    size[k] = 1;
    Min[k] = Max[k] = val[k];
    ans[k] = val2[k];
    if(ch[k][0]) {
        int p = ch[k][0];
        Min[k] = min(Min[k], Min[p]);
        Max[k] = max(Max[k], Max[p]);
        ans[k] = min(ans[k], ans[p]);
        size[k] += size[p];
    }
    if(ch[k][1]) {
        int p = ch[k][1];
        Min[k] = min(Min[k], Min[p]);
        Max[k] = max(Max[k], Max[p]);
        ans[k] = min(ans[k], ans[p]);
        size[k] += size[p];
    }
}

inline void rotate(int x) {
    int y = fa[x], z = (ch[y][1] == x);
    ch[y][z] = ch[x][!z], fa[ch[y][z]] = y;
    ch[x][!z] = y; fa[x] = fa[y]; fa[y] = x;
    ch[fa[x]][ch[fa[x]][1] == y] = x;
    updata(y); updata(x);
}

inline void splay(int x,int w) {
    while(fa[x] != w) {
        int y = fa[x], z = fa[y];
        if(z == w) rotate(x);
        else if((ch[y][1] == x) == (ch[z][1] == y)) rotate(y), rotate(x);
        else rotate(x), rotate(x);
    }
    if(!w) root = x;
}

inline int find(int x,int kth) {
    int tmp = size[ch[x][0]];
    if(tmp >= kth) return find(ch[x][0], kth);
    else if(tmp+1 == kth) return x;
    else return find(ch[x][1], kth-tmp-1);
}

inline void newnode(int &k,int V,int F) {
    k = ++sz;
    size[k] = 1;
    val[k] = Min[k] = Max[k] = V;
    fa[k] = F;
}

inline void build(int &k,int L,int R,int F) {
    if(L > R) return;
    int mid = (L+R) >> 1;
    newnode(k, a[mid], F);
    val2[k] = ans[k] = abs(a[mid] - a[mid-1]);
    build(ch[k][0], L, mid-1, k);
    build(ch[k][1], mid+1, R, k);
    updata(k);
} 

char str[10];

int main() {
//f freopen("tt.in","r",stdin);
    int n = read(), m = read();
    for(int i=1;i<=n;++i) a[i] = read();
    newnode(root, inf, 0);
    newnode(ch[root][1], inf, root);
    int tmp = ch[root][1];
    build(ch[tmp][0], 1, n, tmp);
    updata(tmp);
    updata(root);
    for(int i=1;i<=m;++i) {
        scanf("%s",str+1);
        if(str[1] == 'i') {
            int x = read(), val = read();
            splay(find(root, x+1), 0);
            splay(find(root, x+2), root);
            int tmp = ch[root][1];
            newnode(ch[tmp][0], val, tmp);
            val2[ch[tmp][0]] = ans[ch[tmp][0]] = abs(val - ::val[root]);
            val2[ch[root][1]] = ans[ch[root][1]] = abs(::val[ch[root][1]] - val);
            updata(ch[root][1]);
            updata(root);
        }
        else if(str[2] == 'e') {
            int x = read(), val = read();
            splay(find(root,x), 0);
            splay(find(root,x+3), root);
            int tmp = ch[root][1];
            newnode(ch[tmp][0], val, tmp);
            val2[ch[tmp][0]] = ans[ch[tmp][0]] = abs(val - ::val[root]);
            val2[ch[root][1]] = ans[ch[root][1]] = abs(::val[ch[root][1]] - val);
            updata(ch[root][1]);
            updata(root);
        }
        else if(str[2] == 'a') {
            int x = read(), y = read();
            splay(find(root,x),0);
            splay(find(root,y+2), root);
            int tmp = ch[root][1];
            tmp = ch[tmp][0];
            printf("%d\n", Max[tmp]-Min[tmp]);
        }
        else {
            int x = read(), y = read();
            splay(find(root, x+1), 0);
            splay(find(root, y+2), root);
            int tmp = ch[root][1]; tmp = ch[tmp][0];
            printf("%d\n", ans[tmp]);
        }
    }
}

Title - Artist
0:00

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

TOP