codevs3243:区间翻转,线段树

Posted by Cww97 on 2016-01-07

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50474826
题目描述 Description
给出N个数,要求做M次区间翻转(如1 2 3 4变成4 3 2 1),求出最后的序列

输入描述 Input Description
第一行一个数N,下一行N个数表示原始序列,在下一行一个数M表示M次翻转,之后的M行每行两个数L,R表示将区间[L,R]翻转。

输出描述 Output Description
一行N个数 , 表示最终序列。

样例输入 Sample Input
4
1 2 3 4
2
1 2
3 4

样例输出 Sample Output
2 1 4 3

数据范围及提示 Data Size & Hint
对于30%的数据满足n<=100 , m <= 10000
对于100%的数据满足n <= 150000 , m <= 150000
对于100%的数据满足n为2的幂,且L = i * 2^j + 1 , R = (i + 1) * 2^j

帖代码,感谢XS的调试

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
program cx;
var i,BTM,n,m,l,r:longint;
trs,trlc,trrc,trw,trfz:array[0..100]of longint;

procedure down(t:longint);
var temp:longint;
begin
if trfz[t]=0 then exit;
trfz[t]:=0;
trfz[trlc[t]]:=trfz[trlc[t]]xor 1;
trfz[trrc[t]]:=trfz[trrc[t]]xor 1;
temp:=trlc[t];
trlc[t]:=trrc[t];
trrc[t]:=temp;
end;

function cmp(x:longint):longint; //XS令人苦笑不得的函数,求左子树SIZE
begin
exit(trs[trlc[x]]);
end;

procedure change(t,ll,rr:longint);
begin
if (ll=1)and(rr=trs[t]) then
begin
trfz[t]:=trfz[t] xor 1;
exit;
end;
down(t);
if ll-cmp(t)>=1 then
begin
ll:=ll-cmp(t);
rr:=rr-cmp(t);
change(trrc[t],ll,rr);
end
else
change(trlc[t],ll,rr);
end;

procedure print(t:longint);
var i:longint;
begin
if trlc[t]=0 then
begin
write(trw[t],' ');
exit;
end;
down(t);
print(trlc[t]);
print(trrc[t]);
end;

begin
assign(input,'gym.in');reset(input);
read(n);
BTM:=1;
while BTM<n do BTM:=BTM<<1;
dec(BTM);
for i:=BTM+1 to BTM+n do
begin
read(trw[i]);
trs[i]:=1;
end;
for i:=BTM downto 1 do
begin
trlc[i]:=i<<1;
trrc[i]:=(i<<1)+1;
trs[i]:=trs[trlc[i]]+trs[trrc[i]];
end;

read(m);
for i:=1 to m do
begin
read(l,r);
change(1,l,r);
end;
print(1); writeln;
close(input);
end.