codeforces-scrape

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

1708.md (17598B)


      1 Source: https://codeforces.com/blog/entry/104930
      2 
      3 [1708A - Разностные операции](/contest/1708/problem/A "Codeforces Round 808 (Div. 2)")
      4 
      5 idea: [Imakf](/profile/Imakf "Мастер Imakf")
      6 
      7 **Solution**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 By [Imakf](/profile/Imakf "Мастер Imakf")
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 
     18 #define debug(...) fprintf(stderr ,__VA_ARGS__)
     19 #define LL long long
     20 
     21 const LL MOD = 1e9 + 7;
     22 const int MX = 1e5 + 23;
     23 
     24 int read(){
     25 	char k = getchar(); LL x = 0;
     26 	while(k < '0' || k > '9') k = getchar();
     27 	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
     28 	return x;
     29 }
     30 
     31 int n ,a[MX];
     32 void solve(){
     33 	n = read();
     34 	for(int i = 1 ; i <= n ; ++i) a[i] = read();
     35 	int ok = 1;
     36 	for(int i = 1 ; i <= n ; ++i){
     37 		if(a[i] % a[1]) ok = false;
     38 	}
     39 	puts(ok ? "YES" : "NO");
     40 }
     41 
     42 int main(){
     43 	int T = read();
     44 	while(T--) solve();
     45 	return 0;
     46 }
     47 ```
     48 
     49 [1708B - Различие НОДов](/contest/1708/problem/B "Codeforces Round 808 (Div. 2)")
     50 
     51 idea: [waaitg](/profile/waaitg "Мастер waaitg")
     52 
     53 **Solution**
     54 
     55 Tutorial is loading...
     56 
     57 **Code**
     58 
     59 By [Imakf](/profile/Imakf "Мастер Imakf")
     60 
     61 ```
     62 #include <bits/stdc++.h>
     63 
     64 #define debug(...) fprintf(stderr ,__VA_ARGS__)
     65 #define __FILE(x)\
     66 	freopen(#x".in" ,"r" ,stdin);\
     67 	freopen(#x".out" ,"w" ,stdout)
     68 #define LL long long
     69 
     70 const int MX = 1e5 + 23;
     71 const LL MOD = 998244353;
     72 
     73 int read(){
     74 	char k = getchar(); int x = 0;
     75 	while(k < '0' || k > '9') k = getchar();
     76 	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
     77 	return x;
     78 }
     79 
     80 int a[MX];
     81 void solve(){
     82 	int n = read() ,l = read() ,r = read();
     83 	int ok = 1;
     84 	for(int i = 1 ; i <= n ; ++i){
     85 		a[i] = ((l - 1) / i + 1) * i;
     86 		ok = ok && a[i] <= r;
     87 	}
     88 	if(ok){
     89 		puts("YES");
     90 		for(int i = 1 ; i <= n ; ++i)
     91 			printf("%d%c" ,a[i] ," \n"[i == n]);
     92 	}
     93 	else puts("NO");
     94 }
     95 
     96 int main(){
     97 	int T = read();
     98 	for(int i = 1 ; i <= T ; ++i){
     99 		solve();
    100 	}
    101 	return 0;
    102 }
    103 ```
    104 
    105 [1707A - Дореми и её IQ](/contest/1707/problem/A "Codeforces Round 808 (Div. 1)")
    106 
    107 idea: [Imakf](/profile/Imakf "Мастер Imakf")
    108 
    109 **Solution**
    110 
    111 Tutorial is loading...
    112 
    113 **Code of solution 1**
    114 
    115 By [Imakf](/profile/Imakf "Мастер Imakf")
    116 
    117 ```
    118 #include <bits/stdc++.h>
    119 
    120 #define debug(...) fprintf(stderr ,__VA_ARGS__)
    121 #define __FILE(x)\
    122 	freopen(#x".in" ,"r" ,stdin);\
    123 	freopen(#x".out" ,"w" ,stdout)
    124 #define LL long long
    125 
    126 const int MX = 5e5 + 23;
    127 const LL MOD = 998244353;
    128 
    129 int read(){
    130 	char k = getchar(); int x = 0;
    131 	while(k < '0' || k > '9') k = getchar();
    132 	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
    133 	return x;
    134 }
    135 
    136 int n ,a[MX] ,q ,choose[MX];
    137 bool check(int mid){
    138 	for(int i = 1 ; i <= n ; ++i) choose[i] = 0;
    139 	int iq = q;
    140 	for(int i = 1 ; i < mid ; ++i)
    141 		if(a[i] <= iq) choose[i] = 1;
    142 	for(int i = mid ; i <= n ; ++i){
    143 		choose[i] = 1;
    144 		if(iq == 0) return 0;
    145 		if(a[i] > iq) --iq;
    146 		
    147 	}
    148 	if(iq < 0) return 0;
    149 	return 1;
    150 }
    151 
    152 void solve(){
    153 	n = read() ,q = read();
    154 	for(int i = 1 ; i <= n ; ++i)
    155 		a[i] = read();
    156 	int l = 1 ,r = n ,mid;
    157 	while(l <= r){
    158 		mid = (l + r) >> 1;
    159 		if(check(mid)) r = mid - 1;
    160 		else l = mid + 1;
    161 	}
    162 	// [r + 1 ,n] is selected
    163 	check(r + 1);
    164 	for(int i = 1 ; i <= n ; ++i)
    165 		printf("%d" ,choose[i]);
    166 	puts("");
    167 }
    168 
    169 int main(){
    170 	int T = read();
    171 	for(int i = 1 ; i <= T ; ++i){
    172 		solve();
    173 	}
    174 	return 0;
    175 }
    176 ```
    177 
    178 **Code of solution 2**
    179 
    180 By [waaitg](/profile/waaitg "Мастер waaitg")
    181 
    182 ```
    183 #include<cstdio>
    184 int a[100005],b[100005];
    185 int main(){
    186 	int T;
    187 	scanf("%d",&T);
    188 	while(T--){
    189 		int n,iq;
    190 		scanf("%d%d",&n,&iq);
    191 		for(int i=1;i<=n;++i)
    192 			scanf("%d",&a[i]);
    193 		int sum=0,nq=0;
    194 		for(int i=n;i>=1;--i){
    195 			if(a[i]<=nq)b[i]=1;
    196 			else if(nq<iq)++nq,b[i]=1; 
    197 			else b[i]=0;
    198 		} 
    199 		for(int i=1;i<=n;++i)
    200 			printf("%d",b[i]);
    201 		puts("");
    202 	}
    203 	return 0;
    204 }
    205 ```
    206 
    207 [1707B - Разностный массив](/contest/1707/problem/B "Codeforces Round 808 (Div. 1)")
    208 
    209 idea: [Imakf](/profile/Imakf "Мастер Imakf") and [waaitg](/profile/waaitg "Мастер waaitg")
    210 
    211 Unfortunately, a harder version of this problem has appeared in a codechef contest [here](https://www.codechef.com/START33B/problems/ARRAY_OPS).
    212 
    213 In fact, this problem was come up with more than 1 year ago, earlier than the problem in that codechef contest. We are sorry again.
    214 
    215 **Solution**
    216 
    217 Tutorial is loading...
    218 
    219 **Code**
    220 
    221 By [waaitg](/profile/waaitg "Мастер waaitg")
    222 
    223 ```
    224 #include<cstdio>
    225 #include<cstring>
    226 #include<iostream>
    227 #include<algorithm>
    228 #define ch() getchar()
    229 #define pc(x) putchar(x)
    230 using namespace std;
    231 template<typename T>void read(T&x){
    232 	static char c;static int f;
    233 	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
    234 	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
    235 }
    236 template<typename T>void write(T x){
    237 	static char q[65];int cnt=0;
    238 	if(x<0)pc('-'),x=-x;
    239 	q[++cnt]=x%10,x/=10;
    240 	while(x)
    241 		q[++cnt]=x%10,x/=10;
    242 	while(cnt)pc(q[cnt--]+'0');
    243 }
    244 const int maxn=100005;
    245 int a[maxn];
    246 int main(){
    247 	int T;read(T);
    248 	while(T--){
    249 		int n;read(n);
    250 		for(int i=1;i<=n;++i)read(a[i]);
    251 		for(int i=n-1;i>=1;--i){
    252 			int pre=a[i+1],ok=false;
    253 			for(int j=i;j>=1;--j){
    254 				ok=(a[j]==0);
    255 				pre-=(a[j]=pre-a[j]);
    256 				if(ok){
    257 					sort(a+j,a+i+1);
    258 					break;
    259 				}
    260 			}
    261 			if(!ok)
    262 				sort(a+1,a+i+1);
    263 		}
    264 		write(a[1]),pc('\n');
    265 	}
    266 	return 0;
    267 }
    268 /*
    269 _|_|_|_|        _|_|      _|      _|   _|_|_|_|_|   _|_|_|_|_|   _|
    270 _|      _|    _|    _|    _|_|    _|       _|       _|           _|
    271 _|      _|   _|      _|   _| _|   _|       _|       _|           _|
    272 _|      _|   _|_|_|_|_|   _|  _|  _|       _|       _|_|_|_|_|   _|
    273 _|      _|   _|      _|   _|   _| _|       _|       _|           _|
    274 _|      _|   _|      _|   _|    _|_|       _|       _|           _|
    275 _|_|_|_|     _|      _|   _|      _|   _|_|_|_|_|   _|_|_|_|_|   _|_|_|_|_|
    276 
    277 _|_|_|_|_|   _|      _|   _|_|_|_|     _|      _|
    278     _|        _|    _|    _|      _|    _|    _|
    279     _|         _|  _|     _|      _|     _|  _|
    280     _|          _|_|      _|      _|      _|_|
    281     _|         _|  _|     _|      _|       _|
    282     _|        _|    _|    _|      _|       _|
    283     _|       _|      _|   _|_|_|_|         _|
    284 
    285 _|             _|_|_|     _|      _|   _|_|_|_|_|
    286 _|           _|      _|   _|      _|   _|
    287 _|           _|      _|    _|    _|    _|
    288 _|           _|      _|    _|    _|    _|_|_|_|_|
    289 _|           _|      _|     _|  _|     _|
    290 _|           _|      _|      _|_|      _|
    291 _|_|_|_|_|     _|_|_|         _|       _|_|_|_|_|
    292 
    293 _|_|_|_|_|   _|      _|   _|_|_|_|_|
    294     _|        _|    _|        _|
    295     _|         _|  _|         _|
    296     _|          _|_|          _|
    297     _|           _|           _|
    298     _|           _|           _|
    299     _|           _|           _|
    300 
    301 Created by xiaolilsq.
    302 */
    303 ```
    304 
    305 [1707C - Деревья поиска в глубину](/contest/1707/problem/C "Codeforces Round 808 (Div. 1)")
    306 
    307 idea: [waaitg](/profile/waaitg "Мастер waaitg")
    308 
    309 **Solution**
    310 
    311 Tutorial is loading...
    312 
    313 **Code**
    314 
    315 By [waaitg](/profile/waaitg "Мастер waaitg")
    316 
    317 ```
    318 #include<cstdio>
    319 #include<cstring>
    320 #include<iostream>
    321 #include<algorithm>
    322 #define ch() getchar()
    323 #define pc(x) putchar(x)
    324 using namespace std;
    325 template<typename T>void read(T&x){
    326 	static char c;static int f;
    327 	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
    328 	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
    329 }
    330 template<typename T>void write(T x){
    331 	static char q[65];int cnt=0;
    332 	if(x<0)pc('-'),x=-x;
    333 	q[++cnt]=x%10,x/=10;
    334 	while(x)
    335 		q[++cnt]=x%10,x/=10;
    336 	while(cnt)pc(q[cnt--]+'0');
    337 }
    338 const int maxn=100005,maxm=200005;
    339 int par[maxn];
    340 int AC(int x){
    341 	return par[x]==x?x:par[x]=AC(par[x]);
    342 }
    343 struct Edge{
    344 	int v,nt;
    345 	Edge(int v=0,int nt=0):
    346 		v(v),nt(nt){}
    347 }e[maxn*2],es[maxm];
    348 int hd[maxn],num;
    349 void qwq(int u,int v){
    350 	e[++num]=Edge(v,hd[u]),hd[u]=num;
    351 }
    352 int dp[maxn];
    353 int pa[maxn][20];
    354 void dfs(int u,int p){
    355 	pa[u][0]=p;
    356 	for(int j=1;(1<<j)<=dp[u];++j)
    357 		pa[u][j]=pa[pa[u][j-1]][j-1];
    358 	for(int i=hd[u];i;i=e[i].nt){
    359 		int v=e[i].v;
    360 		if(v==p)continue;
    361 		dp[v]=dp[u]+1;dfs(v,u);
    362 	}
    363 }
    364 int jump(int x,int t){
    365 	for(int cn=0;t;t>>=1,++cn)
    366 		if(t&1)x=pa[x][cn];
    367 	return x;
    368 }
    369 int lca(int x,int y){
    370 	if(dp[x]>dp[y])x=jump(x,dp[x]-dp[y]);
    371 	if(dp[y]>dp[x])y=jump(y,dp[y]-dp[x]);
    372 	if(x==y)return x;
    373 	for(int t=19;t>=0;--t)
    374 		if(pa[x][t]!=pa[y][t])
    375 			x=pa[x][t],y=pa[y][t];
    376 	return pa[x][0];
    377 }
    378 int vis[maxn];
    379 char s[maxn];
    380 void pushdown(int u,int p){
    381 	if(vis[u]==0)s[u]='1';
    382 	else s[u]='0';
    383 	for(int i=hd[u];i;i=e[i].nt){
    384 		int v=e[i].v;
    385 		if(v==p)continue;
    386 		vis[v]+=vis[u];
    387 		pushdown(v,u);
    388 	}
    389 }
    390 int main(){
    391 	int n,m;
    392 	read(n),read(m);
    393 	for(int i=1;i<=n;++i)
    394 		par[i]=i;
    395 	int tp=0;
    396 	for(int i=1;i<=m;++i){
    397 		int u,v;
    398 		read(u),read(v);
    399 		if(AC(u)==AC(v)){
    400 			es[++tp]=Edge(u,v);
    401 		}
    402 		else{
    403 			par[AC(u)]=AC(v);
    404 			qwq(u,v),qwq(v,u);
    405 		}
    406 	}
    407 	int root=1;
    408 	dfs(root,0);
    409 	for(int i=1;i<=tp;++i){
    410 		int u=es[i].v,v=es[i].nt;
    411 		if(dp[u]>dp[v])u^=v^=u^=v;
    412 		int w=lca(u,v);
    413 		if(u==w){
    414 			--vis[v];
    415 			++vis[jump(v,dp[v]-dp[u]-1)];
    416 		}
    417 		else{
    418 			++vis[root];
    419 			--vis[u];
    420 			--vis[v];
    421 		}
    422 	}
    423 	pushdown(root,0);
    424 	s[n+1]='\0';
    425 	printf("%s\n",s+1);
    426 	return 0;
    427 }
    428 ```
    429 
    430 [1707D - Частичные виртуальные деревья](/contest/1707/problem/D "Codeforces Round 808 (Div. 1)")
    431 
    432 idea: [Imakf](/profile/Imakf "Мастер Imakf") and [waaitg](/profile/waaitg "Мастер waaitg")
    433 
    434 **Solution**
    435 
    436 Tutorial is loading...
    437 
    438 **Code**
    439 
    440 By [Imakf](/profile/Imakf "Мастер Imakf")
    441 
    442 ```
    443 #include <bits/stdc++.h>
    444  
    445 #define debug(...) fprintf(stderr ,__VA_ARGS__)
    446 #define __FILE(x)\
    447 	freopen(#x".in" ,"r" ,stdin);\
    448 	freopen(#x".out" ,"w" ,stdout)
    449 #define LL long long
    450  
    451 const int MX = 2000 + 23;
    452  
    453 LL MOD;
    454  
    455 using namespace std;
    456  
    457 int read(){
    458 	char k = getchar(); int x = 0;
    459 	while(k < '0' || k > '9') k = getchar();
    460 	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
    461 	return x;
    462 }
    463  
    464 int head[MX] ,tot = 1;
    465 struct edge{
    466 	int node ,next;
    467 }h[MX << 1];
    468 void addedge(int u ,int v ,int flg = 1){
    469 	// if(flg) debug("%d %d\n" ,u ,v);
    470 	h[++tot] = (edge){v ,head[u]} ,head[u] = tot;
    471 	if(flg) addedge(v ,u ,false);
    472 }
    473  
    474 int n ,dp[MX][MX] ,S[MX][MX] ,suf[MX][MX] ,pre[MX][MX];
    475 void dapai(int x ,int f){
    476 	int ch = 0;
    477 	for(int i = head[x] ,d ; i ; i = h[i].next){
    478 		if((d = h[i].node) == f) continue;
    479 		dapai(d ,x);
    480 	}
    481 	for(int i = head[x] ,d ; i ; i = h[i].next){
    482 		if((d = h[i].node) == f) continue;
    483 		++ch;
    484 		for(int j = 0 ; j <= n ; ++j){
    485 			suf[ch][j] = pre[ch][j] = S[d][j];
    486 		}
    487 	}
    488  
    489 	if(!ch){
    490 		for(int i = 1 ; i <= n ; ++i){
    491 			dp[x][i] = 1 % MOD;
    492 			S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
    493 		}
    494 		return ;
    495 	}
    496 	for(int j = 0 ; j <= n ; ++j){
    497 		for(int i = 1 ; i <= ch ; ++i)
    498 			pre[i][j] = 1LL * pre[i][j] * pre[i - 1][j] % MOD;
    499 		for(int i = ch ; i >= 1 ; --i)
    500 			suf[i][j] = 1LL * suf[i][j] * suf[i + 1][j] % MOD;
    501 	}
    502 	for(int i = 1 ; i <= n ; ++i) dp[x][i] = pre[ch][i];
    503 	if(x != 1) for(int i = head[x] ,d ,c = 0 ; i ; i = h[i].next){
    504 		if((d = h[i].node) == f) continue;
    505 		++c;
    506 		LL sum = 0;
    507 		for(int mx = 1 ; mx <= n ; ++mx){
    508 			dp[x][mx] = (dp[x][mx] + sum * dp[d][mx]) % MOD;
    509 			sum = (sum + 1LL * pre[c - 1][mx] * suf[c + 1][mx]) % MOD;
    510 		}
    511 	}
    512 	for(int i = 1 ; i <= ch ; ++i)
    513 		for(int j = 0 ; j <= n ; ++j)
    514 			suf[i][j] = pre[i][j] = 1 % MOD;
    515 	for(int i = 1 ; i <= n ; ++i)
    516 		S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
    517 }
    518  
    519 int C[MX][MX];
    520 void init(){
    521 	for(int i = 0 ; i < MX ; ++i) C[i][0] = 1 % MOD;
    522 	for(int i = 1 ; i < MX ; ++i)
    523 		for(int j = 1 ; j < MX ; ++j)
    524 			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    525 }
    526  
    527 int main(){
    528     
    529     n = read() ,MOD = read();
    530 	init();
    531 	
    532 	for(int i = 0 ; i < MX ; ++i)
    533 		for(int j = 0 ; j < MX ; ++j)
    534 			suf[i][j] = pre[i][j] = 1 % MOD;
    535 			
    536 	
    537 	 
    538 	for(int i = 2 ; i <= n ; ++i){
    539 		addedge(read() ,read());
    540 		// addedge(rand() % (i - 1) + 1 ,i);
    541 	}
    542 	
    543 	dapai(1 ,0);
    544 	
    545 	for(int i = 1 ; i < n ; ++i){
    546 		LL ans = 0;
    547 		for(int j = 1 ; j <= i ; ++j){
    548 			ans += ((i - j) & 1 ? -1LL : 1LL) * C[i][j] * dp[1][j] % MOD;
    549 		}
    550 		ans = (ans % MOD + MOD) % MOD;
    551 		printf("%lld%c" ,ans ," \n"[i == n]);
    552 	}
    553 	return 0;
    554 }
    555 ```
    556 
    557 [1707E - Замена](/contest/1707/problem/E "Codeforces Round 808 (Div. 1)")
    558 
    559 idea: [Wolam](/profile/Wolam "Кандидат в мастера Wolam"), [Imakf](/profile/Imakf "Мастер Imakf") and [waaitg](/profile/waaitg "Мастер waaitg")
    560 
    561 **Solution**
    562 
    563 Tutorial is loading...
    564 
    565 **Code**
    566 
    567 By [waaitg](/profile/waaitg "Мастер waaitg")
    568 
    569 ```
    570 #include<cstdio>
    571 #include<cstring>
    572 #include<iostream>
    573 #include<algorithm>
    574 #define ch() getchar()
    575 #define pc(x) putchar(x)
    576 using namespace std;
    577 template<typename T>void read(T&x){
    578 	static char c;static int f;
    579 	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
    580 	for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f;
    581 }
    582 template<typename T>void write(T x){
    583 	static char q[64];int cnt=0;
    584 	if(x==0)return pc('0'),void();
    585 	if(x<0)pc('-'),x=-x;
    586 	while(x)q[cnt++]=x%10+'0',x/=10;
    587 	while(cnt--)pc(q[cnt]);
    588 }
    589 const int maxn=100005,maxq=100005,maxt=34;
    590 const int inf=0x3f3f3f3f;
    591 int a[maxn];
    592 struct Segment{
    593 	int l,r;
    594 	Segment(int l=inf,int r=-inf):
    595 		l(l),r(r){}
    596 	Segment operator * (const Segment o)const{
    597 		return Segment(min(l,o.l),max(r,o.r));
    598 	}
    599 	bool operator != (const Segment o)const{
    600 		return l!=o.l||r!=o.r;
    601 	}
    602 	void input(void){
    603 		read(l),read(r);
    604 	}
    605 }sg[maxt][maxn],tr[maxn],qy[maxq];
    606 int n;
    607 void res(void){
    608 	for(int i=1;i<n;++i)
    609 		tr[i]=Segment();
    610 }
    611 void add(int p,Segment v){
    612 	while(p<n){
    613 		tr[p]=tr[p]*v;
    614 		p+=(p&(-p));
    615 	}
    616 }
    617 Segment ask(int p){
    618 	Segment re;
    619 	while(p){
    620 		re=re*tr[p];
    621 		p^=(p&(-p));
    622 	}
    623 	return re;
    624 }
    625 struct Edge{
    626 	int v,w,nt;
    627 	Edge(int v=0,int w=0,int nt=0):
    628 		v(v),w(w),nt(nt){}
    629 }e[maxn];
    630 int num,hd[maxn];
    631 void ins(int u,int v,int w){
    632 	e[++num]=Edge(v,w,hd[u]),hd[u]=num;
    633 }
    634 int st[maxq],tp;
    635 long long Ans[maxq];
    636 int main(){
    637 	int q;read(n),read(q);
    638 	if(n==1){while(q--)puts("0");return 0;}
    639 	for(int i=1;i<=n;++i)read(a[i]);
    640 	for(int i=1;i<n;++i){
    641 		 if(a[i]<=a[i+1])
    642 		 	sg[0][i]=Segment(a[i],a[i+1]);
    643 		else
    644 			sg[0][i]=Segment(a[i+1],a[i]);
    645 	}
    646 	for(int i=1;i<maxt;++i){
    647 		for(int j=1;j<n;++j){
    648 			if(sg[i-1][j].l>=sg[i-1][j].r)sg[i][j]=Segment();
    649 			else ins(sg[i-1][j].l,sg[i-1][j].r-1,j);
    650 		}
    651 		res();
    652 		for(int j=n-1;j>=1;--j){
    653 			add(j,sg[i-1][j]);
    654 			for(int k=hd[j];k;k=e[k].nt){
    655 				sg[i][e[k].w]=ask(e[k].v);
    656 			}
    657 			hd[j]=0;
    658 		}
    659 		num=0;
    660 	}
    661 	for(int i=1;i<=q;++i){
    662 		qy[i].input();
    663 		if(qy[i].l==qy[i].r)Ans[i]=-2;
    664 		else ins(qy[i].l,qy[i].r-1,i);
    665 	}
    666 	res();
    667 	for(int i=n-1;i>=1;--i){
    668 		add(i,sg[maxt-1][i]);
    669 		for(int j=hd[i];j;j=e[j].nt){
    670 			if(i==1&&e[j].v==n-1)
    671 				Ans[e[j].w]=-1;
    672 			else if(ask(e[j].v)!=Segment(1,n))
    673 				Ans[e[j].w]=-2;
    674 			else
    675 				st[++tp]=e[j].w;
    676 		}
    677 		hd[i]=0;
    678 	}
    679 	num=0;
    680 	for(int i=maxt-2;~i;--i){
    681 		for(int j=1;j<=tp;++j){
    682 			ins(qy[st[j]].l,qy[st[j]].r-1,st[j]);
    683 		}
    684 		res();
    685 		for(int j=n-1;j>=1;--j){
    686 			add(j,sg[i][j]);
    687 			for(int k=hd[j];k;k=e[k].nt){
    688 				Segment tmp=ask(e[k].v);
    689 				int id=e[k].w;
    690 				if(tmp!=Segment(1,n))
    691 					Ans[id]|=(1ll<<i),qy[id]=tmp;
    692 			}
    693 			hd[j]=0;
    694 		}
    695 		num=0;
    696 	}
    697 	for(int i=1;i<=q;++i)
    698 		write(++Ans[i]),pc('\n');
    699 	return 0;
    700 }
    701 ```
    702 
    703 [1707F - Бугабу](/contest/1707/problem/F "Codeforces Round 808 (Div. 1)")
    704 
    705 This is a noun almost one year ago when this problem came out.
    706 
    707 idea: [Imakf](/profile/Imakf "Мастер Imakf") and [waaitg](/profile/waaitg "Мастер waaitg")
    708 
    709 **Solution**
    710 
    711 Tutorial is loading...
    712 
    713 **Code**
    714 
    715 By [waaitg](/profile/waaitg "Мастер waaitg")
    716 
    717 ```
    718 #include<cstdio>
    719 #include<cstring>
    720 #include<iostream>
    721 #include<algorithm>
    722 #include<assert.h>
    723 #define ch() getchar()
    724 #define pc(x) putchar(x)
    725 template<typename T>void read(T&x){
    726 	static char c;static int f;
    727 	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
    728 	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
    729 }
    730 template<typename T>void write(T x){
    731 	static char q[65];int cnt=0;
    732 	if(x<0)pc('-'),x=-x;
    733 	q[++cnt]=x%10,x/=10;
    734 	while(x)
    735 		q[++cnt]=x%10,x/=10;
    736 	while(cnt)pc(q[cnt--]+'0');
    737 }
    738 const int maxn=20000005;
    739 struct Count{
    740 	int pos,val;
    741 	Count(int pos=-1,int val=-1):
    742 		pos(pos),val(val){}
    743 };
    744 int plus(int x,int y){
    745 	return (x<0||y<0)?-1:x+y;
    746 }
    747 Count operator + (const Count A,const Count B){
    748 	int Ap=A.pos,Bp=B.pos,va=plus(A.val,B.val);
    749 	if(~Ap&&~Bp)return Ap^Bp?Count():Count(Ap|Bp,va);
    750 	if(~Ap||~Bp)return Count(Ap&Bp,va);
    751 	return Count(-1,va);
    752 }
    753 Count operator * (const Count A,const Count B){
    754 	int Ap=A.pos,Bp=B.pos,va=plus(A.val,B.val);
    755 	if(~Ap&&~Bp)return Count(Ap^Bp,va);
    756 	if(~Ap||~Bp)return Count(-1,va);
    757 	return Count(-1,plus(va,1));
    758 }
    759 int c[maxn];
    760 int tn,Op[maxn],Cn[maxn];
    761 Count dp[maxn];
    762 int t,hb[maxn],rev[maxn];
    763 void pushup(int p){
    764 	int l=p<<1,r=l|1;
    765 	dp[p]=((t&hb[p])?(dp[l]+dp[r]):(dp[l]*dp[r]));
    766 }
    767 int va1,sum;
    768 void ins(int i){
    769 	int p=rev[(i&(tn-1))];
    770 	if(~c[i])Op[p]^=c[i];else ++Cn[p];
    771 	if(dp[p+tn].pos>0)--va1;else sum-=dp[p+tn].val;
    772 	dp[p+tn]=(Cn[p]?Count(-1,Cn[p]-1):Count(Op[p],0));
    773 	if(dp[p+tn].pos>0)++va1;else sum+=dp[p+tn].val;
    774 }
    775 void del(int i){
    776 	int p=rev[(i&(tn-1))];
    777 	if(~c[i])Op[p]^=c[i];else --Cn[p];
    778 }
    779 int power(int a,int x,int p){
    780 	if(x==-1)return 0;
    781 	int re=1;
    782 	while(x){
    783 		if(x&1)re=1ll*re*a%p;
    784 		a=1ll*a*a%p;x>>=1;
    785 	}
    786 	return re;
    787 }
    788 int main(){
    789 	int n,m,w;
    790 	read(n),read(m),read(t),read(w);
    791 	memset(c,-1,sizeof c);
    792 	for(int i=1;i<=m;++i){
    793 		int d;read(d);--d;read(c[d]);
    794 	}
    795 	tn=(n&(-n));
    796 	hb[0]=0;hb[1]=1;
    797 	for(int i=2;i<tn*2;++i)
    798 		hb[i]=(hb[i>>1]<<1);
    799 	int cn=-1;for(;(1<<(cn+1))<tn;++cn);
    800 	for(int i=1;i<tn;++i)
    801 		rev[i]=(rev[i>>1]>>1)|((i&1)<<cn);
    802 	for(int i=0;i<tn;++i)dp[i+tn].val=0;
    803 	for(int i=0;i<n;++i)ins(i);
    804 	if(t<tn)for(int i=tn-1;i>=1;--i)pushup(i);
    805 	int q;read(q);
    806 	while(q--){
    807 		int f;read(f);--f;
    808 		del(f);read(c[f]);ins(f);
    809 		int p;read(p);
    810 		if(t>=tn){
    811 			write(va1?0:power((1<<w)%p,sum,p));
    812 		}
    813 		else{
    814 			int now=(rev[(f&(tn-1))]|tn);while(now>>=1)pushup(now);
    815 			write(power((1<<w)%p,plus(dp[1].val,dp[1].pos==-1),p));
    816 		}
    817 		pc('\n');
    818 	}
    819 	return 0;
    820 }
    821 ```