ps做网站页面,期末网页设计学生作业代码,百度竞价推广账户,wordpress照相馆主题各种操作o(╯□╰)o...不过都挺简单#xff0c;不需要lazy标记。 方法1#xff1a;块状链表 块状链表太强大了#xff0c;区间操作实现起来简单暴力#xff0c;效率比splay稍微慢一点#xff0c;内存开销小很多。 1 #include iostream2 #include cstring3…各种操作o(╯□╰)o...不过都挺简单不需要lazy标记。 方法1块状链表 块状链表太强大了区间操作实现起来简单暴力效率比splay稍微慢一点内存开销小很多。 1 #include iostream2 #include cstring3 #include cstdio4 using namespace std;5 6 const int N 900;7 const int LOW 260;8 const int UP 320;9 int sz[N];10 int next[N];11 int g[N][2];12 int n, m, ps, bl;13 14 struct B15 {16 int v, s;17 } b[N][N];18 19 int gcd( int x, int y )20 {21 if ( y ) return gcd( y, x % y );22 return x;23 }24 25 void update( int cur, int stu )26 {27 g[cur][stu] 0;28 for ( int i 0; i sz[cur]; i )29 {30 if ( b[cur][i].s stu )31 {32 g[cur][stu] gcd( g[cur][stu], b[cur][i].v );33 }34 }35 }36 37 void spilt( int cur )38 {39 int tmp next[cur];40 int ncur bl;41 next[cur] ncur;42 next[ncur] tmp;43 for ( int i sz[cur] / 2; i sz[cur]; i )44 {45 b[ncur][sz[ncur]] b[cur][i];46 }47 sz[cur] sz[cur] / 2;48 update( cur, 0 );49 update( cur, 1 );50 update( ncur, 0 );51 update( ncur, 1 );52 }53 54 void insert( int pos, int val, int stu )55 {56 int cur 0, p sz[cur];57 while ( p pos 1 next[cur] ! -1 )58 {59 cur next[cur];60 p sz[cur];61 }62 if ( p pos 1 )63 {64 pos p;65 }66 p - sz[cur];67 pos - p;68 for ( int j sz[cur] - 1; j pos; j-- )69 {70 b[cur][j 1] b[cur][j];71 }72 b[cur][pos].v val;73 b[cur][pos].s stu;74 sz[cur];75 if ( sz[cur] UP )76 {77 spilt(cur);78 }79 else80 {81 g[cur][stu] gcd( g[cur][stu], val );82 }83 }84 85 void remove( int pos )86 {87 int cur 0, p sz[cur];88 while ( p pos 1 next[cur] ! -1 )89 {90 cur next[cur];91 p sz[cur];92 } 93 if ( p pos 1 )94 {95 return ;96 }97 else98 {99 p - sz[cur];
100 pos - p;
101 int tt b[cur][pos].s;
102 for ( int j pos; j sz[cur] - 1; j )
103 {
104 b[cur][j] b[cur][j 1];
105 }
106 sz[cur]--;
107 update( cur, tt );
108 }
109 }
110
111 void reverse( int pos )
112 {
113 int cur 0, p sz[cur];
114 while ( p pos 1 next[cur] ! -1 )
115 {
116 cur next[cur];
117 p sz[cur];
118 }
119 if ( p pos 1 )
120 {
121 return ;
122 }
123 else
124 {
125 p - sz[cur];
126 pos - p;
127 int tt b[cur][pos].s;
128 b[cur][pos].s ^ 1;
129 update( cur, tt );
130 g[cur][tt ^ 1] gcd( g[cur][tt ^ 1], b[cur][pos].v );
131 }
132 }
133
134 void modify( int pos, int val )
135 {
136 int cur 0, p sz[cur];
137 while ( p pos 1 next[cur] ! -1 )
138 {
139 cur next[cur];
140 p sz[cur];
141 }
142 if ( p pos 1 )
143 {
144 return ;
145 }
146 else
147 {
148 p - sz[cur];
149 pos - p;
150 b[cur][pos].v val;
151 update( cur, b[cur][pos].s );
152 }
153 }
154
155 int query( int l, int r, int stu )
156 {
157 int cur 0, p sz[cur];
158 while ( p l 1 next[cur] ! -1 )
159 {
160 cur next[cur];
161 p sz[cur];
162 }
163 p - sz[cur];
164 l - p;
165 int ncur 0, q sz[ncur];
166 while ( q r 1 next[ncur] ! -1 )
167 {
168 ncur next[ncur];
169 q sz[ncur];
170 }
171 q - sz[ncur];
172 r - q;
173 int ans 0;
174 if ( cur ! ncur )
175 {
176 for ( int i next[cur]; i ! ncur; i next[i] )
177 {
178 if ( g[i][stu] 0 ) continue;
179 ans gcd( ans, g[i][stu] );
180 }
181 for ( int j l; j sz[cur]; j )
182 {
183 if ( b[cur][j].s stu )
184 {
185 ans gcd( ans, b[cur][j].v );
186 }
187 }
188 for ( int j 0; j r; j )
189 {
190 if ( b[ncur][j].s stu )
191 {
192 ans gcd( ans, b[ncur][j].v );
193 }
194 }
195 }
196 else
197 {
198 for ( int j l; j r; j )
199 {
200 if ( b[cur][j].s stu )
201 {
202 ans gcd( ans, b[cur][j].v );
203 }
204 }
205 }
206 if ( ans 0 ) ans -1;
207 return ans;
208 }
209
210 int main ()
211 {
212 while ( scanf(%d%d, n, m) ! EOF )
213 {
214 ps LOW;
215 memset( sz, 0, sizeof(sz) );
216 memset( next, -1, sizeof(next) );
217 memset( g, 0, sizeof(g) );
218 for ( int i 0; i n; i )
219 {
220 int la i / ps, lb i % ps;
221 scanf(%d%d, b[la][lb].v, b[la][lb].s);
222 }
223 int k 0;
224 while ( ( k 1 ) * ps n ) k;
225 for ( int i 0; i k; i )
226 {
227 sz[i] ps;
228 next[i] i 1;
229 }
230 sz[k] n - k * ps;
231 for ( int i 0; i k; i )
232 {
233 g[i][0] g[i][1] 0;
234 for ( int j 0; j sz[i]; j )
235 {
236 int ss b[i][j].s;
237 g[i][ss] gcd( g[i][ss], b[i][j].v );
238 }
239 }
240 bl k 1;
241 char op[2];
242 int num1, num2, num3;
243 while ( m-- )
244 {
245 scanf(%s, op);
246 if ( op[0] Q )
247 {
248 scanf(%d%d%d, num1, num2, num3);
249 num1--;
250 num2--;
251 printf(%d\n, query( num1, num2, num3 ));
252 }
253 else if ( op[0] I )
254 {
255 scanf(%d%d%d, num1, num2, num3);
256 insert( num1, num2, num3 );
257 }
258 else if ( op[0] D )
259 {
260 scanf(%d, num1);
261 num1--;
262 remove(num1);
263 }
264 else if ( op[0] R )
265 {
266 scanf(%d, num1);
267 num1--;
268 reverse(num1);
269 }
270 else if ( op[0] M )
271 {
272 scanf(%d%d, num1, num2);
273 num1--;
274 modify( num1, num2 );
275 }
276 }
277 }
278 return 0;
279 } 方法2splay 写起来也不算特别长。 1 #include iostream2 #include cstring3 #include cstdio4 using namespace std;5 6 const int N 200002;7 int v[N];8 int s[N];9 int n, m;10 11 int gcd( int x, int y )12 {13 if ( y ) return gcd( y, x % y );14 return x;15 }16 17 struct Node 18 {19 Node * ch[2];20 int g[2];21 int val;22 int stu;23 int rank;24 int sz;25 26 int cmp( int x ) const 27 {28 if ( x rank ) return -1;29 return x rank ? 0 : 1;30 }31 32 void maintain()33 {34 sz rank 1;35 g[0] g[1] 0;36 g[stu] val;37 if ( ch[0] ! NULL )38 {39 sz ch[0]-sz;40 rank ch[0]-sz;41 if ( ch[0]-g[0] ) g[0] gcd( g[0], ch[0]-g[0] );42 if ( ch[0]-g[1] ) g[1] gcd( g[1], ch[0]-g[1] );43 }44 if ( ch[1] ! NULL )45 {46 sz ch[1]-sz;47 if ( ch[1]-g[0] ) g[0] gcd( g[0], ch[1]-g[0] );48 if ( ch[1]-g[1] ) g[1] gcd( g[1], ch[1]-g[1] );49 }50 }51 } * root;52 53 void rotate( Node * o, int d )54 {55 Node * k o-ch[d ^ 1];56 o-ch[d ^ 1] k-ch[d];57 k-ch[d] o;58 o-maintain();59 k-maintain();60 o k;61 }62 63 void splay( Node * o, int k )64 {65 int d o-cmp(k);66 if ( d ! -1 )67 {68 if ( d 1 ) k - o-rank;69 Node * p o-ch[d];70 int d2 p-cmp(k);71 if ( d2 ! -1 )72 {73 int k2 ( d2 0 ? k : k - p-rank ); 74 splay( p-ch[d2], k2 );75 if ( d d2 )76 {77 rotate( o, d ^ 1 );78 }79 else80 {81 rotate( o-ch[d], d );82 }83 }84 rotate( o, d ^ 1 );85 }86 }87 88 Node * build( int l, int r )89 {90 if ( l r ) return NULL;91 Node * o new Node();92 int mid ( l r ) 1;93 o-sz r - l 1;94 o-val v[mid];95 o-stu s[mid];96 o-rank mid - l 1;97 o-g[0] o-g[1] 0;98 o-g[o-stu] o-val;99 o-ch[0] build( l, mid - 1 );
100 o-ch[1] build( mid 1, r );
101 o-maintain();
102 return o;
103 }
104
105 int query( int l, int r, int stu )
106 {
107 splay( root, l );
108 splay( root-ch[1], r - l 2 );
109 return root-ch[1]-ch[0]-g[stu];
110 }
111
112 void insert( int k, int vv, int ss )
113 {
114 splay( root, k );
115 splay( root-ch[1], 1 );
116 Node * o root-ch[1]-ch[0];
117 o new Node();
118 o-sz o-rank 1;
119 o-g[0] o-g[1] 0;
120 o-val vv;
121 o-stu ss;
122 o-g[ss] vv;
123 root-ch[1]-maintain();
124 root-maintain();
125 }
126
127 void remove( int k )
128 {
129 splay( root, k );
130 splay( root-ch[1], 2 );
131 root-ch[1]-ch[0] NULL;
132 root-ch[1]-maintain();
133 root-maintain();
134 }
135
136 void reverse( int k )
137 {
138 splay( root, k );
139 root-stu ^ 1;
140 root-maintain();
141 }
142
143 void modify( int k, int vv )
144 {
145 splay( root, k );
146 root-val vv;
147 root-maintain();
148 }
149
150 int main ()
151 {
152 while ( scanf(%d%d, n, m) ! EOF )
153 {
154 for ( int i 1; i n; i )
155 {
156 scanf(%d%d, v i, s i);
157 }
158 root build( 0, n 1 );
159 char cmd[11];
160 int a, b, c;
161 while ( m-- )
162 {
163 scanf(%s, cmd);
164 if ( cmd[0] Q )
165 {
166 scanf(%d%d%d, a, b, c);
167 int tmp query( a, b, c );
168 if ( !tmp ) tmp -1;
169 printf(%d\n, tmp);
170 }
171 else if ( cmd[0] I )
172 {
173 scanf(%d%d%d, a, b, c);
174 a;
175 insert( a, b, c );
176 }
177 else if ( cmd[0] D )
178 {
179 scanf(%d, a);
180 remove(a);
181 }
182 else if ( cmd[0] R )
183 {
184 scanf(%d, a);
185 a;
186 reverse(a);
187 }
188 else if ( cmd[0] M )
189 {
190 scanf(%d%d, a, b);
191 a;
192 modify( a, b );
193 }
194 }
195 }
196 return 0;
197 } 转载于:https://www.cnblogs.com/huoxiayu/p/4736490.html
