DQS DQS

HIT Summer Training Day9 Splay

in 算法,Splay,数据结构,模拟赛read (180) 文章转载请注明来源!

码Splay到手酸……四题蒟蒻

都会做,写不出来,这是最气的。

果然我适合当嘴巴选手。


A : LYDSY - 3223

splay区间翻转

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;


struct node
{
    node *f,*ch[2];
    int v,sz;
    bool rev;

    void setc(node *x,int d) { (ch[d] = x) -> f = this; }
    int dir() { return f -> ch[1] == this; }
    void maintain()
    {
        sz = ch[0] -> sz + 1 + ch[1] -> sz;
    }
    void pushdown();
}T[SZ], *root, *null;

int Tcnt = 0;

node* newnode(int x,node *fa)
{
    node *k = T + Tcnt ++;
    k -> f = fa;
    k -> ch[0] = k -> ch[1] = null;
    k -> v = x;
    k -> rev = 0;
    return k;
}

void pushrev(node *p)
{
    if(p == null) return ;
    swap(p -> ch[0],p -> ch[1]);
    p -> rev ^= 1;
}

void node :: pushdown()
{
    if(this == null) return ;
    if(rev)
        pushrev(ch[0]),pushrev(ch[1]),rev = 0;
}

void rotate(node *p)
{
    node *fa = p -> f;
    int d = p -> dir();
    fa -> f -> setc(p,fa -> dir());
    fa -> setc(p -> ch[d ^ 1],d); fa -> maintain();
    p -> setc(fa,d ^ 1); p -> maintain();
    if(fa == root) root = p;
}

void splay(node *p,node *rt = null)
{
    p -> pushdown();
    while(p -> f != rt)
    {
        if(p -> f -> f == rt) rotate(p);
        else
        {
            p -> f -> f -> pushdown(); p -> f -> pushdown(); p -> pushdown();
            if(p -> dir() == p -> f -> dir())
                rotate(p -> f),rotate(p);
            else
                rotate(p),rotate(p);
        }
    }
    p -> maintain();
}

node* find(int k)
{
    node *p = root;
    while(p != null)
    {
        p -> pushdown();
        int x = p -> ch[0] -> sz + 1;
        if(x == k) return p;
        if(k > x) k -= x,p = p -> ch[1];
        else p = p -> ch[0];
    }
}


void build(node* &p,int l,int r,node *fa)
{
    if(l > r) return ;
    int mid = l + r >> 1;
    p = newnode(mid,fa);
    build(p -> ch[0],l,mid - 1,p);
    build(p -> ch[1],mid + 1,r,p);
    p -> maintain();
}


void reverse(int l,int r)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    pushrev(root -> ch[1] -> ch[0]);
    root -> ch[1] -> maintain();
    root -> maintain();
}

void print_ans(node *p)
{
    if(p == null) return ;
    p -> pushdown();
    print_ans(p -> ch[0]);
    printf("%d ",p -> v);
    print_ans(p -> ch[1]);
}


void init()
{
    null = newnode(0,null);
    null -> sz = 0;

    root = newnode(0,null);
    root -> ch[1] = newnode(0,root);
    root -> maintain();
}

int main()
{
    int n,m;
    init();
    scanf("%d%d",&n,&m);
    build(root -> ch[1] -> ch[0],1,n,root -> ch[1]);
    root -> ch[1] -> maintain();
    root -> maintain();

    for(int i = 1;i <= m;i ++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        reverse(l,r);
    }
    splay(find(1)); splay(find(n + 2),root);
    print_ans(root -> ch[1] -> ch[0]);
    return 0;
}


B : LYDSY - 3224

板子题,当年写过不知道多少遍

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;


struct node
{
    node *f,*ch[2];
    int v,sz,cnt;

    void setc(node *x,int d) { (ch[d] = x) -> f = this; }
    int dir() { return f -> ch[1] == this; }
    void maintain()
    {
        sz = ch[0] -> sz + cnt + ch[1] -> sz;
    }
    int cmp(int x)
    {
        if(x == v) return -1;
        return x < v ? 0 : 1;
    }
    void pushdown() {} ;
}T[SZ], *root, *null;

