codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

794.md (33512B)


      1 Source: https://codeforces.com/blog/entry/51962
      2 
      3 **Bank Robbery**
      4 
      5 Author : [zscoder](/profile/zscoder "Grandmaster zscoder")
      6 
      7 This is a simple implementation problem. We iterate through all banknotes one by one and check if Oleg can take each of them. If a banknote is at position *x*, then Oleg can take it if and only if *b* < *x* < *c*. This can be checked in *O*(1) time. Thus, the total complexity is *O*(*n*). Note that the information on the starting position of Oleg is useless here.
      8 
      9 **Code**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 #include <ext/pb_ds/assoc_container.hpp>
     14 #include <ext/pb_ds/tree_policy.hpp>
     15 
     16 using namespace std;
     17 using namespace __gnu_pbds;
     18 
     19 #define fi first
     20 #define se second
     21 #define mp make_pair
     22 #define pb push_back
     23 #define fbo find_by_order
     24 #define ook order_of_key
     25 
     26 typedef long long ll;
     27 typedef pair<ll,ll> ii;
     28 typedef vector<ll> vi;
     29 typedef long double ld; 
     30 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
     31 typedef set<int>::iterator sit;
     32 typedef map<int,int>::iterator mit;
     33 typedef vector<int>::iterator vit;
     34 
     35 int main()
     36 {
     37 	ios_base::sync_with_stdio(0); cin.tie(0);
     38 	int a, b, c; cin>>a>>b>>c;
     39 	int n; cin>>n;
     40 	int ans=0;
     41 	for(int i=0;i<n;i++)
     42 	{
     43 		int x; cin>>x;
     44 		if(x>b&&x<c) ans++;
     45 	}
     46 	cout<<ans<<'\n';
     47 }
     48 ```
     49 
     50 **Cutting Carrot**
     51 
     52 Author : [zscoder](/profile/zscoder "Гроссмейстер zscoder")
     53 
     54 Let's find the value of *x**i* explicitly. Suppose we make the *i*-th cut and distance *x**i* from the apex. Then, the ratio of similitude of the isosceles triangle with apex equal to the apex of the carrot and the base equal to the *i*-th cut and the whole carrot is ![](https://espresso.codeforces.com/9220b64ac46382804cc668f7ebd056813ae52c25.png). Since the area of this smaller isosceles triangle is the sum of areas of the first *i* pieces, which is ![](https://espresso.codeforces.com/11b846518b825d8f6389c3c993bbdaa960fe29ef.png) of the whole carrot. Thus, ![](https://espresso.codeforces.com/7716f44dad47f8bfbdc99807aa58c2f2cd25e111.png), which is equivalent to ![](https://espresso.codeforces.com/8adb3992d6bd4f58df2426f81d681918ddb0c1b1.png). Thus, ![](https://espresso.codeforces.com/ca1ae7ef3de6de8281c5405bd2f56977498fb17d.png) and we can find each *x**i* in *O*(1) time. The total complexity is *O*(*n*).
     55 
     56 **Code**
     57 
     58 ```
     59 #include <bits/stdc++.h>
     60 #include <ext/pb_ds/assoc_container.hpp>
     61 #include <ext/pb_ds/tree_policy.hpp>
     62 
     63 using namespace std;
     64 using namespace __gnu_pbds;
     65 
     66 #define fi first
     67 #define se second
     68 #define mp make_pair
     69 #define pb push_back
     70 #define fbo find_by_order
     71 #define ook order_of_key
     72 
     73 typedef long long ll;
     74 typedef pair<ll,ll> ii;
     75 typedef vector<ll> vi;
     76 typedef long double ld; 
     77 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
     78 typedef set<int>::iterator sit;
     79 typedef map<int,int>::iterator mit;
     80 typedef vector<int>::iterator vit;
     81 
     82 int main()
     83 {
     84 	ios_base::sync_with_stdio(0); cin.tie(0);
     85 	ll n, h; cin>>n>>h;
     86 	for(int i=1;i<=n-1;i++)
     87 	{
     88 		cout<<fixed<<setprecision(12)<<sqrt(ld(i)/ld(n))*ld(h);
     89 		if(i<n-1) cout<<' ';
     90 	}	
     91 	cout<<'\n';
     92 }
     93 ```
     94 
     95 **Naming Company**
     96 
     97 Author : [zscoder](/profile/zscoder "Гроссмейстер zscoder")
     98 
     99 First, it is clear that Oleg will place ![](https://espresso.codeforces.com/ddb3724dfe86122a90456ba01b63e009b59027a6.png) letters and Igor will place ![](https://espresso.codeforces.com/ff3debcd979cb1dbc17aecf1e75e31f997a019f8.png) letters. Next, it is clear that Oleg and Igor will both choose their smallest and biggest letters respectively to place in the final string. Thus, we now consider that Oleg places his smallest ![](https://espresso.codeforces.com/ddb3724dfe86122a90456ba01b63e009b59027a6.png) letters and Igor places his largest ![](https://espresso.codeforces.com/ff3debcd979cb1dbc17aecf1e75e31f997a019f8.png) letters.
    100 
    101 Consider the following greedy strategy. When it's Oleg's turn, he will replace the frontmost question mark with his smallest letter. When it's Igor's turn, he will replace the frontmost question mark with his largest letter. At first glance, you might think that this works. However, there's another case that we haven't considered.
    102 
    103 Suppose Oleg has the letters {*x*, *y*, *z*} and Igor has the letters {*a*, *b*, *c*}. According to our previous strategy, Oleg will place x as the first letter. However, that's not optimal. He can place his letters at the back and force Igor to place the first letter. The reason is because the largest letter of Igor is not larger than the smallest letter of Oleg. Thus, it is beneficial for Oleg to place his letters at the back and force Igor to place his letters in front.
    104 
    105 So, what exactly will the final string look like? We'll look at the moves one by one. If at some point Oleg's smallest letter is still strictly smaller than Igor's largest letter, then both player must put their smallest (largest if it's Igor) letter as the frontmost letter. Why? Suppose not, then on the next turn the other player will occupy that spot with their best (smallest if Oleg, largest if Igor) letter, and the resulting string will be worse for the current player. This proves that greedy is correct in this case.
    106 
    107 Now, what if Oleg's smallest letter is not smaller than Igor's largest letter. In this case, both players will want to force the other player to place their own letter at the beginning of the string. It can be proven that in this case, each person will place their current worst (largest if Oleg, smallest if Igor) letter at the back of the string in the optimal strategy. Thus, we can calculate the final string starting from this point and after that reverse this part and combine it with the first part of the string where both players greedily place their best letters in the beginning.
    108 
    109 Time Complexity : *O*(*n*)
    110 
    111 Many people failed on pretest 6 initially because they didn't consider the second case.
    112 
    113 **Code**
    114 
    115 ```
    116 #include <bits/stdc++.h>
    117 #include <ext/pb_ds/assoc_container.hpp>
    118 #include <ext/pb_ds/tree_policy.hpp>
    119 
    120 using namespace std;
    121 using namespace __gnu_pbds;
    122 
    123 #define fi first
    124 #define se second
    125 #define mp make_pair
    126 #define pb push_back
    127 #define fbo find_by_order
    128 #define ook order_of_key
    129 
    130 typedef long long ll;
    131 typedef pair<ll,ll> ii;
    132 typedef vector<ll> vi;
    133 typedef long double ld; 
    134 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    135 typedef set<int>::iterator sit;
    136 typedef map<int,int>::iterator mit;
    137 typedef vector<int>::iterator vit;
    138 
    139 int main()
    140 {
    141 	ios_base::sync_with_stdio(0); cin.tie(0);
    142 	string ansl;
    143 	string ansr;
    144 	string s,t;
    145 	cin>>s>>t;
    146 	sort(s.begin(),s.end());
    147 	sort(t.begin(),t.end());
    148 	reverse(t.begin(),t.end());
    149 	int n = s.length();
    150 	deque<char> a,b;
    151 	for(int i=0;i<(n+1)/2;i++)
    152 	{
    153 		a.pb(s[i]);
    154 	}
    155 	for(int i=0;i<n/2;i++)
    156 	{
    157 		b.pb(t[i]);
    158 	}
    159 	bool mode=0;
    160 	for(int i=0;i<n;i++)
    161 	{
    162 		if(i&1)
    163 		{
    164 			if(!a.empty()&&a[0]>=b[0])
    165 			{
    166 				mode=1;
    167 			}
    168 			if(mode)
    169 			{
    170 				ansr+=b.back();
    171 				b.pop_back();
    172 			}
    173 			else
    174 			{
    175 				ansl+=b[0];
    176 				b.pop_front();
    177 			}
    178 		}
    179 		else //P1's turn
    180 		{
    181 			if(!b.empty()&&a[0]>=b[0])
    182 			{
    183 				mode=1;
    184 			}
    185 			if(mode)
    186 			{
    187 				ansr+=a.back();
    188 				a.pop_back();
    189 			}
    190 			else
    191 			{
    192 				ansl+=a[0];
    193 				a.pop_front();
    194 			}
    195 		}
    196 	}
    197 	reverse(ansr.begin(),ansr.end());
    198 	ansl+=ansr;
    199 	cout<<ansl<<'\n';
    200 }
    201 ```
    202 
    203 **Labelling Cities**
    204 
    205 Author : [AnonymousBunny](/profile/AnonymousBunny "Кандидат в мастера AnonymousBunny")
    206 
    207 Add each vertex to its own adjacency list. Now, we claim that if it is possible to label the cities to satisfy the problem conditions, then it is possible to do so so that for every two cities with the same adjacency list, they're labelled with the same number.
    208 
    209 Indeed, if they have the same adjacency list, they must be neighbours. Thus, the difference between their labels is at most 1. Suppose we label the first vertex *u* with number *i* and the second vertex *v* with the number *i* + 1. Note that since their adjacency lists are equal, a vertex *x* is a neighbour of *u* iff it's a neighbour of *v*. Thus, *u* and *v* can't have neighbours with labels *i* - 1 or *i* + 2, or else it will contradict the condition. Thus, all neighbours of *u* and *v* have labels *i* or *i* + 1. Thus, we can safely change the label of the second vertex *v* to *i* and the conditions will still hold.
    210 
    211 Thus, we can sort the set of adjacency lists of each vertex, and then group the vertices with the same adjacency list together. Suppose there are *k* such groups. For simplicity, we can create a new graph where each group represent a vertex of the new graph. Connect two groups *i* and *j* if and only if there exist some vertex in group *i* that connects to a vertex in group *j*. Note that the graph will have at most *O*(*m*) edges. Now, if a vertex has degree  ≥ 3, we can't assign a number to that vertex properly, as one of its neighbours will not have a label which have a difference  ≤ 1 from it. Thus, all vertices in the new graph must have degree  ≤ 2. Since it's connected, it must be either a cycle or a path. However, it can be easily seen that there is no labelling if it's a cycle. Thus, it must be a path. Now, we can just assign the labels to the graph from one end of the path to the other end by the numbers 1 to *k*. Finally, the label of a vertex is simply the label of its group.
    212 
    213 This solution can be implemented in ![](https://espresso.codeforces.com/5dc26215e7d35f45e90b61eab9c75bc9243bc085.png) time.
    214 
    215 **Code**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 #include <ext/pb_ds/assoc_container.hpp>
    220 #include <ext/pb_ds/tree_policy.hpp>
    221 
    222 using namespace std;
    223 using namespace __gnu_pbds;
    224 
    225 #define fi first
    226 #define se second
    227 #define mp make_pair
    228 #define pb push_back
    229 #define fbo find_by_order
    230 #define ook order_of_key
    231 
    232 typedef long long ll;
    233 typedef pair<int,int> ii;
    234 typedef vector<ll> vi;
    235 typedef long double ld; 
    236 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    237 typedef set<int>::iterator sit;
    238 typedef map<int,int>::iterator mit;
    239 typedef vector<int>::iterator vit;
    240 
    241 const int N = 300000;
    242 
    243 pair<vi,int> adj[N+2];
    244 int ans[N+2];
    245 int lab[N+2];
    246 int lab2[N+2];
    247 set<int> adj2[N+2];
    248 vector<ii> edges;
    249 
    250 struct DSU
    251 {
    252 	int S;
    253 	
    254 	struct node
    255 	{
    256 		int p; ll sum;
    257 	};
    258 	vector<node> dsu;
    259 	
    260 	DSU(int n)
    261 	{
    262 		S = n;
    263 		for(int i = 0; i < n; i++)
    264 		{
    265 			node tmp;
    266 			tmp.p = i; tmp.sum = 0;
    267 			dsu.pb(tmp);
    268 		}
    269 	}
    270 	
    271 	void reset(int n)
    272 	{
    273 		dsu.clear();
    274 		S = n;
    275 		for(int i = 0; i < n; i++)
    276 		{
    277 			node tmp;
    278 			tmp.p = i; tmp.sum = 0;
    279 			dsu.pb(tmp);
    280 		}
    281 	}
    282 	
    283 	int rt(int u)
    284 	{
    285 		if(dsu[u].p == u) return u;
    286 		dsu[u].p = rt(dsu[u].p);
    287 		return dsu[u].p;
    288 	}
    289 	
    290 	void merge(int u, int v)
    291 	{
    292 		u = rt(u); v = rt(v);
    293 		if(u == v) return ;
    294 		if(rand()&1) swap(u, v);
    295 		dsu[v].p = u;
    296 		dsu[u].sum += dsu[v].sum;
    297 	}
    298 	
    299 	bool sameset(int u, int v)
    300 	{
    301 		if(rt(u) == rt(v)) return true;
    302 		return false;
    303 	}
    304 	
    305 	ll getstat(int u)
    306 	{
    307 		return dsu[rt(u)].sum;
    308 	}
    309 };
    310 
    311 deque<int> chain;
    312 
    313 void dfs(int u, int p, bool type)
    314 {
    315 	if(type) chain.pb(u);
    316 	else chain.push_front(u);
    317 	int c=0;
    318 	for(sit it = adj2[u].begin(); it != adj2[u].end(); it++)
    319 	{
    320 		int v = (*it);
    321 		if(v==p) continue;
    322 		if(p!=-1)
    323 		{
    324 			dfs(v,u,type);
    325 		}
    326 		else
    327 		{
    328 			dfs(v,u,c);
    329 			c++;
    330 		}
    331 	}
    332 }
    333 
    334 int main()
    335 {
    336 	//ios_base::sync_with_stdio(0); cin.tie(0);
    337 	int n, m; scanf("%d %d", &n, &m);
    338 	for(int i = 0; i < m; i++)
    339 	{
    340 		int u, v; scanf("%d %d", &u, &v);
    341 		u--; v--;
    342 		adj[u].fi.pb(v);
    343 		adj[v].fi.pb(u);
    344 		edges.pb(mp(u,v));
    345 	}
    346 	for(int i = 0; i < n; i++)
    347 	{
    348 		adj[i].fi.pb(i);
    349 		adj[i].se = i;
    350 		sort(adj[i].fi.begin(),adj[i].fi.end());
    351 	}
    352 	sort(adj,adj+n);
    353 	int cnt = 1;
    354 	for(int i = 0; i < n; i++)
    355 	{
    356 		if(i==0) 
    357 		{
    358 			lab[adj[i].se] = cnt;
    359 		}
    360 		else
    361 		{
    362 			if(adj[i].fi==adj[i-1].fi)
    363 			{
    364 				lab[adj[i].se]=cnt;
    365 			}
    366 			else
    367 			{
    368 				lab[adj[i].se]=++cnt;
    369 			}
    370 		}
    371 	}
    372 	if(cnt==1)
    373 	{
    374 		printf("YES\n");
    375 		for(int i = 0; i < n; i++)
    376 		{
    377 			printf("%d ",lab[i]);
    378 		}
    379 		printf("\n");
    380 		return 0;
    381 	}
    382 	DSU dsu(cnt+1);
    383 	for(int i = 0; i < m; i++)
    384 	{
    385 		int u = edges[i].fi; int v = edges[i].se;
    386 		if(lab[u]!=lab[v])
    387 		{
    388 			adj2[lab[u]].insert(lab[v]);
    389 			adj2[lab[v]].insert(lab[u]);
    390 			dsu.merge(lab[u],lab[v]);
    391 		}
    392 	}
    393 	bool pos = 1;
    394 	for(int i = 1; i <= cnt; i++)
    395 	{
    396 		if(dsu.rt(i)!=dsu.rt(1))
    397 		{
    398 			pos=0;
    399 			break;
    400 		}
    401 	}
    402 	if(!pos)
    403 	{
    404 		printf("NO\n");
    405 		return 0;
    406 	}
    407 	int d1 = 0;
    408 	for(int i = 1; i <= cnt; i++)
    409 	{
    410 		if(adj2[i].size()>2)
    411 		{
    412 			printf("NO\n");
    413 			return 0;
    414 		}
    415 		if(adj2[i].size()==1) d1++;
    416 		else assert(adj2[i].size()==2);
    417 	}
    418 	if(d1==2)
    419 	{
    420 		printf("YES\n");
    421 		dfs(1,-1,0);
    422 		for(int i = 0; i < chain.size(); i++)
    423 		{
    424 			lab2[chain[i]] = i+1;
    425 		}
    426 		for(int i = 0; i < n; i++)
    427 		{
    428 			printf("%d ",lab2[lab[i]]);
    429 		}
    430 		printf("\n");
    431 	}
    432 	else
    433 	{
    434 		printf("NO\n");
    435 		return 0;
    436 	}
    437 }
    438 ```
    439 
    440 **Choosing Carrot**
    441 
    442 Author : [zscoder](/profile/zscoder "Гроссмейстер zscoder")
    443 
    444 First, we solve the problem when no one has any extra turns.
    445 
    446 Suppose we're binary searching the answer. Let all the numbers  ≥ *x* be equal to 1 and all the numbers  < *x* be equal to 0. Both players can remove one number from one end of the row. The goal of the first player is to let the remaining number be 1 and the goal of the second player is to leave 0 in the end. If the first player can win, this means that the answer is at least *x*. Thus, we first try to solve this simpler problem.
    447 
    448 We claim that the first player wins if and only if :
    449 
    450 1. *n* is even and one of the two middle numbers is 1.
    451 2. *n* is odd, the middle digit is 1 and at least one of the digits beside the middle digit is 1 (unless *n* = 1, for which first players wins when the only carrot is labelled 1)
    452 
    453 Indeed, once we deduce this, we can easily prove this by induction on *n*. The proof is just doing casework and considering all possible moves.
    454 
    455 Once we have this fact, we realize we don't actually have to binary search the answer. If *n* is even, the answer is ![](https://espresso.codeforces.com/52786dd3066242d0377b02d6aa19337c5ed8fda6.png) while if *n* ≥ 3 is odd, the answer is ![](https://espresso.codeforces.com/8b8b9882bb8489f73c5bf7edf7181e1976c5e69c.png). (If *n* = 1 then the answer is obviously *a*1.)
    456 
    457 Now, we have to take extra moves into account. Fortunately, it's not very difficult. Having *k* extra moves just means that Player 1 can choose to start the game in any subsegment of length *n* - *k*. Thus, we just have to compute the maximum answer for all subsegments of length *n* - *k* for all 0 ≤ *k* ≤ *n* - 1. With the formula above, you can find all the answers in *O*(*n*) time or even ![](https://espresso.codeforces.com/06b2dfff448a3a9e0e9b5c879f5cda0ce1cecba5.png) time if you use sparse table for range maximum query.
    458 
    459 **Code**
    460 
    461 ```
    462 #include <bits/stdc++.h>
    463 #include <ext/pb_ds/assoc_container.hpp>
    464 #include <ext/pb_ds/tree_policy.hpp>
    465 
    466 using namespace std;
    467 using namespace __gnu_pbds;
    468 
    469 #define fi first
    470 #define se second
    471 #define mp make_pair
    472 #define pb push_back
    473 #define fbo find_by_order
    474 #define ook order_of_key
    475 
    476 typedef long long ll;
    477 typedef pair<ll,ll> ii;
    478 typedef vector<ll> vi;
    479 typedef long double ld; 
    480 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    481 typedef set<int>::iterator sit;
    482 typedef map<int,int>::iterator mit;
    483 typedef vector<int>::iterator vit;
    484 
    485 int a[300001];
    486 int ans[300001];
    487 int b[300001];
    488 
    489 int main()
    490 {
    491 	ios_base::sync_with_stdio(0); cin.tie(0);
    492 	int n; cin>>n;
    493 	int mx=0;
    494 	for(int i=0;i<n;i++) 
    495 	{
    496 		cin>>a[i];
    497 		mx=max(mx,a[i]);
    498 	}
    499 	for(int i=0;i<n-2;i++)
    500 	{
    501 		b[i]=min(a[i+1],max(a[i],a[i+2]));
    502 	}
    503 	ans[n-1]=mx;
    504 	int odd=n;int even=n;
    505 	if(n&1) even=n-1;
    506 	else odd=n-1;
    507 	mx=0;
    508 	for(int i=even;i>=2;i-=2)
    509 	{
    510 		int l = (i-1)/2; int r=n-i/2;
    511 		assert(l<=r);
    512 		mx=max(mx,max(a[l],a[r]));
    513 		if(i==even)
    514 		{
    515 			assert(r-l<=2);
    516 			if(r-l==2)
    517 			{
    518 				mx=max(mx,a[l+1]);
    519 			}
    520 		}
    521 		ans[n-i]=mx;
    522 	}
    523 	mx=0;
    524 	for(int i=odd;i>=3;i-=2)
    525 	{
    526 		int l = i/2-1; int r=n-2-i/2;
    527 		assert(l<=r);
    528 		if(i==odd) assert(r-l<=1);
    529 		mx=max(mx,max(b[l],b[r]));
    530 		ans[n-i]=mx;
    531 	}
    532 	for(int i=0;i<n;i++)
    533 	{
    534 		cout<<ans[i];
    535 		if(i<n-1) cout<<' ';
    536 	}
    537 	cout<<'\n';
    538 }
    539 ```
    540 
    541 **Leha and security system**
    542 
    543 Author : [hloya_ygrt](/profile/hloya_ygrt "Мастер hloya_ygrt")
    544 
    545 We use a segment tree to solve this problem. For each node, it is sufficient to store two arrays : *sum*[*i*], denoting the total contribution of the digit *i* in the current segment (if a digit is in the tens digit then it contributes 10 to the sum and etc...), and also *nxt*[*i*], what all the digits *i* in the current segment are changed to.
    546 
    547 Maintaining these arrays is quite straightforward with lazy propogation. When we push an update down a node, we need to update the nxt array of the children. First, we change *st*[*id*].*nxt*[*u*] to *v*, where the current update is to change all digits *u* to *v*. Then, we change *st*[*id* * 2].*nxt*[*i*] to *st*[*id*].*nxt*[*st*[*id* * 2].*nxt*[*i*]], where *st*[*id*] is the current node and *st*[*id* * 2] is one of the children nodes. (Do the same for the right children). You can see the code if you need more details. Finally, update the sum array of the current segment.
    548 
    549 The total complexity of the code is ![](https://espresso.codeforces.com/0a1827fe1ee47477ae5e2f0c305fa15355991297.png), which is fast enough.
    550 
    551 **Code**
    552 
    553 ```
    554 #include <bits/stdc++.h>
    555 #include <ext/pb_ds/assoc_container.hpp>
    556 #include <ext/pb_ds/tree_policy.hpp>
    557 
    558 using namespace std;
    559 using namespace __gnu_pbds;
    560 
    561 #define fi first
    562 #define se second
    563 #define mp make_pair
    564 #define pb push_back
    565 #define fbo find_by_order
    566 #define ook order_of_key
    567 
    568 typedef long long ll;
    569 typedef pair<ll,ll> ii;
    570 typedef vector<int> vi;
    571 typedef long double ld; 
    572 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    573 typedef set<int>::iterator sit;
    574 typedef map<int,int>::iterator mit;
    575 typedef vector<int>::iterator vit;
    576 const int N = 100000;
    577 int a[N+1][10];
    578 
    579 struct node
    580 {
    581 	int nxt[10];
    582 	ll sum[10];
    583 };
    584 
    585 node st[N*4+1];
    586 
    587 void combine(int id)
    588 {
    589 	for(int i = 0; i < 10; i++)
    590 	{
    591 		st[id].sum[i]=st[id*2].sum[i]+st[id*2+1].sum[i];
    592 	}
    593 }
    594 
    595 void build(int id, int l, int r)
    596 {
    597 	if(r-l<2)
    598 	{
    599 		for(int i = 0; i < 10; i++) st[id].sum[i]=a[l][i];
    600 		for(int i = 0; i < 10; i++)
    601 		{
    602 			st[id].nxt[i] = i;
    603 		}
    604 		return ;
    605 	}
    606 	for(int i = 0; i < 10; i++)
    607 	{
    608 		st[id].nxt[i] = i;
    609 	}
    610 	int mid=(l+r)>>1;
    611 	build(id*2,l,mid);
    612 	build(id*2+1,mid,r);
    613 	combine(id);
    614 }
    615 
    616 int nxt1[10];
    617 int nxt2[10];
    618 ll sum[10];
    619 
    620 void push(int id, int l, int r)
    621 {
    622 	memset(sum,0,sizeof(sum));
    623 	if(r-l>=2)
    624 	{
    625 		for(int i = 0; i < 10; i++)
    626 		{
    627 			nxt1[i] = st[id].nxt[st[id*2].nxt[i]];
    628 			nxt2[i] = st[id].nxt[st[id*2+1].nxt[i]];
    629 		}
    630 		for(int i=0;i<10;i++)
    631 		{
    632 			st[id*2].nxt[i]=nxt1[i];
    633 			st[id*2+1].nxt[i]=nxt2[i];
    634 		}
    635 	}
    636 	for(int i=0;i<10;i++)
    637 	{
    638 		sum[st[id].nxt[i]]+=st[id].sum[i];
    639 	}
    640 	for(int i=0;i<10;i++) 
    641 	{
    642 		st[id].sum[i]=sum[i];
    643 		st[id].nxt[i]=i;
    644 	}
    645 }
    646 
    647 void update(int id, int l, int r, int ql, int qr, int u, int v)
    648 {
    649 	push(id,l,r);
    650 	if(ql>=r||l>=qr) return ;
    651 	if(ql<=l&&r<=qr)
    652 	{
    653 		st[id].nxt[u]=v;
    654 		push(id,l,r);
    655 		return ;
    656 	}
    657 	int mid=(l+r)>>1;
    658 	update(id*2,l,mid,ql,qr,u,v);
    659 	update(id*2+1,mid,r,ql,qr,u,v);
    660 	combine(id);
    661 }
    662 
    663 ll query(int id, int l, int r, int ql, int qr)
    664 {
    665 	push(id,l,r);
    666 	if(ql>=r||l>=qr) return 0;
    667 	if(ql<=l&&r<=qr)
    668 	{
    669 		ll sum=0;
    670 		for(int i=1;i<10;i++)
    671 		{
    672 			sum+=ll(i)*st[id].sum[i];
    673 		}
    674 		return sum;
    675 	}
    676 	int mid=(l+r)>>1;
    677 	return (query(id*2,l,mid,ql,qr)+query(id*2+1,mid,r,ql,qr));
    678 }
    679 
    680 int main()
    681 {
    682 	ios_base::sync_with_stdio(0); cin.tie(0);
    683 	int n, q; cin>>n>>q;
    684 	for(int i = 0; i < n; i++)
    685 	{
    686 		int x; cin>>x;
    687 		int cur=1;
    688 		for(int j = 0; j < 9; j++)
    689 		{
    690 			a[i][x%10] += cur;
    691 			x/=10;
    692 			cur*=10;
    693 			if(x==0) break;
    694 		}
    695 	}
    696 	build(1,0,n);
    697 	for(int i = 0; i < q; i++)
    698 	{
    699 		int type;
    700 		cin>>type;
    701 		if(type==1)
    702 		{
    703 			int l,r,u,v;
    704 			cin>>l>>r>>u>>v;
    705 			l--; r--;
    706 			update(1,0,n,l,r+1,u,v);
    707 		}
    708 		else
    709 		{
    710 			int l,r; cin>>l>>r;
    711 			l--; r--;
    712 			ll sum = query(1,0,n,l,r+1);
    713 			cout<<sum<<'\n';
    714 		}
    715 	}
    716 }
    717 ```
    718 
    719 **Replace All**
    720 
    721 Author : [zscoder](/profile/zscoder "Гроссмейстер zscoder")
    722 
    723 First, we solve the problem when there're no question marks, i.e. we find a way to calculate the number of good pairs of strings fast for a constant pair of strings *A* and *B*.
    724 
    725 Call a pair of strings (*S*, *T*) where |*S*| ≤ |*T*| coprime if *S* = *T* or *S* is a prefix of *T*, and if *T* = *S* + *X*, then (*X*, *S*) is also coprime. (*S*, *T*) where |*S*| > |*T*| is coprime iff (*T*, *S*) is coprime.
    726 
    727 If *A* = *B*, then all possible strings work. Thus, we assume *A* ≠ *B* from now on. We remove the longest common prefix of *A* and *B*. Thus, we can assume *A*[0] ≠ *B*[0]. Thus, either *S* is a prefix of *T* or *T* is a prefix of *S*. WLOG, *S* is a prefix of *T*. Let *T* = *S* + *X*. Now, *A* and *B* consists of only *S* and *X*. Using this, we can prove by induction on |*S*| + |*T*| that *S* and *T* must be coprime.
    728 
    729 One important property of coprime strings is that *S* + *T* = *T* + *S* holds. (again induction works here)
    730 
    731 Now, since the strings *S* and *T* needs to be coprime, we have *S* + *T* = *T* + *S*. This allows us to swap any neighbouring Ss and Ts (or 'A's and 'B's) in *A* and *B*, as the resulting strings will still be equal. Thus, swapping repeatedly allows us to sort the strings A and B. (the 'A's appear in front and 'B's appear at the back) Let *x**A*, *x**B*, *y**A*, *y**B* denote the number of As and Bs in the first string and second string respectively. If (*x**A*, *x**B*) > (*y**A*, *y**B*), then the answer is 0. We'll handle the case (*x**A*, *x**B*) = (*y**A*, *y**B*) later. Now, assume *x**A* > *y**A*, *x**B* < *y**B*. Thus, we have to solve the equation (*x**A* - *y**A*) copies of *S* = (*y**B* - *x**B*) copies of *T*.
    732 
    733 Now, let *x* = *x**A* - *y**A*, *y* = *y**B* - *x**B*. If *x* = *y*, then the solution is *S* = *T*. Otherwise, assume *x* > *y*. Then, |*S*| < |*T*|. So, by comparing, we again have *T* = *S* + *X*, for some nonempty binary string *X*. Note that *S* and *X* must be coprime too, so we can sort the second string as well. We cancel off the Ss on both sides to get (*x* - *y*)*S* = *yX*. Thus, this means that if (*S*, *T*) is a solution for (*x*, *y*), then (*S*, *X*) is a solution for (*x* - *y*, *y*). Note that repeating this process will eventually lead us to (1, 1). (this process is similar to Euclidean Algorithm)
    734 
    735 The answer for (1, 1) is the number of solutions to *S* = *T*. Let's denote the solution here as *X*. Doing some backtracking, we realize that the answer for (*x*, *y*) is equal to (X....X (*y* times), X...X (*x* times)). Note that we still have the condition |*S*|, |*T*| ≤ *N*, so we can translate this to an appropriate condition on the length of *X* and the answer is simply the number of binary strings of length not exceeding the maximum possible length of *X*.
    736 
    737 The only case that remains is that (*x**A*, *x**B*) = (*y**A*, *y**B*). In this case, any pair of coprime strings *S* and *T* will work. Thus, our task reduces to calculating the number of coprime pair of strings with length not exceeding *N*.
    738 
    739 We claim that the number of coprime pair of strings (*S*, *T*) with |*S*| = *p*, |*T*| = *q* is ![](https://espresso.codeforces.com/7aead411d9bea1233ad21ef2cd5882a110ae1487.png).
    740 
    741 If *p* = *q* the claim is obviously true. Otherwise, we can induct on *p* + *q* agin. If *q* > *p*, we can write *T* = *S* + *X* and then the number of coprime pairs of (*S*, *T*) is equal to the number of coprime pairs of (*S*, *X*), which by induction is equal to ![](https://espresso.codeforces.com/f44a09acacbd71c3903a9aaad394d16f56ff984c.png). This proves the claim.
    742 
    743 Thus, we just need to compute the sum of ![](https://espresso.codeforces.com/7aead411d9bea1233ad21ef2cd5882a110ae1487.png) for all 1 ≤ *p*, *q* ≤ *N*.
    744 
    745 Indeed, since *N* ≤ 3·105, it is enough to count the number of pairs (*p*, *q*) with *gcd* = *g* for all *g*.
    746 
    747 However, this is quite easy. Let *cnt*[*i*] denote the number of pairs (*p*, *q*) such that *p* and *q* are both divisible by *i*. Let *ans*[*i*] denote the number of pairs (*p*, *q*) with *gcd* = *i*. Then, ![](https://espresso.codeforces.com/2fb8d4899f2930b2c422cd7c6b936de899e738b7.png). Thus, this can be computed in ![](https://espresso.codeforces.com/06b2dfff448a3a9e0e9b5c879f5cda0ce1cecba5.png).
    748 
    749 Now, we need to find out how to calculate the sum of all these values on two strings *X* and *Y* with question marks. Handle the case when the two strings become equal separately.
    750 
    751 Let's first make a summary of the number of good pairs of strings for constant strings *A* and *B*. In fact, note that the formulaes above only depends on (*d**A*, *d**B*), the difference between the number of As in *A* and *B*, and the difference between the number of Bs in *A* and *B* (note that *d**A*, *d**B* can be negative)
    752 
    753 If *d**A* = *d**B* = 0, then the answer is the sum of ![](https://espresso.codeforces.com/7aead411d9bea1233ad21ef2cd5882a110ae1487.png) for all 1 ≤ *p*, *q* ≤ *N*, which as we have just saw can be precomputed in time.
    754 
    755 Otherwise, if *d**A*, *d**B* ≥ 0 or *d**A*, *d**B* ≤ 0, then there are no good pair of strings.
    756 
    757 Finally, in other cases, let *p* = |*d**A*|, *q* = |*d**B*|. Then, the answer is ![](https://espresso.codeforces.com/78507b0e65a043ea60ac19778f524cca10303783.png).
    758 
    759 This also means that we can compute the answer if we know *d**A* and *d**B* very fast. (worst case is ![](https://espresso.codeforces.com/e864584c28b3beb52a5d9a7cbbcda3d80a9d4515.png))
    760 
    761 Now, suppose in the strings *X* and *Y*, we have *a* and *b* question marks respectively. Additionally, suppose the current difference between the number of As and Bs of these strings is (*p*, *q*).
    762 
    763 If we choose *x* and *y* of the question marks from *X* and *Y* to be replaced with As, then the difference between As and Bs in the strings become (*p* + *x* - *y*, *q* + (*a* - *b*) - (*x* - *y*)). Let's denote *q* as *q* + *a* - *b* for simplicity. Thus, the difference is now written as (*p* + (*x* - *y*), *q* - (*x* - *y*)). The values of *x* and *y* can be any integer in the range [0, *a*] and [0, *b*] respectively. Suppose for all  - *b* ≤ *d* ≤ *a*, we know how many ways to assign the question marks have *x* - *y* = *d*. Then, we can iterate through all the *d*s one by one and compute the answer fast for each *d*.
    764 
    765 Thus, the final hurdle is to calculate the number of ways to obtain *x* - *y* = *d* for all possible *d* so that 0 ≤ *x* ≤ *a*, 0 ≤ *y* ≤ *b*. This is just the sum of ![](https://espresso.codeforces.com/ab2325d1e42d7075e21fef185cc4b3521d35fcf1.png) for all 0 ≤ *x* ≤ *a*. However, this is equal to ![](https://espresso.codeforces.com/c62866f5561e7244d73adb12b1d63125a130222c.png), as the number of ways to choose *b* + *d* objects from *a* + *b* objects is the same as the sum of the product of the number of ways to choose *x* objects from the first *a* objects and the number of ways to choose *b* + *d* - *x* objects from the first *b* objects for all 0 ≤ *a* ≤ *x*. Thus, this value can be computed in *O*(1) with precomputed factorials and inverse factorials (or you can maintain this value when we iterate through all *d*).
    766 
    767 Finally, don't forget to take care of the cases where it is possible for both strings to be equal.
    768 
    769 The time complexity of the solution is ![](https://espresso.codeforces.com/bec2049ed7fe79cd54abc80b05d0323658bf1a14.png).
    770 
    771 **Code**
    772 
    773 ```
    774 #include <bits/stdc++.h>
    775 #include <ext/pb_ds/assoc_container.hpp>
    776 #include <ext/pb_ds/tree_policy.hpp>
    777 
    778 using namespace std;
    779 using namespace __gnu_pbds;
    780 
    781 #define fi first
    782 #define se second
    783 #define mp make_pair
    784 #define pb push_back
    785 #define fbo find_by_order
    786 #define ook order_of_key
    787 
    788 typedef long long ll;
    789 typedef pair<ll,ll> ii;
    790 typedef vector<ll> vi;
    791 typedef long double ld; 
    792 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
    793 typedef set<int>::iterator sit;
    794 typedef map<int,int>::iterator mit;
    795 typedef vector<int>::iterator vit;
    796 
    797 const int MOD = 1e9 + 7;
    798 
    799 struct NumberTheory
    800 {
    801 	vector<ll> primes;
    802 	vector<bool> prime;
    803 	vector<ll> totient;
    804 	vector<ll> sumdiv;
    805 	vector<ll> bigdiv;
    806 	void Sieve(ll n)
    807 	{
    808 		prime.assign(n+1, 1);
    809 		prime[1] = false;
    810 		for(ll i = 2; i <= n; i++)
    811 		{
    812 			if(prime[i])
    813 			{
    814 				primes.pb(i);
    815 				for(ll j = i*2; j <= n; j += i)
    816 				{
    817 					prime[j] = false;
    818 				}
    819 			}
    820 		}
    821 	}
    822 	
    823 	ll phi(ll x)
    824 	{
    825 		map<ll,ll> pf;
    826 		ll num = 1; ll num2 = x;
    827 		for(ll i = 0; primes[i]*primes[i] <= x; i++)
    828 		{
    829 			if(x%primes[i]==0)
    830 			{
    831 				num2/=primes[i];
    832 				num*=(primes[i]-1);
    833 			}
    834 			while(x%primes[i]==0)
    835 			{
    836 				x/=primes[i];
    837 				pf[primes[i]]++;
    838 			}
    839 		}
    840 		if(x>1)
    841 		{
    842 			pf[x]++; num2/=x; num*=(x-1);
    843 		}
    844 		x = 1;
    845 		num*=num2;
    846 		return num;
    847 	}
    848 	
    849 	bool isprime(ll x)
    850 	{
    851 		if(x==1) return false;
    852 		for(ll i = 0; primes[i]*primes[i] <= x; i++)
    853 		{
    854 			if(x%primes[i]==0) return false;
    855 		}
    856 		return true;
    857 	}
    858 
    859 	void SievePhi(ll n)
    860 	{
    861 		totient.resize(n+1);
    862 		for (int i = 1; i <= n; ++i) totient[i] = i;
    863 		for (int i = 2; i <= n; ++i)
    864 		{
    865 			if (totient[i] == i)
    866 			{
    867 				for (int j = i; j <= n; j += i)
    868 				{
    869 					totient[j] -= totient[j] / i;
    870 				}
    871 			}
    872 		}
    873 	}
    874 	
    875 	void SieveSumDiv(ll n)
    876 	{
    877 		sumdiv.resize(n+1);
    878 		for(int i = 1; i <= n; ++i)
    879 		{
    880 			for(int j = i; j <= n; j += i)
    881 			{
    882 				sumdiv[j] += i;
    883 			}
    884 		}
    885 	}
    886 	
    887 	ll getPhi(ll n)
    888 	{
    889 		return totient[n];
    890 	}
    891 	
    892 	ll getSumDiv(ll n)
    893 	{
    894 		return sumdiv[n];
    895 	}
    896 	
    897 	ll modpow(ll a, ll b, ll mod)
    898 	{
    899 		ll r = 1;
    900 		if(b < 0) b += mod*100000LL;
    901 		while(b)
    902 		{
    903 			if(b&1) r = (r*a)%mod;
    904 			a = (a*a)%mod;
    905 			b>>=1;
    906 		}
    907 		return r;
    908 	}
    909 	
    910 	ll inv(ll a, ll mod)
    911 	{
    912 		return modpow(a, mod - 2, mod);
    913 	}
    914 	
    915 	ll invgeneral(ll a, ll mod)
    916 	{
    917 		ll ph = phi(mod);
    918 		ph--;
    919 		return modpow(a, ph, mod);
    920 	}
    921 	
    922 	void getpf(vector<ii>& pf, ll n)
    923 	{
    924 		for(ll i = 0; primes[i]*primes[i] <= n; i++)
    925 		{
    926 			int cnt = 0;
    927 			while(n%primes[i]==0)
    928 			{
    929 				n/=primes[i]; cnt++;
    930 			}
    931 			if(cnt>0) pf.pb(ii(primes[i], cnt));
    932 		}
    933 		if(n>1)
    934 		{
    935 			pf.pb(ii(n, 1));
    936 		}
    937 	}
    938 
    939 	//ll op;
    940 	void getDiv(vector<ll>& div, vector<ii>& pf, ll n, int i)
    941 	{
    942 		//op++;
    943 		ll x, k;
    944 		if(i >= pf.size()) return ;
    945 		x = n;
    946 		for(k = 0; k <= pf[i].se; k++)
    947 		{
    948 			if(i==int(pf.size())-1) div.pb(x);
    949 			getDiv(div, pf, x, i + 1);
    950 			x *= pf[i].fi;
    951 		}
    952 	}
    953 };
    954 
    955 NumberTheory nt;
    956 
    957 ll modpow(ll a, ll b)
    958 {
    959 	ll r = 1;
    960 	while(b)
    961 	{
    962 		if(b&1) r=(r*a)%MOD;
    963 		a=(a*a)%MOD;
    964 		b>>=1;
    965 	}
    966 	return r;
    967 }
    968 
    969 ll inv(ll a)
    970 {
    971 	return modpow(a,MOD-2);
    972 }
    973 
    974 ll n;
    975 ll cnt[300001];
    976 ll mob[300001];
    977 
    978 ll mobius(ll x)
    979 {
    980 	int cc = 0;
    981 	for(int i=0;nt.primes[i]*nt.primes[i]<=x;i++)
    982 	{
    983 		int z=0;
    984 		while(x%nt.primes[i]==0)
    985 		{
    986 			z++;
    987 			x/=nt.primes[i];
    988 		}
    989 		if(z>=2) return 0;
    990 		if(z>0) cc++;
    991 	}
    992 	if(x>1) cc++;
    993 	if(cc&1) return -1;
    994 	else return 1;
    995 }
    996 
    997 ll solve(ll x, ll y)
    998 {
    999 	if(x==0&&y==0)
   1000 	{
   1001 		for(int i=1;i<=n;i++)
   1002 		{
   1003 			cnt[i]=ll(n/i)*ll(n/i);
   1004 		}
   1005 		for(int i=1;i<=n;i++)
   1006 		{
   1007 			for(int j=2*i;j<=n;j+=i)
   1008 			{
   1009 				cnt[i]+=mob[j/i]*cnt[j];
   1010 			}
   1011 		}	
   1012 		ll ans = 0;
   1013 		ll cur = 2;
   1014 		for(int i=1;i<=n;i++)
   1015 		{
   1016 			cnt[i]%=MOD;
   1017 			if(cnt[i]<0) cnt[i]+=MOD;
   1018 			//cerr<<i<<' '<<cnt[i]<<'\n';
   1019 			ans=(ans+(cur*cnt[i])%MOD)%MOD;
   1020 			if(ans<0) ans+=MOD;
   1021 			cur=(cur*2)%MOD;
   1022 			if(cur<0) cur+=MOD;
   1023 		}
   1024 		return ans;
   1025 	}
   1026 	else if(x>=0&&y>=0)
   1027 	{
   1028 		return 0;
   1029 	}
   1030 	else if(x<=0&&y<=0)
   1031 	{
   1032 		return 0;
   1033 	}
   1034 	else
   1035 	{
   1036 		x=abs(x); y=abs(y);
   1037 		ll g = __gcd(x,y);
   1038 		x/=g; y/=g;
   1039 		ll k = n/max(x,y);
   1040 		ll ans = modpow(2,k+1)+MOD-2;
   1041 		while(ans>=MOD) ans-=MOD;
   1042 		return ans;
   1043 	}
   1044 }
   1045 
   1046 ll fact[600001];
   1047 ll ifact[600001];
   1048 ll inverse[600001];
   1049 
   1050 ll choose(ll n, ll r)
   1051 {
   1052 	if(r==0) return 1;
   1053 	ll ans = fact[n];
   1054 	ans=(ans*ifact[r])%MOD;
   1055 	ans=(ans*ifact[n-r])%MOD;
   1056 	if(ans<0) ans+=MOD;
   1057 	return ans;
   1058 }
   1059 
   1060 int main()
   1061 {
   1062 	ios_base::sync_with_stdio(0); cin.tie(0);
   1063 	string s, t;
   1064 	cin>>s>>t;
   1065 	cin>>n;
   1066 	fact[0]=1; ifact[0]=1;
   1067 	for(int i=1;i<=600000;i++)
   1068 	{
   1069 		fact[i]=(fact[i-1]*i)%MOD;
   1070 		if(fact[i]<0) fact[i]+=MOD;
   1071 		ifact[i]=inv(fact[i]);
   1072 		inverse[i]=inv(i);
   1073 	}
   1074 	nt.Sieve(300001);
   1075 	for(int i=2;i<=n;i++)
   1076 	{
   1077 		mob[i]=mobius(i);
   1078 	}
   1079 	ll sa, sb, sc; //sa = # of As in s, sb = # of Bs in s, sc = # of ?s in s
   1080 	ll ta, tb, tc;
   1081 	sa=sb=sc=ta=tb=tc=0;
   1082 	ll same = 1; //number of ways to fill in ?s such that |S| = |T|
   1083 	if(s.length()!=t.length()) same=0;
   1084 	else
   1085 	{
   1086 		for(int i=0;i<s.length();i++)
   1087 		{
   1088 			if(s[i]=='?'&&t[i]=='?') same=(same*2)%MOD;
   1089 			else if(s[i]=='?'||t[i]=='?')
   1090 			{
   1091 				
   1092 			}
   1093 			else if(s[i]==t[i])
   1094 			{
   1095 				
   1096 			}
   1097 			else
   1098 			{
   1099 				same=0;
   1100 			}
   1101 		}
   1102 	}
   1103 	for(int i=0;i<s.length();i++)
   1104 	{
   1105 		if(s[i]=='A') sa++;
   1106 		else if(s[i]=='B') sb++;
   1107 		else sc++;
   1108 	}
   1109 	for(int i=0;i<t.length();i++)
   1110 	{
   1111 		if(t[i]=='A') ta++;
   1112 		else if(t[i]=='B') tb++;
   1113 		else tc++;
   1114 	}
   1115 	ll ans = 0;
   1116 	ll c = 1;
   1117 	int cntt=0;
   1118 	for(ll i = sa - ta - tc; i <= sa - ta + sc; i++)
   1119 	{
   1120 		if(i==0)
   1121 		{
   1122 			ll cc = (c-same)%MOD;
   1123 			if(cc<0) cc+=MOD;
   1124 			ans=(ans+(cc*solve(i,sa+sb+sc-ta-tb-tc-i))%MOD)%MOD;
   1125 			ll tmp = modpow(2,n+1)+MOD-2;
   1126 			while(tmp>=MOD) tmp-=MOD;
   1127 			tmp=(tmp*tmp)%MOD;
   1128 			ans=(ans+(same*tmp)%MOD)%MOD;
   1129 		}
   1130 		else
   1131 		{
   1132 			ans=(ans+(c*solve(i,sa+sb+sc-ta-tb-tc-i))%MOD)%MOD;
   1133 		}
   1134 		if(ans<0) ans+=MOD;
   1135 		c=(c*inverse[cntt+1])%MOD;
   1136 		c=(c*(sc+tc-cntt))%MOD;
   1137 		if(c<0) c+=MOD;
   1138 		cntt++;
   1139 	}
   1140 	cout<<ans<<'\n';
   1141 }
   1142 ```