专栏首页HansBug's Lab算法模板——线段树7(骰子翻转问题)

算法模板——线段树7(骰子翻转问题)

实现功能:首先输入一个长度为N的序列,由1-4组成(1表示向前滚一下,2表示向后滚一下,3表示向左滚一下,4表示向右滚一下,骰子原始状态:上1前2左4右5后3下6),然后输入任意多个操作,输入“1 x y”表示将序列第x个数改成y,输入“2 x y”表示输出对于原始状态的骰子,按照从x到y的序列操作可以使骰子变成什么样子

原理:还是线段树,而且只需要点修改区间访问,不过这里面区间之间的合并不再是简单的累加了,而是——置换关系,通过置换关系的合并实现及时的维护即可

 1 type
 2     cube=array[1..6] of longint;
 3 const fo:cube=(3,1,6,4,5,2);
 4       ba:cube=(2,6,1,4,5,3);
 5       le:cube=(5,2,3,1,6,4);
 6       ri:cube=(4,2,3,6,1,5);
 7       mo:cube=(1,2,3,4,5,6);
 8 var
 9    i,j,k,l,m,n:longint;
10    a:array[0..1000000] of cube;
11    a1:cube;
12 function min(x,y:longint):longint;inline;
13          begin
14               if x<y then min:=x else min:=y;
15          end;
16 function max(x,y:longint):longint;inline;
17          begin
18               if x>y then max:=x else max:=y;
19          end;
20 
21 function merge(a1,a2:cube):cube;inline;
22           var a3:cube;i:longint;
23           begin
24                for i:=1 to 6 do
25                    a3[i]:=a1[a2[i]];
26                exit(a3);
27           end;
28 procedure built(z,x,y:longint);inline;
29           begin
30                if x=y then
31                   begin
32                        read(i);
33                        case i of
34                             1:a[z]:=fo;
35                             2:a[z]:=ba;
36                             3:a[z]:=le;
37                             4:a[z]:=ri;
38                        end;
39                   end
40                else
41                    begin
42                         built(z*2,x,(x+y) div 2);
43                         built(z*2+1,(x+y) div 2+1,y);
44                         a[z]:=merge(a[z*2],a[z*2+1]);
45                    end;
46           end;
47 procedure op(z,x,y,t,v:longint);inline;
48           begin
49                if (t=y) and (x=t) then
50                   begin
51                        case v of
52                             1:a[z]:=fo;
53                             2:a[z]:=ba;
54                             3:a[z]:=le;
55                             4:a[z]:=ri;
56                        end;
57                        exit;
58                   end;
59                if t<=(x+y) div 2 then op(z*2,x,(x+y) div 2,t,v) else op(z*2+1,(x+y) div 2+1,y,t,v);
60                a[z]:=merge(a[z*2],a[z*2+1]);
61           end;
62 function res(z,x,y,l,r:longint):cube;inline;
63          begin
64               if (l>r) then exit(mo);
65               if (x=l) and (y=r) then exit(a[z]);
66               exit(merge(result(z*2,x,(x+y) div 2,l,min((x+y) div 2,r)),result(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r)));
67          end;
68 begin
69      readln(n);
70      built(1,1,n);
71      readln;
72      while true do
73            begin
74                 read(i);
75                 case i of
76                      1:begin
77                             readln(j,k);
78                             op(1,1,n,j,k);
79                      end;
80                      2:begin
81                             readln(j,k);
82                             a1:=res(1,1,n,j,k);
83                             for i:=1 to 6 do write(a1[i],' ');
84                             writeln;
85                      end;
86                 end;
87            end;
88 
89 end.
90                  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法模板——Dinic最小费用最大流

    实现功能:输入M,N,S,T;接下来M行输入M条弧的信息(包括起点,终点,流量,单位费用);实现功能是求出以S为源点,T为汇点的网络最大流的最小费用 其实相当的...

    HansBug
  • 算法模板——Dinic网络最大流 2

    实现功能:同Dinic网络最大流 1 这个新的想法源于Dinic费用流算法。。。 在费用流算法里面,每次处理一条最短路,是通过spfa的过程中就记录下来,然后顺...

    HansBug
  • 3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家

    3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec  Memory...

    HansBug
  • 3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家

    3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec  Memory...

    HansBug
  • 2953: [Poi2002]商务旅行

    2953: [Poi2002]商务旅行 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 8  Solved: 8...

    HansBug
  • 算法模板——LCA(最近公共祖先)

    实现的功能如下——在一个N个点的无环图中,共有N-1条边,M个访问中每次询问两个点的距离 原理——既然N个点,N-1条边,则说明这是一棵树,而且联通。所以以1为...

    HansBug
  • 3732: Network

    3732: Network Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 395  Solved: 179 ...

    HansBug
  • 算法模板——二分图匹配

    实现功能为二分图匹配 原理:匈牙利算法,核心思想——匹配上了就配,没直接匹配上也要通过前面的腾出位置让这个匹配上(详见:趣写算法系列之——匈牙利算法) 本程序以...

    HansBug
  • Codevs2776 寻找代表元

    2776 寻找代表元  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题目描述 Description 广州二中苏元实...

    HansBug
  • 马化腾:关于运用移动互联网推进智慧民生发展的建议

      全球已经步入移动互联网连接一切的时代。2015年1月,全球接入互联网的移动设备超过70亿台。我国的移动互联网发展也已走在世界前列。目前,我国互联网用户6.4...

    腾讯研究院

扫码关注云+社区

领取腾讯云代金券