int Tcnt = 0;

node* newnode(int x,node *fa)
{
    node *k = T + Tcnt ++;
    k -> f = fa;
    k -> ch[0] = k -> ch[1] = null;
    k -> v = x;
    k -> cnt = k -> sz = 1;
    return k;
}

void rotate(node *p)
{
    node *fa = p -> f;
    int d = p -> dir();
    fa -> f -> setc(p,fa -> dir());
    fa -> setc(p -> ch[d ^ 1],d); fa -> maintain();
    p -> setc(fa,d ^ 1); p -> maintain();
}

void splay(node *p,node *rt = null)
{
    p -> pushdown();
    while(p -> f != rt)
    {
        if(p -> f -> f == rt) rotate(p);
        else
        {
            p -> f -> f -> pushdown(); p -> f -> pushdown(); p -> pushdown();
            if(p -> dir() == p -> f -> dir())
                rotate(p -> f),rotate(p);
            else
                rotate(p),rotate(p);
        }
    }
    p -> maintain();
}

void insert(node *p,int x,node* &root)
{
    if(root == null) { root = newnode(x,null); return ; }
    while(p != null)
    {
        p -> sz ++;
        int d = p -> cmp(x);
        if(d == -1) { p -> cnt ++; break; }
        if(p -> ch[d] == null)
        {
            p -> ch[d] = newnode(x,p);
            p = p -> ch[d];
            break;
        }
        p = p -> ch[d];
    }
    splay(p);
    while(root -> f != null) root = root -> f;
}

void erase(node *p,int x,node* &root)
{
    while(p != null)
    {
        p -> sz --;
        int d = p -> cmp(x);
        if(d == -1) { p -> cnt --; break;}
        p = p -> ch[d];
    }
    if(p -> cnt) return ;
    splay(p);
    while(root -> f != null) root = root -> f;
    if(p -> ch[1] == null) { root = p -> ch[0],root -> f = null; return ; }
    if(p -> ch[0] == null) { root = p -> ch[1],root -> f = null; return ; }
    p = p -> ch[0];
    while(p -> ch[1] != null) p = p -> ch[1];
    splay(p,root);
    p -> ch[1] = root -> ch[1]; p -> ch[1] -> f = p;
    p -> f = null; p -> maintain();
    root = p;
}



int ask_num(int k)
{
    node *p = root;
    while(p != null)
    {
        int l = p -> ch[0] -> sz + 1;
        int r = p -> ch[0] -> sz + p -> cnt;
        if(l <= k && k <= r) return p -> v;
        if(k > r) k -= r,p = p -> ch[1];
        else p = p -> ch[0];
    }
}

int ask_rank(int x)
{
    node *p = root;
    int ans = 0;
    while(p != null)
    {
        int d = p -> cmp(x);
        if(d == -1) return ans + p -> ch[0] -> sz + 1;
        if(d == 1) ans += p -> ch[0] -> sz + p -> cnt;
        p = p -> ch[d];
    }
    return -1;
}

int ask_pre(int x)
{
    node *p = root;
    int ans = 0;
    while(p != null)
    {
        if(p -> v < x)
            ans = p -> v,p = p -> ch[1];
        else
            p = p -> ch[0];
    }
    return ans;
}

int ask_suf(int x)
{
    node *p = root;
    int ans = 0;
    while(p != null)
    {
        if(p -> v > x)
            ans = p -> v,p = p -> ch[0];
        else
            p = p -> ch[1];
    }
    return ans;
}



void init()
{
    null = newnode(-INF,null);
    null -> sz = null -> cnt = 0;
    root = null;
}

int main()
{
    int n,m;
    init();
    scanf("%d",&n);
    while(n --)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt == 1)
            insert(root,x,root);
        if(opt == 2)
            erase(root,x,root);
        if(opt == 3)
            printf("%d\n",ask_rank(x));
        if(opt == 4)
            printf("%d\n",ask_num(x));
        if(opt == 5)
            printf("%d\n",ask_pre(x));
        if(opt == 6)
            printf("%d\n",ask_suf(x));
    }
    return 0;
}


