2019年CCPC网络赛 HDU 6703 array【权值线段树】

题目大意：给出一个n个元素的数组A，A中所有元素都是不重复的[1,n]。
有两种操作：
1.将pos位置的元素+1e7
2.查询不属于[1,r]中的最小的>=k的值。
强制在线。

题解
因为数组中的值唯一，且在1到n的范围内，而询问的r和k也在1到n的范围内。所以对于任意一个被操作1修改过的值都不会成为询问的答案，而询问的结果也必然在k到n＋1的范围内。因为没有被修改过值是唯一的，所以可以建立权值线段树，维护权值区间内的值所在下标的最大值。而询问则转化为不小于k的值里面，下标超过r的最小权值是多少。如何处理询问呢，一种较为暴力的解法是直接在线段树上询问权值在k到n+1的范围内第一个下标超过r的权值是多少。但复杂度可能会被卡，需要减枝。再加上一个额外的判断就可以了，就是在递归查询完左子树内存不存在大于r的下标之后，如果不存在，则先看一下右子树内的下标的最大值是否大于r。如果不大于r，则不必再进入右子树内查询，否则答案一定在右子树内。在进左子树之前也利用同样的判断条件来判断是否有必要进入左子树，这样做可以保证单次查询的复杂度是O(log n) 的。而对于操作1，则等价于修改某个权值的下标为无穷大。操作复杂度也是O（log n )的。综上所述，得到了一个复杂度为O( m * log n )的在线算法，可以较快地通过此题。

/*HDU 6703 array

权值线段树 在线处理

2019/08/27 12：00

*/

#pragma GCC optimize(3,"Ofast","inline")      //G++

#pragma comment(linker, "/STACK:102400000,102400000")

#pragma GCC optimize(2)

#include<bits/stdc++.h>

#include <functional>

#define TEST freopen("in.txt","r",stdin);

#define mem(a,x) memset(a,x,sizeof(a))

#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;

typedef unsigned long long ull; // %llu

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod=1e9+;

const int INF = 1e6+;

const int maxn = 1e5+;

int n,q;

struct node

{

    int l,r,pos;    //建立权值线段树 维护区间下标最大值

} t[*maxn];

int a[maxn];

void build(int l,int r,int o)   //一颗大树由此而生

{

    t[o].l=l;

    t[o].r=r;

    if(l==r)

    {

        return ;

    }

    int mid=(l+r)>>;

    build(l,mid,o<<);

    build(mid+,r,o<<|);

}

void pushup(int o)          //自如其名 pushup

{

    t[o].pos=max(t[o<<].pos,t[o<<|].pos);

}

void add(int o,int x,int pos)   //添加操作 维护区间下标最大值

{

    if(t[o].l==t[o].r&&t[o].l==x)

    {

        t[o].pos=pos;

        return ;

    }

    int mid=(t[o].l+t[o].r)>>;

    if(x<=mid)

        add(o<<,x,pos);

    else

        add(o<<|,x,pos);

    pushup(o);

}

int qurey(int o,int l,int r,int ask)

{

    if(t[o].l==t[o].r)      //到叶子节点判读答案是否成立

    {

        if(t[o].pos>ask)

            return t[o].l;

       else

           return INF;

    }

    if(t[o].l==l&&t[o].r==r)        //在当期节点区间时 需要根据左右子树的pos值判读下一步往哪边走（剪枝）

    {

        if(t[o<<].pos>ask)

        {

            return qurey(o<<,l,(l+r)>>,ask);

        }

        else if(t[o<<|].pos>ask)

        {

            return qurey(o<<|,(l+r)>>|,r,ask);

        }

       else

           return INF;

    }

    int mid=(t[o].l+t[o].r)>>;         //熟悉的操作

    if(r<=mid)

    {

        return qurey(o<<,l,r,ask);     //锁定区间

    }

    else if(l>mid)

    {

        return qurey(o<<|,l,r,ask);   //还是锁定区间

    }

    else

    {

        return min(qurey(o<<,l,mid,ask),qurey(o<<|,mid+,r,ask));        //锁定区间 答案即可能在左子树也可能在右子树 所以取左右子树中最小的值（有可能左子树返回INF）

    }

}

void init()     //输入

{

    scanf("%d%d",&n,&q);

    build(,+n,);

    for(int i=; i<=n; i++)

    {

        scanf("%d",&a[i]);

        add(,a[i],i);

    }

    add(,n+,INF);

}

void solve()        //解决

{

    int op,last=;      //在线处理

    while(q--)

    {

        scanf("%d",&op);

        if(op==)

        {

            int pos;

            scanf("%d",&pos);

            pos^=last;

            add(,a[pos],INF);

        }

        else

        {

            int r,k;

            scanf("%d%d",&r,&k);

            r^=last,k^=last;

            last=qurey(,k,n+,r);

            printf("%d\n",last);

        }

    }

}

int main()

{

//    TEST

    int T;

    scanf("%d",&T);

    while(T--)

    {

        mem(t,);

        init();

        solve();

    }

}

巴特西

2019年CCPC网络赛 HDU 6703 array【权值线段树】

最新文章

热门文章