HDU-6703-array-2019CCPC选拔赛

我TM真是一个弟弟。。。

题意：

给出一串1-N的数字

你每次可以把某个位置的值+1000000

或者找一个值，所有a[1]...a[r]序列的数都不能等于这个值，并且这个值>w

当时比赛觉得肯定是树套树，待修区间第K大，一想不会就自闭了。。。

其实反过来想，如果a[1]....a[r]序列的数都不能等于这个值，那么其实我们可以从a[r+1]....a[n]找到第一个值>=w

但是考虑本题带修改，你会发现这个值加的非常大，大于n，那么一旦某个位置加了这个值，这个值就不再产生贡献

相当于把这个值删掉。

我们考虑把这些值保存起来，因为一旦这个值被删掉，那么意味着，它是有可能作为答案的。

我们建立一颗主席树，并实现查询大于>=w的数的个数，以及区间第K小的操作，并把删除的数放入set里面

我们在区间内部查找>=w的个数，如果这个值为0，我们查询删除的数里面是否有比w大的，如果没有的话，答案就是n+1，否则就是set里面第一个大于w的数，可用lower_bound实现

考虑不为0，我们查第r-l+1+num(大于num的个数)这样就能区间内部查到第一个>=w的数字

再在set里面查询第一个>=w的数字，因为可能1-r区间内被删除的数且这个数比r+1到n区间内>=w的数答案更优秀

两者取最小值即可。

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<set>

using namespace std;

const int maxx = 2e5+;

struct node{

  int l,r;

  int cnt;

}tree[maxx*];

int root[maxx];

int cnt;

set<int>s;

int a[maxx];

void inserts(int l,int r,int pre,int &now,int pos){

     now=++cnt;

     tree[now]=tree[pre];

     tree[now].cnt++;

     if(l==r){

        return ;

     }

     int mid=(l+r)>>;

     if (pos<=mid){

        inserts(l,mid,tree[pre].l,tree[now].l,pos);

     }else{

        inserts(mid+,r,tree[pre].r,tree[now].r,pos);

     }

}

int query(int L,int R,int l,int r,int w){

    if (l==r){

        return tree[R].cnt-tree[L].cnt;

    }

    int mid=(l+r)>>;

    if (w<=mid){

        return tree[tree[R].r].cnt-tree[tree[L].r].cnt+query(tree[L].l,tree[R].l,l,mid,w);

    }else {

        return query(tree[L].r,tree[R].r,mid+,r,w);

    }

}

int Kth(int L,int R,int l,int r,int k){

     if (l==r){

        return l;

     }

     int mid=(l+r)>>;

     int s=tree[tree[R].l].cnt-tree[tree[L].l].cnt;

     if (s>=k){

        return Kth(tree[L].l,tree[R].l,l,mid,k);

     }else {

        return Kth(tree[L].r,tree[R].r,mid+,r,k-s);

     }

}

int main(){

  int t;

  int n,m;

  scanf("%d",&t);

  while(t--){

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

     s.clear();

     memset(tree,,sizeof(tree));

     memset(root,,sizeof(root));

     cnt=;

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

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

        inserts(,n,root[i-],root[i],a[i]);

     }

     int op;

     int r,w,pos=;

     int ans=;

     while(m--){

        scanf("%d",&op);

        if (op==){

           scanf("%d",&pos);

           pos=pos^ans;

           s.insert(a[pos]);

        }else {

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

          r=r^ans;

          w=w^ans;

          int num=query(root[r],root[n],,n,w);

          if (num==){

            auto it=s.lower_bound(w);

            if (it!=s.end()){

                ans=*it;

                printf("%d\n",*it);

            }else {

                ans=n+;

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

            }

          }else {

            auto it=s.lower_bound(w);

            if (it!=s.end()){

                ans=min(Kth(root[r],root[n],,n,n-r+-num),*it);

            }else {

                ans=Kth(root[r],root[n],,n,n-r+-num);

            }

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

          }

        }

     }

  }

  return ;

}

巴特西

HDU-6703-array-2019CCPC选拔赛

最新文章

热门文章