C : LYDSY - 4864

定义区间极差为 区间最大值-区间最小值。

给一个序列,支持区间删除两个数,插入一个数,询问一个区间内的所有区间的区间极差的最大值和最小值。

区间越大,最大值不会变小,最小值不会变大,所以区间极差取最大时就是取整个区间,最小时就说取某两个相邻元素的差值。

记录左区间最右边的元素,右区间最左边的元素,合并答案时和权值v作差更新。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;


struct node
{
    node *f,*ch[2];
    int v,sz,mx,mi,maxn,minn,lx,rx;

    void setc(node *x,int d) { (ch[d] = x) -> f = this; }
    int dir() { return f -> ch[1] == this; }
    void maintain();

    void pushdown();
}T[SZ], *root, *null;

int sa[SZ];
int Tcnt1 = 0,Tcnt2 = 0;

node* newnode(int x,node *fa)
{
    int cnt;
    if(Tcnt2) cnt = sa[Tcnt2 --];
    else cnt = Tcnt1 ++;
    node *k = T + cnt;
    k -> f = fa;
    k -> ch[0] = k -> ch[1] = null;
    k -> v = k -> lx = k -> rx = k -> minn = k -> maxn = x;
    k -> mx = -INF;
    k -> mi = INF;
    k -> sz = 1;
    return k;
}

void node :: maintain()
{
    sz = ch[0] -> sz + 1 + ch[1] -> sz;
    if(ch[0] != null) lx = ch[0] -> lx;
    else lx = v;
    if(ch[1] != null) rx = ch[1] -> rx;
    else rx = v;
    minn = min(min(ch[1] -> minn,ch[0] -> minn),v);
    maxn = max(max(ch[1] -> maxn,ch[0] -> maxn),v);
    int d1 = ch[0] == null ? INF : abs(v - ch[0] -> rx);
    int d2 = ch[1] == null ? INF : abs(v - ch[1] -> lx);
    mi = min(min(ch[0] -> mi,ch[1] -> mi),min(d1,d2));
    mx = max(max(ch[0] -> mx,ch[1] -> mx),maxn - minn);
}


void node :: pushdown()
{
    if(this == null) return ;
}

void rotate(node *p)
{
    node *fa = p -> f;
    int d = p -> dir();
    fa -> f -> setc(p,fa -> dir());
    fa -> setc(p -> ch[d ^ 1],d); fa -> maintain();
    p -> setc(fa,d ^ 1); p -> maintain();
    if(fa == root) root = p;
}

void splay(node *p,node *rt = null)
{
    p -> pushdown();
    while(p -> f != rt)
    {
        if(p -> f -> f == rt) rotate(p);
        else
        {
            p -> f -> f -> pushdown(); p -> f -> pushdown(); p -> pushdown();
            if(p -> dir() == p -> f -> dir())
                rotate(p -> f),rotate(p);
            else
                rotate(p),rotate(p);
        }
    }
    p -> maintain();
}

node* find(int k)
{
    node *p = root;
    while(p != null)
    {
        p -> pushdown();
        int x = p -> ch[0] -> sz + 1;
        if(x == k) return p;
        if(k > x) k -= x,p = p -> ch[1];
        else p = p -> ch[0];
    }
}


int num[SZ];

void build(node* &p,int l,int r,node *fa)
{
    if(l > r) return ;
    int mid = l + r >> 1;
    p = newnode(num[mid],fa);
    build(p -> ch[0],l,mid - 1,p);
    build(p -> ch[1],mid + 1,r,p);
    p -> maintain();
//    cout << l << " " << r << " : " << endl;
//    printf("%d %d %d %d\n",p -> lx,p -> rx,p -> mx,p -> mi);
}


