HDU 6703 CCPC 2019 网络赛 1002 array 可持久化线段树(主席树) + set
可持久化线段树   发布于 2019-08-24   733人围观  1条评论
可持久化线段树   发表于 2019-08-24   733人围观  1条评论

题目大意

给定一个1----n的排列,有以下两种操作:

1.给序列中位置i的数+10000000。

2.询问未在1-----r位置出现过且≥k的最小值。

题目保证1≤k≤ 100000,强制在线。

题解

这场CCPC网络赛可谓有毒,博主这题被卡常卡到心态爆炸。

首先我们来看一下这两个操作分别有什么性质。

根据k≤100000这个条件,我们每做一次1操作,就相当于直接将i位置的数删除掉,也就是i位置的数可取了,毕竟k还是比一千万小很多的。

2操作貌似没什么性质,只是我们要搞的时候注意不能取用1----r之间的所有数就是了。

因为很明显的涉及到时间戳的问题,所以肯定是主席树。

然后最容易想到的是直接用带修主席树,利用权值线段树的思想,维护时间戳r时数字区间x---y之间出现的数的总个数。

这样是nlog2n的做法,貌似有人就这么过了……

可是博主并不会带修主席树。

于是博主想,直接使用普通主席树,既然1操作相当于删除,那么我就用一个set去保存当前所有被删除过的数。在求的时候,先二分答案mid,看k---mid之间是否所有数都出现过,如果没出现过就往左,否则往右,找到最初始的答案。然后再去set里面对k取lower_bound,取两个答案中的最小值。

这个做法是nlog2n的,理论上是能过的,不过……博主比赛的时候被卡常卡到心态炸裂……

于是在比赛后又想……能不能去掉那个二分啊……

于是博主又想到了……主席树反向建立,就是相当于对于每一位讲,每向前推进一位,当前这一位的数就变得可用了。那么我们建立的时候root[n]是完全没有数可用的,root[n-1]可用n位置的数。于是在主席树维护的东西上做了一点变动,不再维护每个权值出现的次数,而是改为:叶子节点的权值如果当前可用,那么就直接保存当前节点的权值,非叶子节点的节点保存所辖权值范围的所有权值中可用权值的最小值。在查询的时候,set的操作还是不变,主席树部分的查询改为,查询时间戳为r时刻的k---n的权值区间可用权值中的最小权值。这样我们就把二分的部分给省去了。整体时间复杂度nlogn。

然后博主满怀信心的交了上去,又迎来了一发TLE。

博主开始怀疑人生了……

博主强行把自己的内存池指针式写法改成数组式写法,并且min函数改为手写min而非stlmin,终于算是卡过去了……1278ms。。。而且还是得使用比较快的取消关联的cin cout。。。

那些不超过1s的大神真的不知道怎么做的,可能我常数还是写大了?

(小声bb:听说可以不用主席树,用二分ST表?不会啊,我还是好弱啊……)

代码

#include <bits/stdc++.h>
using namespace std;
int t;
const int maxn = 1e5+5;
struct tree{
    int l,r;
    int lc,rc;
    int sum;    
}pool[maxn<<5];
int root[maxn];
int cnt = 0;
int min(int a,int b){
    return (a < b ? a : b);
}
void init(){
    cnt = 0;
    return;
}
set<int>s;
set<int>::iterator it;
int tot = 0;
int build(int l,int r){
    int now = ++cnt;
    pool[now].l = l;
    pool[now].r = r;
    pool[now].sum = 1e9;
    pool[now].lc = pool[now].rc = 0;
    if(l == r)return now;
    int mid = (l + r) >> 1;
    pool[now].lc = build(l,mid);
    pool[now].rc = build(mid+1,r);
    return now;
}
int update(int pre,int x){
    int now = ++cnt;
    pool[now].sum = 0;
    pool[now].lc = pool[pre].lc;
    pool[now].rc = pool[pre].rc;
    pool[now].l = pool[pre].l;
    pool[now].r = pool[pre].r;
    pool[now].sum = min(pool[pre].sum,x);
    if(pool[now].l == pool[now].r)
        return now;
    int mid = (pool[now].l + pool[now].r) >> 1;
    if(x <= mid)
        pool[now].lc = update(pool[pre].lc,x);
    else pool[now].rc = update(pool[pre].rc,x);
    return now;
}
int query(int rr,int k,int x){
    if(pool[rr].l >= k && pool[rr].r <= x){
        return pool[rr].sum;
    }
    int mid = (pool[rr].l + pool[rr].r) >> 1;
    int ans = 1e9;
    if(k <= mid)ans = min(ans,query(pool[rr].lc,k,x));
    if(x > mid)ans = min(ans,query(pool[rr].rc,k,x));
    return ans;
}
int a[maxn];
int n,q;
int opt = 0;
int l,r,k,cl,cr;
int ans = 0;
int vis[maxn];
int midd,pans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--){
        init();
        cin >> n >> q;
        s.clear();
        root[n] = build(1,n);
        for(int i = 1;i <= n;++i){
            cin >> a[i];
            vis[i] = 0;
        }
        for(int i = n-1;i >= 0;--i){
            root[i] = update(root[i+1],a[i+1]);
        }
        ans = 0;
        while(q--){
            cin >> opt;
            if(opt == 1){
                cin >> l;
                l ^= ans;
                if(vis[l])continue;
                vis[l] = 1;
                s.insert(a[l]);
            }
            else{
                cin >> r >> k;
                r ^= ans;
                k ^= ans;
                cl = k,cr = n;
                ans = n+1;
                ans = min(ans,query(root[r],k,n));
                cl = k;cr = n;
                it = s.lower_bound(k);
                if(it != s.end())
                    ans = min(ans,*it);
                cout << ans << "\n";
            }
        }
    }
    return 0;
}

 

上一篇: 2019 CCPC网络赛 1005 huntian oy 杜教筛

下一篇: Codeforces Round 580div2 1025B Shortest Cycle 思维题

立即登录,发表评论
没有帐号?立即注册
1 条评论