2018HDU多校联合第五场G题：GladYouGame（线段树优化解法）

1 #include
2 using namespace std;
3 typedef long long LL;
4 const int maxn&＃61;1e5&＃43;10;
5 int n,m,T;
6 unsigned int X,Y,Z;
7
8 struct Node{
9 int l,r,maxnum,minnum,tag;
10 } tree[maxn<<2];
11
12 unsigned int functions()
13 {
14 X&＃61;X^(X<<11);
15 X&＃61;X^(X>>4);
16 X&＃61;X^(X<<5);
17 X&＃61;X^(X>>14);
18 unsigned int w&＃61;X^(Y^Z);
19 X&＃61;Y; Y&＃61;Z; Z&＃61;w;
20 return Z;
21 }
22
23 void build(int pos,int l,int r)
24 {
25 tree[pos].l&＃61;l,tree[pos].r&＃61;r,tree[pos].tag&＃61;-1;
26 if(l&＃61;&＃61;r)
27 {
28 tree[pos].maxnum&＃61;0;
29 tree[pos].minnum&＃61;0;
30 return ;
31 }
32 int mid&＃61;(tree[pos].l&＃43;tree[pos].r)>>1;
33 build(pos<<1,l,mid);
34 build(pos<<1|1,mid&＃43;1,r);
35 tree[pos].maxnum&＃61;max(tree[pos<<1].maxnum,tree[pos<<1|1].maxnum);
36 tree[pos].minnum&＃61;min(tree[pos<<1].minnum,tree[pos<<1|1].minnum);
37 }
38
39 void pushup(int pos)
40 {
41 tree[pos].maxnum&＃61;max(tree[pos<<1].maxnum,tree[pos<<1|1].maxnum);
42 tree[pos].minnum&＃61;min(tree[pos<<1].minnum,tree[pos<<1|1].minnum);
43 }
44
45 void pushdown(int pos)
46 {
47 tree[pos<<1].maxnum&＃61;max(tree[pos<<1].maxnum,tree[pos].tag);
48 tree[pos<<1|1].maxnum&＃61;max(tree[pos<<1|1].maxnum,tree[pos].tag);
49 tree[pos<<1].minnum&＃61;max(tree[pos<<1].minnum,tree[pos].tag);
50 tree[pos<<1|1].minnum&＃61;max(tree[pos<<1|1].minnum,tree[pos].tag);
51 tree[pos<<1].tag&＃61;max(tree[pos<<1].tag,tree[pos].tag);
52 tree[pos<<1|1].tag&＃61;max(tree[pos<<1|1].tag,tree[pos].tag);
53 tree[pos].tag&＃61;-1;
54 }
55
56 void update(int pos,int l,int r,int val)
57 {
58 if(tree[pos].l&＃61;&＃61;tree[pos].r)
59 {
60 tree[pos].maxnum&＃61;max(tree[pos].maxnum,val);
61 tree[pos].minnum&＃61;max(tree[pos].minnum,val);
62 return ;
63 }
64 if(tree[pos].l>&＃61;l&&tree[pos].r<&＃61;r)
65 {
66 if(tree[pos].maxnum<&＃61;val)
67 {
68 tree[pos].maxnum&＃61;tree[pos].minnum&＃61;val;
69 tree[pos].tag&＃61;max(tree[pos].tag,val);
70 return ;
71 }
72 }
73 if(tree[pos].minnum>&＃61;val) return ;
74
75 if(tree[pos].tag!&＃61;-1) pushdown(pos);
76 int mid&＃61;(tree[pos].l&＃43;tree[pos].r)>>1;
77 if(r<&＃61;mid) update(pos<<1,l,r,val);
78 else if(l>&＃61;mid&＃43;1) update(pos<<1|1,l,r,val);
79 else update(pos<<1,l,mid,val),update(pos<<1|1,mid&＃43;1,r,val);
80 pushup(pos);
81 }
82
83 int query(int pos,int k)
84 {
85 if(tree[pos].l&＃61;&＃61;tree[pos].r&&tree[pos].l&＃61;&＃61;k) return tree[pos].maxnum;
86 int mid&＃61;(tree[pos].l&＃43;tree[pos].r)>>1;
87 if(tree[pos].tag!&＃61;-1) pushdown(pos);
88 if(k<&＃61;mid) return query(pos<<1,k);
89 else return query(pos<<1|1,k);
90 }
91
92 int main()
93 {
94 ios::sync_with_stdio(false);
95 cin.tie(0);
96 cin>>T;
97 while(T--)
98 {
99 LL ans&＃61;0;
100 cin>>n>>m>>X>>Y>>Z;
101 build(1,1,n);
102 for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)
103 {
104 int l&＃61;functions()%n&＃43;1;
105 int r&＃61;functions()%n&＃43;1;
106 int v&＃61;functions()%(1<<30);
107 if(l>r) swap(l,r);
108 update(1,l,r,v);
109 }
110 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) ans^&＃61;1ll*i*query(1,i);
111 cout<endl;
112 }
113
114 return 0;
115 }