void insert(int pos,int tot)
{
    pos ++;
    splay(find(pos)); splay(find(pos + 1),root);
    build(root -> ch[1] -> ch[0],1,tot,root -> ch[1]);
    root -> ch[1] -> maintain();
    root -> maintain();
//    cout << root ->v << " " << root ->ch[1] -> v << endl;
//    printf("%d %d %d %d\n",root -> ch[1] -> lx,root -> ch[1] -> rx,root -> ch[1] -> mx,root -> ch[1] -> mi);
//    printf("%d %d %d %d\n",root -> lx,root -> rx,root -> mx,root -> mi);
}


void del(node *p)
{
    if(p == null) return ;
    sa[++ Tcnt2] = p - T;
    del(p -> ch[0]);
    del(p -> ch[1]);
}

void erase(int l,int r)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    del(root -> ch[1] -> ch[0]); root -> ch[1] -> ch[0] = null;
    root -> ch[1] -> maintain();
    root -> maintain();
}



int ask_max(int l,int r)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    return root -> ch[1] -> ch[0] -> mx;
}

int ask_min(int l,int r)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    return root -> ch[1] -> ch[0] -> mi;
}


void init()
{
    null = newnode(-INF,null);
    null -> sz = 0;
    root = newnode(-INF,null);
    root -> ch[1] = newnode(-INF,root);
    root -> minn = root -> ch[1] -> minn = null -> minn = INF;
    root -> maxn = root -> ch[1] -> maxn = null -> maxn = -INF;
    root -> mi = root -> ch[1] -> mi = null -> mi = INF;
    root -> mx = root -> ch[1] -> mx = null -> mx = -INF;
    root -> maintain();
}

int main()
{
    int n,m;
    init();
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%d",&num[i]);
    insert(0,n);
    while(m --)
    {
        char opt[20];
        int x,y;
        scanf("%s%d%d",opt,&x,&y);
        if(opt[1] == 'e') //merge
            erase(x,x + 1),num[1] = y,insert(x - 1,1);
        if(opt[1] == 'n') //insert
            num[1] = y,insert(x,1);
        if(opt[1] == 'a') //max
            printf("%d\n",ask_max(x,y));
        if(opt[1] == 'i') //min
            printf("%d\n",ask_min(x,y));
    }
    return 0;
}
/*
4 233
5 8 10 2
max 1 3
min 1 3
max 2 4
merge 2 5
max 1 3
min 1 3

5 5 2

*/


D : LYDSY - 1500

当年的噩梦……不知道写了多少遍……

Splay维护区间的板子题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;


struct node
{
    node *f,*ch[2];
    int v,sz,lx,rx,mx,sum;
    bool rev,same;

    void setc(node *x,int d) { (ch[d] = x) -> f = this; }
    int dir() { return f -> ch[1] == this; }
    void maintain()
    {
        sz = ch[0] -> sz + 1 + ch[1] -> sz;
        sum = ch[0] -> sum + v + ch[1] -> sum;
        lx = max(ch[0] -> lx,ch[0] -> sum + v + max(ch[1] -> lx,0));
        rx = max(ch[1] -> rx,ch[1] -> sum + v + max(ch[0] -> rx,0));
        mx = max(max(ch[0] -> mx,ch[1] -> mx),max(ch[0] -> rx,0) + v + max(ch[1] -> lx,0));
    }
    void pushdown();
}T[SZ], *root, *null;

int sa[SZ];
int Tcnt1 = 0,Tcnt2 = 0;

node* newnode(int x,node *fa)
{
    int cnt;
    if(Tcnt2) cnt = sa[Tcnt2 --];
    else cnt = Tcnt1 ++;
    node *k = T + cnt;
    k -> f = fa;
    k -> ch[0] = k -> ch[1] = null;
    k -> v = k -> lx = k -> rx = k -> mx = k -> sum = x;
    k -> rev = k -> same = 0;
    k -> sz = 1;
    return k;
}

void pushrev(node *p)
{
    if(p == null) return ;
    swap(p -> ch[0],p -> ch[1]);
    swap(p -> lx,p -> rx);
    p -> rev ^= 1;
}

