Fork me on GitHub

「BZOJ3065」 带插入区间K小值 替罪羊树套主席树

发表于 | 分类于
字数统计: 1,395字 | 阅读时长 ≈ 8分钟

真-毒瘤题

Links there:BZOJ3065

题意

如题,强制在线,带修改,带插入的区间 $k​$ 小值的查询

思路

不带插入是可以带修主席树直接做的 不带插入的右转 BZOJ1901

这个插入的操作十分的令人恶心 我们要多维护一个区间顺序的信息了

脑海里回顾一下学过的毒瘤的数据结构 似乎只有平衡树能搞这个东西了

所以我们用替罪羊树套主席树!

Treap?Splay?插入的时候要rotate太难写!

我们用暴力重构的Scapegoat!

不用旋转 思维比较简单 实现难度低 代码量小 绝对是非可持久化平衡树的首选啊

每次暴力重构的时间是 $O(nlog^2n)$ 每个点期望重构次数是严格小于 $logn$ 次的所以总复杂度小于等于 $O(nlog^3n)$

再考虑一下询问 这里是要把每个结点对应区间的节点作为一个向量拉出来 对于向量跑二分.

二分复杂度 $logn$ 每次询问寻找复杂度 $logn$ 所以询问的复杂度为 $O(qlog^2n)$

还有没有优化的余地呢 ?

答案是肯定的 对于 $N$ 个权值区域相同的主席树合并可以做到 $O(nlogn)$

每次暴力重构的复杂度可以通过权值线段树的合并做到 $O(nlog^2n)$

这样最后的复杂度是 $O((n+q) \times log^2n)$ 的但是因为暴力重构的次数实际上并不多 因此这个优化实质上也不明显

注意垃圾回收! 垃圾回收一定不要写挂! (这就是我调一个上午的理由)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//What is broken can be reforged.
#include<bits/stdc++.h>
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define mp make_pair
#define se second
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}

const int N = 1e7 + 100,m =70000,M = 1e5 + 100;
int c[N][2],lson[M],rson[M],rt[M],sz[N],pool[N + 5],rub = 0,q[M],a[M],p[M],headpq;
int n,root = 0,headp,headq,trtot = 0,lastans = 0;
inline char NextChar(void){char c = getchar(); while(!isalpha(c)) c = getchar(); return c;}
const double xs = 0.75;
int Newnode(){
    if (!rub) return ++trtot;
    else return pool[rub--];
}

void Recycle(int &k){
    if (rub > N) --rub;
    pool[++rub] = k;
    if (c[k][0]) Recycle(c[k][0]);
    if (c[k][1]) Recycle(c[k][1]);
    sz[k] = 0; k = 0;
}

void dfs(int &u) {
    Recycle(rt[u]);
    if (lson[u]) dfs(lson[u]);
    p[++headp] = u;
    if (rson[u]) dfs(rson[u]);
}

void ins(int &k,int l,int r,int x,int y){
    if (!k) k=Newnode();
    if (l==r){ sz[k]+=y; return; } int mid=(l+r)>>1;
    if (x<=mid) ins(c[k][0],l,mid,x,y); else ins(c[k][1],mid+1,r,x,y);
    sz[k]=sz[c[k][0]]+sz[c[k][1]];
    if (!sz[k]) Recycle(k);
}
void build(int &k,int l,int r){
    if (l>r) return;
    if (l==r){
        k=p[l]; ins(rt[k],0,m,a[k],1); return;
    }
    int i,mid=(l+r)>>1; k=p[mid];
    build(lson[k],l,mid-1); build(rson[k],mid+1,r);
    for (i=l; i<=r; i++) ins(rt[k],0,m,a[p[i]],1);
}
void rebuild(int &k){
    headp=0; dfs(k); build(k,1,headp);
}
bool add(int &k,int x,int y){
    if (!k){
        k=++n; ins(rt[k],0,m,y,1);
        a[k]=y; return 0;
    }
    ins(rt[k],0,m,y,1);
    int tmp=sz[rt[lson[k]]]; bool bo;
    if (tmp>=x) bo=add(lson[k],x,y);
        else bo=add(rson[k],x-tmp-1 ,y);
    if (sz[rt[k]]*0.75>max(sz[rt[lson[k]]],sz[rt[rson[k]]])){
        if (bo)
            if (tmp>=x) rebuild(lson[k]); else rebuild(rson[k]);
        return 0;
    } else return 1;
}
inline void getid(int k,int l,int r){
    if (l == 1 && r == sz[rt[k]]) {p[++headp] = rt[k]; return ;}
    int t = sz[rt[lson[k]]] + 1;
    if (l <= t && r >= t) q[++headq] = a[k];
    if (r < t) getid(lson[k],l,r);
    else if (l > t) getid(rson[k],l-t,r-t);
    else {
        if (l < t) getid(lson[k],l,t-1);
        if (r > t) getid(rson[k],1,r-t);
    }
}

int solve(int x,int y,int rst){
    headp=0; headq=0; getid(root,x,y);
    rst--; int l=0,r=m,mid,i,tmp;
    while (l<r){
        mid=(l+r)>>1; tmp=0;
        for (i = 1; i<=headp; i++) tmp+=sz[c[p[i]][0]];
        for (i = 1; i<=headq; i++)
            if (l <= q[i] && q[i]<=mid) tmp++;
        if (tmp>rst){
            for (i=1; i<=headp; i++) p[i]=c[p[i]][0];
            r=mid;
        }
        else{
            for (i=1; i<=headp; i++) p[i]=c[p[i]][1];
            l=mid+1;rst-=tmp;
        }
    }
    return l;
}

int Modify(int k,int x,int y){
    ins(rt[k],0,m,y,1); int t = sz[rt[lson[k]]] + 1,ret;
    if (x == t) {ret = a[k]; a[k] = y;}
    else if (x < t) ret = Modify(lson[k],x,y);
    else ret = Modify(rson[k],x-t,y);
    ins(rt[k],0,m,ret,-1);
    return ret;
}

///------------------head------------------
signed main(signed argc, char *argv[]){
    n = read();
    rep(i,1,n) a[i] = read(),p[i] = i;
    build(root,1,n);
    int op = read();
    while(op--) {
        char c = NextChar();
        int x = read()^lastans,y = read()^lastans;
        //printf("%lld %lld\n",x,y);
        if (c == 'I') {if (add(root,x-1,y)) rebuild(root);}
        else if (c == 'Q') {
            int z = read()^lastans; lastans = solve(x,y,z); printf("%d\n",lastans);
        }
        else Modify(root,x,y);
    }
    return 0;
}

/* Examples: */
/*

*/

/*

*/