明明是树状数组套主席树裸题我为什么要写权值线段树套平衡树……
如果是全局的查询就用权值线段树对吧。
那么这里考虑套一个平衡树来维护下标。
由于是 FHQ Treap，
成功地卡常卡不过……
此代码无法在 BZOJ 上通过。
代码： 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
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
while(ch < '0' || ch > '9')
w |= ch == '-',ch = gc();
while(ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
w ? x = -x : x;
}
const int N = 1e5;
const int A = 1e9;
int n,m;
int a[N + 10];
int seg_tot,segroot;
int ls[(N << 8) + 10],rs[(N << 8) + 10];
struct node
{
int val,rnd,sz;
node *lson,*rson;
} *rt[(N << 8) + 10];
inline node *new_node(int v)
{
node *ret = new node();
ret->val = v;
ret->rnd = rand();
ret->sz = 1;
return ret;
}
inline void up(node *p)
{
p->sz = 1;
if(ls(p))
p->sz += ls(p)->sz;
if(rs(p))
p->sz += rs(p)->sz;
}
node *merge(node *x,node *y)
{
if(!x || !y)
return !x ? y : x;
if(x->rnd < y->rnd)
{
rs(x) = merge(rs(x),y);
up(x);
return x;
}
else
{
ls(y) = merge(x,ls(y));
up(y);
return y;
}
}
void split(node *p,int v,node *&x,node *&y)
{
if(!p)
{
x = y = NULL;
return ;
}
if(p->val <= v)
x = p,split(rs(p),v,rs(p),y);
else
y = p,split(ls(p),v,x,ls(p));
up(p);
}
void update(int x,int v,int k,int &p,int tl,int tr)
{
if(!p)
p = ++seg_tot;
node *a,*b,*c;
if(~k)
{
split(rt[p],x,a,b);
rt[p] = merge(merge(a,new_node(x)),b);
}
else
{
split(rt[p],x,a,c);
split(a,x - 1,a,b);
if(b)
delete b;
rt[p] = merge(a,c);
}
if(tl == tr)
return ;
int mid = tl + tr >> 1;
if(v <= mid)
update(x,v,k,ls[p],tl,mid);
else
update(x,v,k,rs[p],mid + 1,tr);
}
int query(int l,int r,int k,int p,int tl,int tr)
{
if(tl == tr)
return tl;
node *a,*b,*c;
int cnt = 0;
split(rt[ls[p]],r,a,c);
split(a,l - 1,a,b);
if(b)
cnt = b->sz;
rt[ls[p]] = merge(merge(a,b),c);
int mid = tl + tr >> 1;
if(k <= cnt)
return query(l,r,k,ls[p],tl,mid);
else
return query(l,r,k - cnt,rs[p],mid + 1,tr);
}
int main()
{
read(n),read(m);
for(register int i = 1;i <= n;++i)
read(a[i]),update(i,a[i],1,segroot,0,A);
char op;
int l,r,v;
while(m--)
{
op = 0;
while(op ^ 'Q' && op ^ 'C')
op = gc();
if(op == 'Q')
{
read(l),read(r),read(v);
printf("%d\n",query(l,r,v,segroot,0,A));
}
else
{
read(l),read(v);
update(l,a[l],-1,segroot,0,A);
a[l] = v;
update(l,a[l],1,segroot,0,A);
}
}
}