void pushsame(node *p,int x)
{
    if(p == null) return ;
    p -> v = x;
    p -> sum = x * p -> sz;
    p -> lx = p -> rx = p -> mx = max(p -> v,p -> sum);
    p -> same = 1;
}

void node :: pushdown()
{
    if(this == null) return ;
    if(rev)
        pushrev(ch[0]),pushrev(ch[1]),rev = 0;
    if(same)
        pushsame(ch[0],v),pushsame(ch[1],v),same = 0;
}

void rotate(node *p)
{
    node *fa = p -> f;
    int d = p -> dir();
    fa -> f -> setc(p,fa -> dir());
    fa -> setc(p -> ch[d ^ 1],d); fa -> maintain();
    p -> setc(fa,d ^ 1); p -> maintain();
    if(fa == root) root = p;
}

void splay(node *p,node *rt = null)
{
    p -> pushdown();
    while(p -> f != rt)
    {
        if(p -> f -> f == rt) rotate(p);
        else
        {
            p -> f -> f -> pushdown(); p -> f -> pushdown(); p -> pushdown();
            if(p -> dir() == p -> f -> dir())
                rotate(p -> f),rotate(p);
            else
                rotate(p),rotate(p);
        }
    }
    p -> maintain();
}

node* find(int k)
{
    node *p = root;
    while(p != null)
    {
        p -> pushdown();
        int x = p -> ch[0] -> sz + 1;
        if(x == k) return p;
        if(k > x) k -= x,p = p -> ch[1];
        else p = p -> ch[0];
    }
}


int num[SZ];

void build(node* &p,int l,int r,node *fa)
{
    if(l > r) return ;
    int mid = l + r >> 1;
    p = newnode(num[mid],fa);
    build(p -> ch[0],l,mid - 1,p);
    build(p -> ch[1],mid + 1,r,p);
    p -> maintain();
}


void insert(int pos,int tot)
{
    pos ++;
    for(int i = 1;i <= tot;i ++) scanf("%d",&num[i]);
    splay(find(pos)); splay(find(pos + 1),root);
    build(root -> ch[1] -> ch[0],1,tot,root -> ch[1]);
    root -> ch[1] -> maintain();
    root -> maintain();
}

void del(node *p)
{
    if(p == null) return ;
    sa[++ Tcnt2] = p - T;
    del(p -> ch[0]);
    del(p -> ch[1]);
}

void erase(int l,int r)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    del(root -> ch[1] -> ch[0]); root -> ch[1] -> ch[0] = null;
    root -> ch[1] -> maintain();
    root -> maintain();
}

void change(int l,int r,int v)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    pushsame(root -> ch[1] -> ch[0],v);
    root -> ch[1] -> maintain();
    root -> maintain();
}

void reverse(int l,int r)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    pushrev(root -> ch[1] -> ch[0]);
    root -> ch[1] -> maintain();
    root -> maintain();
}

int ask_sum(int l,int r)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    return root -> ch[1] -> ch[0] -> sum;
}

int ask_ans(int l,int r)
{
    l ++; r ++;
    splay(find(l - 1)); splay(find(r + 1),root);
    return root -> ch[1] -> ch[0] -> mx;
}


void init()
{
    null = newnode(-INF,null);
    null -> sz = 0;

    root = newnode(-INF,null);
    root -> ch[1] = newnode(-INF,root);
    root -> sum = root -> ch[1] -> sum = null -> sum = 0;
    root -> maintain();
}

int main()
{
    int n,m;
    init();
    scanf("%d%d",&n,&m);
    insert(0,n);
    while(m --)
    {
        char opt[20];
        scanf("%s",opt);
        if(opt[2] == 'S')
        {
            int pos,tot;
            scanf("%d%d",&pos,&tot);
            insert(pos,tot);
        }
        if(opt[2] == 'L')
        {
            int pos,tot;
            scanf("%d%d",&pos,&tot);
            int l = pos,r = pos + tot - 1;
            erase(l,r);
        }
        if(opt[2] == 'K')
        {
            int pos,tot,c;
            scanf("%d%d%d",&pos,&tot,&c);
            int l = pos,r = pos + tot - 1;
            change(l,r,c);
        }
        if(opt[2] == 'V')
        {
            int pos,tot;
            scanf("%d%d",&pos,&tot);
            int l = pos,r = pos + tot - 1;
            reverse(l,r);
        }
        if(opt[2] == 'T')
        {
            int pos,tot;
            scanf("%d%d",&pos,&tot);
            int l = pos,r = pos + tot - 1;
            printf("%d\n",ask_sum(l,r));
        }
        if(opt[2] == 'X')
        {
            printf("%d\n",ask_ans(1,root -> sz - 2));
        }
    }
    return 0;
}


