國際慣例的題面:
這種維護排序序列，嚴格大于的進行操作的題都很套路......
我們按照[0,k],(k,2k],(2k,inf)分類討論一下就好。
顯然第一個區間的不會變化，第二個區間的會被平移進第一個區間，第三個區間的相對大小不會變化。
于是我們直接把第二個區間拆了重構，一個一個插入第一個區間即可。因為每次這樣做最少減半，所以每個元素只會被重構log次，復雜度nlog^2n。
這種按照值域分離區間的操作，非旋轉treap實現起來是最簡單的......
然而第一次寫非旋轉treap還是出了一點問題，注意它的插入是通過按照值域分裂，新建點，再進行兩次合并實現的。直接插入復雜度不對。
另外區間值域存在重合的情況兩個treap不能直接合并......
我寫的判定size的版本復雜度好像不對(不如暴力快？)，于是只好預先生成fix值。
代碼:
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstdlib>
4 const int maxn=1e5+
1e2;
5
6 typedef std::pair<
int,
int>
pii;
7 __inline pii mp(
const int &x,
const int &y) {
return std::make_pair(x,y); }
8
9 int seq[maxn],sql;
10 int stk[maxn],top;
11
12 struct Treap {
13 int lson[maxn],rson[maxn],lazy[maxn],val[maxn],siz[maxn],fix[maxn],cnt;
14
15 inline
void init(
int n) {
16 for(
int i=
1;i<=n;i++) fix[i] =
i;
17 std::random_shuffle(fix+
1,fix+
1+
n);
18 }
19 inline
void apply(
int pos,
int x) {
20 if(pos) lazy[pos] += x , val[pos] -=
x;
21 }
22 inline
void push(
int pos) {
23 if( lazy[pos] ) apply(lson[pos],lazy[pos]) , apply(rson[pos],lazy[pos]) , lazy[pos] =
0;
24 }
25 inline
void maintain(
int pos) {
26 siz[pos] = siz[lson[pos]] + siz[rson[pos]] +
1;
27 }
28
29 inline pii split(
int pos,
int dv) {
// left is <= , right is > .
30 if( !pos )
return mp(
0,
0);
31 push(pos);
32 if( dv <
val[pos] ) {
33 pii spl =
split(lson[pos],dv);
34 lson[pos] =
spl.second , maintain(pos);
35 return mp(spl.first,pos);
36 }
else {
37 pii spr =
split(rson[pos],dv);
38 rson[pos] =
spr.first , maintain(pos);
39 return mp(pos,spr.second);
40 }
41 }
42 inline
int merge(
int x,
int y) {
43 if( !x || !y )
return x |
y;
44 push(x) , push(y);
45 if( val[x] >
val[y] ) std::swap(x,y);
46 if( fix[x] > fix[y] ) {
// siz[x] is bigger .
47 lson[y] =
merge(lson[y],x) , maintain(y);
48 return y;
49 }
else {
50 rson[x] =
merge(rson[x],y) , maintain(x);
51 return x;
52 }
53 }
54 inline
void dfs(
int pos) {
55 if( !pos )
return;
56 seq[++sql] =
val[pos] , push(pos);
57 dfs(lson[pos]) , dfs(rson[pos]);
58 lson[pos] = rson[pos] = siz[pos] =
0 , stk[++top] =
pos;
59 }
60 inline
int kth(
int pos,
int k) {
// return the kth value .
61 if( k == siz[lson[pos]] +
1 )
return val[pos];
62 return push(pos) , k <= siz[lson[pos]] ? kth(lson[pos],k) : kth(rson[pos],k-siz[lson[pos]]-
1);
63 }
64 inline
void insert(
int &root,
int x) {
65 val[++cnt] = x , siz[cnt] =
1;
66 pii sp =
split(root,x);
67 root = merge(sp.first,cnt) , root =
merge(root,sp.second);
68 }
69 inline
void reinsert(
int &root,
int x) {
70 int cur = stk[top--
];
71 val[cur] = x , siz[cur] =
1;
72 pii sp =
split(root,x);
73 root = merge(sp.first,cur) , root =
merge(root,sp.second);
74 }
75
76 }tp;
77
78 int main() {
79 static int n,m,root,rtl,rtm,rtr;
80 scanf(
"%d%d",&n,&
m) , tp.init(n);
81 for(
int i=
1,t;i<=n;i++) scanf(
"%d",&
t) , tp.insert(root,t);
82 for(
int i=
1,o,x;i<=m;i++
) {
83 scanf(
"%d%d",&o,&
x);
84 if( o ==
1 ) printf(
"%d\n",tp.kth(root,x));
85 else if( o ==
2 ) {
86 pii sp =
tp.split(root,x);
87 rtl = sp.first , sp = tp.split(sp.second,x<<
1);
88 rtm = sp.first , rtr =
sp.second;
89 sql =
0 , tp.dfs(rtm) , tp.apply(rtr,x);
90 for(
int i=
1;i<=sql;i++) tp.reinsert(rtl,seq[i]-
x);
91 root =
tp.merge(rtl,rtr);
92 }
93 }
94 return 0;
95 }
View Code
Thupc被拒了好氣啊！我們隊可是有yzy大爺的！(即使這樣都被拒了，一看就是我太菜了)
ありのままでいればいつも
只要堅守自我維持現狀
あるべき私かここにいると
自己希望成為的樣貌就存在于此
信じてまた 新しい夢を
不要放棄希望 嶄新的夢想
精一杯描き出せばいい
再次奮力地去描繪就好
そう気づき始めたよ私
是啊 而我開始意識到
みんなとただ笑ってる未來を
大家單純地綻放笑容的未來
夢見て
誠心盼望
轉載于:https://www.cnblogs.com/Cmd2001/p/8996861.html
總結
以上是生活随笔為你收集整理的4923: [Lydsy1706月赛]K小值查询 平衡树 非旋转Treap的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