E : LYDSY - 2809

给一棵树,每个节点有权值ci和li。给定值m,让从一个子树中选取一些节点,使它们的ci之和小于等于m。定义权值为选取节点个数*子树根节点的li,求这个权值最大值。

对于每个子树,li是确定的,所以我们要尽量选多的节点使它们ci之和小于等于m,于是我们一定是选ci小的那些。递归回溯时需要把儿子的答案合并到父亲上,可以启发式合并。

具体来说,每个点开一个堆维护当前子树的bi小的那些节点,让它们的权值和不超过m。合并后如果大于m,则从权值大的点开始pop,直到小于等于m为止。

堆可以用set,当然左偏树最好了。

这样每个点至多被pop一次,加上启发式合并,复杂度为$O(nlog^2n)$

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const LL INF = 1000000000000000010;


int fa[SZ],n,m;
int head[SZ],nxt[SZ],to[SZ],tot = 1;
LL ans = -INF,cost[SZ],val[SZ];

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

int id[SZ];
LL sz[SZ];
priority_queue<LL> q[SZ];

void dfs(int u)
{
    q[id[u]].push(cost[u]);
    sz[id[u]] += cost[u];
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        dfs(v);
        int x = id[u],y = id[v];
        if(q[x].size() > q[y].size())
        {
            sz[x] += sz[y];
            while(q[y].size()) q[x].push(q[y].top()),q[y].pop();
        }
        else
        {
            sz[y] += sz[x],id[u] = y;
            while(q[x].size()) q[y].push(q[x].top()),q[x].pop();
        }
    }
    int x = id[u];
    while(sz[x] > m && q[x].size()) sz[x] -= q[x].top(),q[x].pop();
    ans = max(ans,val[u] * (LL)q[x].size());
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) id[i] = i;
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d%lld%lld",&fa[i],&cost[i],&val[i]);
        if(fa[i]) build(fa[i],i);
    }
    for(int i = 1;i <= n;i ++)
        if(fa[i] == 0)
            dfs(i);
    printf("%lld\n",ans);
    return 0;
}


F : LYDSY - 3196

讲道理,我还对一年半以前我写的那个线段树套splay的卡常耿耿于怀

于是考场上决定撸分块,结果因为E会BB不会写浪费了许多时刻,这个题还没调试就结束了……

分块竟然挺好写!!改天学习一个分块的姿势。

后来改的时候发现全是小毛病,简直了……

把vector改掉,然后加手读,bzoj卡线过……人傻自带大常数

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;

const int SZ = 100010;
const int INF = 1000000010;

int n,m,B,A;
int g[5010][5010],Len[SZ];
int L[SZ],R[SZ],id[SZ],a[SZ];

int tmp[SZ],len;

int Min(int x,int y) { return x < y ? x : y; }
int Max(int x,int y) { return x > y ? x : y; }

int ask_rank(int l,int r,int x)
{
    len = 0;
    int ll = id[l],rr = id[r];
    while(l <= r && l <= R[ll])
        tmp[len ++] = a[l],l ++;
    while(l <= r && r >= L[rr])
        tmp[len ++] = a[r],r --;
    int ans = 0;
    if(l <= r)
        for(int i = id[l];i <= id[r];i ++)
            ans += lower_bound(g[i],g[i] + Len[i],x) - g[i];
    sort(tmp,tmp + len);
    //puts("tmp");
//    for(int i = 0;i < tmp.size();i ++)
    //    printf("%d ",tmp[i]); puts("");
    ans += lower_bound(tmp,tmp + len,x) - tmp;
    return ans + 1;
}

int ask_num(int l,int r,int k)
{
/*    for(int i = 1;i <= n;i ++)
    {
        printf("%d %d %d\n",l,r,::l[i]);
        cout << ask_rank(l,r,::l[i]) << endl;
    }*/

    int L = 0,R = 1e8 + 1;
    while(R - L > 1)
    {
        int mid = L + R >> 1;
        int ans = ask_rank(l,r,mid);
//        cout << ::l[mid] << " " << ans << " " << k << endl;
        if(ans <= k) L = mid;
        else R = mid;
    }
    return L;
}

void change(int pos,int k)
{
    int i = id[pos];
    *lower_bound(g[i],g[i] + Len[i],a[pos]) = k;
    a[pos] = k;
    sort(g[i],g[i] + Len[i]);
}

int ask_pre(int l,int r,int x)
{
    int ans = 0;
    int ll = id[l],rr = id[r];
    while(l <= r && l <= R[ll])
    {
        if(a[l] < x) ans = Max(ans,a[l]);
        l ++;
    }
    while(l <= r && r >= L[rr])
    {
        if(a[r] < x) ans = Max(ans,a[r]);
        r --;
    }
    if(l <= r)
        for(int i = id[l];i <= id[r];i ++)
        {
            int d = lower_bound(g[i],g[i] + Len[i],x) - g[i] - 1;
            if(d >= 0)
                ans = Max(ans,g[i][d]);
        }
    return ans;
}

int ask_suf(int l,int r,int x)
{
    int ans = INF;
    int ll = id[l],rr = id[r];
    while(l <= r && l <= R[ll])
    {
        if(a[l] > x) ans = Min(ans,a[l]);
        l ++;
    }
    while(l <= r && r >= L[rr])
    {
        if(a[r] > x) ans = Min(ans,a[r]);
        r --;
    }
    //cout << l << " " << r << " " << ans << endl;
//    for(int i = 0;i < g[id[l]].size();i ++)
//        printf("%d ",g[id[l]][i]); puts("");
    if(l <= r)
        for(int i = id[l];i <= id[r];i ++)
        {
            int d = upper_bound(g[i],g[i] + Len[i],x) - g[i];
        //    cout << d << endl;
            if(d < Len[i])
                ans = Min(ans,g[i][d]);
        }
    return ans;
}

int read()
{
    char a = getchar();
    int n = 0; bool flag = 0;
    while(a > '9' || a < '0') {if(a == '-') flag = 1; a = getchar();}
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar();}
    if(flag) n = -n;
    return n;
}

int main()
{
    //freopen("3196.in","r",stdin);         freopen("3196.out","w",stdout);
    n = read(); m = read();
    B = sqrt(n); A = 0;
    for(int i = 1;i <= n;i ++)
        a[i] = read();

    for(int i = 1;i <= n;i += B)
    {
        A ++;
        L[A] = i,R[A] = Min(n,i + B - 1);
        for(int j = i;j <= Min(n,i + B - 1);j ++)
            g[A][Len[A] ++] = a[j],id[j] = A;
        sort(g[A],g[A] + Len[A]);
    }

    while(m --)
    {
        int opt,l,r,pos,k;
        scanf("%d",&opt);
        if(opt == 1)
            l = read(),r = read(),k = read(),printf("%d\n",ask_rank(l,r,k));
        if(opt == 2)
            l = read(),r = read(),k = read(),printf("%d\n",ask_num(l,r,k));
        if(opt == 3)
            pos = read(),k = read(),change(pos,k);
        if(opt == 4)
            l = read(),r = read(),k = read(),printf("%d\n",ask_pre(l,r,k));
        if(opt == 5)
            l = read(),r = read(),k = read(),printf("%d\n",ask_suf(l,r,k));
    }
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法Splay数据结构模拟赛
最后由DQS修改于2017-08-11 00:35
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