2025.2.17
A: Sede de Sal
As operações que exigem custo adicional são executadas no máximo uma vez. Portanto, existem três cenários. O primeiro é saltar diretamente para a frente e gastar um custo extra para recuar. O segundo é não realizar nenhuma operação com custo adicional; ambos são simples. No primeiro caso, basta consultar o mínimo de prefixo. Para o segundo, podemos usar a técnica de escalada binária para pré-processar ( f_{i,j} ), que indica a posição alcançada a partir de ( j ) avançando ( 2^i ) passos. O único cenário que requer atenção é quando se faz um salto primeiro e depois avança até o destino. Durante a competição, mantive a abordagem de saltar para trás, mas acabei elaborando uma maneira incorreta de estimar a resposta, que felizmente não foi desafiada. A escalada binária de trás para frente é complicada. A escalada binária da frente para trás, definindo ( g_{i,j} ) como o custo mínimo do ponto mais distante dentro do alcance de ( 2^i ) passos a partir de ( j ) até ( j ), permite consultas eficientes após o pré-processamento. Quando percebe-se que a escalada binária de trás para frente torna difícil determinar o custo devido à incerteza do ponto de partida, deve-se considerar rapidamente a abordagem da frente para trás, em vez de tentar corrigir a estimativa da resposta para aumentar a precisão.
B: Trio de Cafés
Vou explicar a pontuação parcial. Minha primeira abordagem para resolver com força bruta foi armazenar todas as operações. Observando que a resposta final para diferentes limites superiores ( x ) possui monotonicidade, utilizei a busca binária para encontrar o valor mínimo e máximo da resposta para as consultas, resultando em uma complexidade de tempo ( O(q^2 \log V) ), extremamente ineficiente. Após muita reflexão, posso pensar em um truque clássico: definir ( f_i ) como a resposta final após algumas operações com limite superior ( i ). Assim, basta manter esse gráfico de linha quebrada. Com apenas modificações pontuais, manter esse gráfico exige ( O(q \log q) ) tempo, permitindo obter a pontuação parcial, embora seja complicado de implementar. Lembre-se desse tipo de problema onde se mantém uma função de resposta.
C: Desonra de Cenouras
É relativamente simples; durante a competição, fiquei indeciso em pontos desnecessários. Ao varrer a sequência de operações de trás para frente, sempre que encontrarmos a primeira operação que ainda não apareceu, a atribuímos à última linha. Finalmente, podemos determinar o estado da última linha. O objetivo final é distribuir a sequência de operações entre n linhas, de modo que o estado de cada linha seja igual ao da última linha. Uma propriedade crucial é que o sufixo crescente no final de uma linha não precisa necessariamente de operações. Com isso claro, varremos novamente de trás para frente, atribuindo cada operação à linha correspondente. Se, no final, todas as linhas puderem completar as operações necessárias, então a configuração é válida.
2025.2.17 Noite
A: Reerguer a Bandeira
Não pretendo desabafar, apenas acho que incluir em competições de programação problemas que exigem alta intensidade de raciocínio, algoritmos avançados, muitos casos extremos, dados vinculados a subtarefas e com pacotes contendo vários casos de canto é um pouco excessivo? Durante a competição, a ideia era começar a codificar, mas no final obviamente falhei. O problema é adicionar um valor a uma aresta na árvore para maximizar o MDC de todos os números. Pela propriedade de subtração do MDC, é natural pensar na diferença na árvore. Para evitar muitas discussões, adicionamos uma raiz virtual com valor 0 e depois fazemos a diferença. A operação consiste em escolher um par de pontos com relação ancestral-descendente para adicionar ( k ) ao inferior e subtrair ( k ) do superior; ou escolher um par de pontos ( u, v ), seu ancestral comum mais próximo ( l ) e o pai do ancestral comum ( fa_l ), adicionando ( k ) a ( u, v ) enquanto subtraímos ( k ) de ( l, fa_l ). A resposta final é o MDC de n números, então um fator primo ( p ) da resposta final deve ser divisor de pelo menos ( n-4 ) pontos antes da operação de adição, pois podemos modificar no máximo quatro pontos. Para encontrar os fatores primos que são divisores de pelo menos ( n-4 ) pontos, podemos decompor em fatores primos quaisquer 5 números não-zero, garantindo que todos os fatores primos candidatos sejam considerados. A partir desse ângulo, para cada primo ( p ), consideramos a contribuição de ( p_k ) para a resposta. Seja ( b ) o array após a diferença. Se ( p^k ) divide todos os ( b_i ), certamente contribui para a resposta. Se ( p^k ) divide ( n-2 ) dos ( b_i ), identificamos os dois ( b ) não divisíveis, digamos ( u, v ). Se ( \text{lca}(u,v) \in {u,v} ) e ( b_u \equiv -b_v \pmod{p^k} ), então podemos contribuir com a adição na aresta, exigindo ( b_u + k \equiv 0 \pmod{p^k} ). Se ( p^k ) divide ( n-4 ) dos ( b_i ), encontramos os quatro pontos não divisíveis ( q_1, q_2, q_3, q_4 ), ordenados por profundidade crescente. Se ( fa_{q_2} = q_1 ) e ( \text{lca}(q_3, q_4) = q_2 ) e ( b_{q_3} \equiv b_{q_4}, b_{q_1} \equiv b_{q_2}, b_{q_3} \equiv -b_{q_2} \pmod{p^k} ), então podemos contribuir com a adição na aresta, exigindo ( b_{q_3} + k \equiv 0 \pmod{p^k} ). As restrições sobre ( k ) podem ser armazenadas em um unordered_map. Finalmente, para cada par de pontos ( (u, v) ), usamos o Teorema Chinês do Resto para combinar o ( k ) final. Ainda não terminamos: o ( k ) adicionado deve ser divisor da resposta obtida no primeiro cenário, e os módulos podem não ser coprimos, então precisamos usar o Teorema Chinês do Resto Estendido. Além disso, se a sequência original tiver muitos números repetidos, a diferença na árvore pode não encontrar 5 números não-zero; a verificação especial aqui é um pouco tediosa, conforme o código abaixo.
Clique para ver o código``` #include <bits/stdc++.h> #define fr first #define se second #define Un unsigned #define LL long long #define pb push_back #define pii pair<int,int> #define pLi pair<LL,int> #define pLL pair<LL,LL> #define __ __int128 #define LD long double #define VE vector<LL> #define DB double #define Ve vector
using namespace std;
inline LL read() { LL x = 0,f = 1;char ch = getchar(); while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar(); while(isdigit(ch)) x = x10+ch-48,ch = getchar(); return xf; }
LL qp(LL x,int y) { LL res = 1; while (y) { if (y&1) res = resx; x = xx,y >>= 1; } return res; }
const int N = 5e5+5; struct edge{int to,pre;}e[N<<1]; int las[N],cnt,siz[N],fa[N],hs[N],dep[N],top[N],ct,t[100][70],tmp[5]; LL a[N],b[N],c[100]; struct node{LL p,a,w;}; unordered_map < int,node > mul[N];
void add(int u,int v){e[++cnt] = {v,las[u]},las[u] = cnt;}
void D1(int x) { dep[x] = dep[fa[x]]+1,siz[x] = 1,b[x] = a[x]; for (int i = las[x],y;i;i = e[i].pre) { if ((y = e[i].to) != fa[x]) { fa[y] = x,D1(y),siz[x] += siz[y],b[x] -= a[y]; if (siz[y] > siz[hs[x]]) hs[x] = y; } } }
void D2(int x,int t) { top[x] = t; if (hs[x]) D2(hs[x],t); for (int i = las[x],y;i;i = e[i].pre) if ((y = e[i].to) != fa[x] && y != hs[x]) D2(y,y); }
int LCA(int x,int y) { while (top[x] != top[y]) dep[top[x]] < dep[top[y]] ? y = fa[top[y]] : x = fa[top[x]]; return dep[x] < dep[y] ? x : y; }
void exgcd(LL a,LL b,LL &x,LL &y) { if (!b) return (void)(x = 1,y = 0); exgcd(b,a%b,y,x),y -= a/b*x; }
const LL INF = 1e18;
int main() { int n = read(),id = read(); for (int i = 1;i <= n;i++) a[i] = read(); for (int i = 1,u,v;i < n;i++) u = read(),v = read(),add(u,v),add(v,u); n++,add(n,1),D1(n),D2(n,n); int zer = 0,T = 5; for (int i = 1;i <= n && T;i++) { if (!b[i]) continue; LL k = abs(b[i]);T--; for (LL j = 2;jj <= k;j++) { if (k%j == 0) { c[++ct] = j; while (k%j == 0) k /= j; } } if (k > 1) c[++ct] = k; } sort(c+1,c+ct+1),ct = unique(c+1,c+ct+1)-c-1; for (int i = 1;i <= n;i++) { if (b[i]) { for (int j = 1;j <= ct;j++) { if (b[i]%c[j] == 0) { LL p = 0,k = b[i]; while (k%c[j] == 0) k /= c[j],t[j][++p]++; } } } else zer++; } LL nans = 0,uu,vv,ww; if (zer == n || zer == n-2 || zer == n-4) { if (zer == n) return printf("%lld\n1 1 %lld\n",INF,INF),0; int p = 0; for (int i = 1;i <= n;i++) if (b[i]) tmp[++p] = i; sort(tmp+1,tmp+p+1,[](int x,int y){return dep[x] < dep[y];}); if (p == 2 && LCA(tmp[1],tmp[2]) == tmp[1] && b[tmp[1]]+b[tmp[2]] == 0) { int f = tmp[2]; while (fa[f] != tmp[1]) f = fa[f]; return printf("%lld\n%d %d %lld",b[tmp[2]]+INF,f,tmp[2],INF),0; } if (p == 4 && tmp[1] == fa[tmp[2]] && LCA(tmp[3],tmp[4]) == tmp[2]) { if (b[tmp[3]] == b[tmp[4]] && b[tmp[1]] == b[tmp[2]] && b[tmp[3]]+b[tmp[2]] == 0) return printf("%lld\n%d %d %lld",b[tmp[3]]+INF,tmp[3],tmp[4],INF),0; LL k = __gcd(abs(b[tmp[3]]-b[tmp[4]]),abs(b[tmp[1]]+b[tmp[3]])); nans = k,uu = tmp[3],vv = tmp[4],ww = (k-b[tmp[3]]%k)%k; } } LL ans = 1; for (int i = 1;i <= ct;i++) { int mx = 0; for (int j = 1;t[i][j] && t[i][j]+zer >= n-4;j++) { if (t[i][j]+zer == n) mx = j; else { LL val = qp(c[i],j),p = 0; if (t[i][j]+zer == n-2 && t[i][j+1]+zer != n-2) { for (int k = 1;k <= n;k++) if (b[k]%val) tmp[++p] = k; sort(tmp+1,tmp+p+1,[](int x,int y){return dep[x] < dep[y];}); if (LCA(tmp[1],tmp[2]) == tmp[1] && (b[tmp[1]]+b[tmp[2]])%val == 0) { LL k = (b[tmp[1]]%val+val)%val,w = qp(c[i],j-mx); int f = tmp[2]; while (fa[f] != tmp[1]) f = fa[f]; if (!mul[f].count(tmp[2])) mul[f][tmp[2]] = {val,k,w}; else { auto [p1,a1,w1] = mul[f][tmp[2]]; LL k1,k2,l = valp1;exgcd(val,p1,k1,k2); LL res = ((()valk1%la1%l+()p1k2%lk%l)%l+l)%l; mul[f][tmp[2]] = {l,res,w1w}; } } } else if (t[i][j]+zer == n-4 && t[i][j+1]+zer != n-4) { for (int k = 1;k <= n;k++) if (b[k]%val) tmp[++p] = k; sort(tmp+1,tmp+p+1,[](int x,int y){return dep[x] < dep[y];}); if (tmp[1] == fa[tmp[2]] && LCA(tmp[3],tmp[4]) == tmp[2] && (b[tmp[3]]%val+val)%val == (b[tmp[4]]%val+val)%val && (b[tmp[1]]%val+val)%val == (b[tmp[2]]%val+val)%val && (b[tmp[3]]+b[tmp[2]])%val == 0) { LL k = (b[tmp[1]]%val+val)%val,w = qp(c[i],j-mx); if (!mul[tmp[3]].count(tmp[4])) mul[tmp[3]][tmp[4]] = {val,k,w}; else { auto [p1,a1,w1] = mul[tmp[3]][tmp[4]]; LL k1,k2,l = valp1;exgcd(val,p1,k1,k2); LL res = ((()valk1%la1%l+()p1k2%lk%l)%l+l)%l; mul[tmp[3]][tmp[4]] = {l,res,w1w}; } } } } } ans = qp(c[i],mx); } LL mx = 0,val;pii Ans; for (int u = 1;u <= n;u++) { for (auto [v,q] : mul[u]) { auto [p,a,w] = q; if (w > mx) { LL k1,k2;exgcd(p,ans,k1,k2); LL d = __gcd(p,ans); k1 = (k1(-a/d))%(ans/d); if (k1 < 0) k1 += ans/d; LL m = p/gcd(p,ans)*ans; a = ()(pk1+a)%m; if (a < 0) a += m; mx = w,Ans = {u,v},val = a; } } } if (nans > ans) return printf("%lld\n%lld %lld %lld",nans,uu,vv,ww),0; if (!mx) printf("%lld\n1 1 0",ans); else printf("%lld\n%d %d %lld\n",ans*mx,Ans.fr,Ans.se,val); return 0; }
2025.2.18
---------
#### A: Bispo
Construção simples; não complique demais; a resposta sempre segue o formato abaixo:
#### B: Marca Preguiçosa
Uma operação de atribuição pode ser vista como multiplicar por 0 primeiro e depois adicionar x. Portanto, temos apenas operações de multiplicação e adição. O problema exige manter a expectativa da soma do intervalo e a expectativa do quadrado de um ponto. Para um nó da árvore de segmentos, mantemos \( add, mul, sum, sum^2, add^2, mul^2, muladd \), representando a expectativa da marca de adição, a expectativa da marca de multiplicação, a expectativa da soma do intervalo, a expectativa do quadrado da soma, a expectativa do quadrado da marca de adição, a expectativa do quadrado da marca de multiplicação e a expectativa do produto da marca de multiplicação pela marca de adição, respectivamente, para manter a resposta. Embora eu não entenda expectativa, acho este problema extremamente chato.
\[\begin{aligned} sum_{del} &\gets ml\cdot sum + ad \cdot siz\\ sum^2_{del} &\gets (ml \cdot sum + ad \cdot (r-l+1))^2 \\ &= ml^2 \cdot sum^2 + 2mlad \cdot siz \cdot sum + ad^2\cdot siz^2 \\ add_{del} &\gets ml \cdot add + ad \\ add^2_{del} &\gets (ml \cdot add + ad)^2 \\ &= ml^2 \cdot add^2 + 2mlad \cdot add + ad^2 \\ mul_{del} &\gets ml \cdot mul \\ mul^2_{del} &\gets (ml \cdot mul)^2 \\ &= ml^2 \cdot mul^2 \\ muladd_{del} &\gets ml \cdot mul(ml \cdot add + ad) \\ &= ml^2 \cdot muladd + mlad \cdot mul \end{aligned} \]
2025.2.19
---------
#### B: Árvore Geradora
Para uma árvore geradora de grafo completo, pense no algoritmo de Boruvka. Para encontrar o ponto mais próximo em componentes conexas diferentes, podemos usar a decomposição por centro de gravidade. Especificamente, no processo de decomposição por centro de gravidade, extraímos as distâncias dos pontos na subárvore atual até o centro de gravidade atual, ordenando-as. Então, torna-se encontrar para cada número o menor número maior ou igual a ele que esteja em uma subárvore diferente e em uma componente conexa diferente. Isso é um problema de restrição de dupla cor. Se os pontos na mesma subárvore forem colocados em segmentos contíguos na sequência, restará apenas uma restrição. Podemos manter o mínimo do intervalo e o segundo mínimo, garantindo que as cores do mínimo e do segundo mínimo sejam diferentes para resolver o problema, com complexidade de tempo \( O(n\log^3n) \).
2025.2.20
---------
#### A: Pequeno X e o Retângulo
Um retângulo é válido se e somente se cada ponto tenha grau de entrada igual a 1. Em seguida, basta verificar se o grau de entrada de cada ponto é 1. Subsequências válidas contendo apenas RL são fáceis de encontrar. Abaixo, discutiremos apenas como encontrar subsequências válidas contendo simultaneamente RLUD. Enumere o início da subsequência válida, encontre o primeiro caractere após o início do ciclo RL. Se for U ou L, já não há solução. Abaixo, discutimos os casos R e D. Primeiro, para cada posição, encontre a posição do primeiro U a partir dela, denotada por \( nxt_i \). Se for R, encontre o primeiro U após ele; então a entrada deste R é fornecida por este U, como mostrado abaixo:
RLRLRLRLR???? ????????U
É fácil perceber que se U aparecer em um ? mais à frente, certamente não é válido. Neste ponto, a posição de U é encontrada e a largura do nosso retângulo é determinada como \( nxt_j-i-(j-i)=nxt_j-i \). Se for D, encontre o primeiro U após ele da mesma forma:
RLRLRLDLLL???? ??????RRRU
Semelhante ao caso anterior, a largura do retângulo é \( nxt_j-i-(j+i-sum_{j+1})=nxt_j-(j+sum_{j+1}) \). Após calcular a largura, registramos o início atual, a largura do retângulo e o valor do início módulo a largura do retângulo. Retângulos com a mesma largura e mesmo valor do início módulo a largura podem ser processados juntos. Em seguida, verificar a validade pode ser feito usando hashing de strings. Tomando a linha intermediária como exemplo, verificamos se a D da linha de cima mais a U da linha de baixo mais a L e R da linha atual são iguais ao hash de uma sequência toda de uns.
#### C: Pequeno X e os Paus
Durante a competição, vi que o módulo era 998244353 e parecia uma forma de convolução, então comecei a expandir a fórmula e convoluir. Uma lição é não usar sua experiência para julgar afirmativamente um problema, caso contrário, pode-se passar toda a competição com uma ideia errada. Devido às modificações em \( a_i \), é natural pensar em calcular \( f_i \), que representa a frequência esperada de paus de comprimento \( i \). \( f_i = 2 \times \sum_{j>i} \frac{f_j i(j-i-1)}{\binom{j}{3}} \), e a resposta final é \( \sum_{i>m} a_i f_i \). Uma ideia nada natural é usar matrizes para manter \( f_i \), dividindo \( f_i \) em \( \sum_{j>i} \frac{f_j 2i(j-1)}{\binom{j}{3}} - \sum_{j>i} \frac{f_j 2i^2}{{\binom{j}{3}}} \). Assim, podemos manter \( \sum \frac{f_i(i-1)}{\binom{i}{3}} \) e \( \sum \frac{f_i}{\binom{i}{3}} \) através de multiplicação de matrizes. Sinto que a ideia é semelhante a DP dinâmico; para manter com modificações, usamos matrizes para manter algumas coisas e atualizar rapidamente. Esse truque não é muito comum e é bastante avançado.
2025.2.11
---------
#### A: A Multiplicação de Xiao Kai
Se a sequência for ordenada, podemos resolver por divisão e conquista. Seja o intervalo atual \( [l, r] \), e os intervalos esquerdo e direito \( L = [l, mid] \), \( R = [mid+1, r] \). Seja \( sum_{l,r} = \sum_{i=l}^r a_i \). Classifiquemos as discussões:
Se os três valores estiverem em \( L \) ou \( R \), a resposta é \( ans_L \) ou \( ans_R \).
Se o valor do meio estiver em \( L \) e o valor máximo em \( R \), a contribuição é \( \sum_{x=l}^{mid} \sum_{y=mid+1}^r a_x a_y sum_{l,x-1} 2^{y-x-1} = \left( \sum_{x=l}^{mid} a_x sum_{l,x-1} 2^{mid-x} \right) \left( \sum_{y=mid+1}^r a_y 2^{y-mid-1} \right) = f_L g_R \).
Se o valor mínimo estiver em \( L \) e o valor do meio em \( R \), a contribuição é \( \sum_{x=mid+1}^r \sum_{y=x}^r a_x a_y sum_{l,mid} 2^{\max(y-x-1,0)} = s_L h_R \).
Então, em cada nível da divisão e conquista, calculamos os \( f, g, s, h \) correspondentes para processar cada consulta em \( O(n \log n) \), mas precisamos ordenar cada vez. Para otimizar, primeiro operamos no intervalo de valores para evitar a ordenação, discretizando primeiro. Calcular \( f, g, s, h \) em cada nível da divisão e conquista consome muito tempo, e a estrutura da divisão e conquista é semelhante à nossa árvore de segmentos. Então, podemos usar uma árvore de segmentos de intervalo de valores para combinar rapidamente os intervalos esquerdo e direito e manter \( f, g, s, h \). A resposta é sim; a implementação específica é um pouco complicada e requer alguns arrays auxiliares.
Clique para ver o código```
#include <bits/stdc++.h>
#define fr first
#define se second
#define Un unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define LD long double
#define VE vector<LL>
#define DB double
#define Ve vector<int>
using namespace std;
inline int read()
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
return x*f;
}
const int N = 3e4,P = 998244353;
int a[N],bl[N],pw[N],cnt,b[N],Ans[N<<2];
struct Que{int l,r,id;}que[N<<2];
bool cmp(Que x,Que y){return bl[x.l] == bl[y.l] ? (bl[x.l]&1) ? x.r < y.r : x.r > y.r : x.l < y.l;}
LL qp(LL x,int y)
{
LL res = 1;
while (y)
{
if (y&1) res = res*x%P;
x = x*x%P,y >>= 1;
}
return res;
}
int sum[N<<2],ct[N<<2],ans[N<<2],f[N<<2],g[N<<2],h[N<<2],s[N<<2];
LL inv2 = qp(2,P-2);
void pushup(int i)
{
ct[i] = ct[i<<1]+ct[i<<1|1];
sum[i] = (sum[i<<1]+sum[i<<1|1])%P;
f[i] = (1LL*f[i<<1]*pw[ct[i<<1|1]]+1LL*s[i<<1|1]*sum[i<<1]+f[i<<1|1])%P;
g[i] = (g[i<<1]+1LL*g[i<<1|1]*pw[ct[i<<1]])%P,
s[i] = (1LL*s[i<<1]*pw[ct[i<<1|1]]+s[i<<1|1])%P;
h[i] = (h[i<<1]+h[i<<1|1]+1LL*s[i<<1]*g[i<<1|1])%P;
ans[i] = (ans[i<<1]+ans[i<<1|1]+1LL*f[i<<1]*g[i<<1|1]+1LL*sum[i<<1]*h[i<<1|1])%P;
}
void M1(int l,int r,int p,int i)
{
if (l == r)
{
h[i] = (h[i]+1LL*g[i]*b[l]+1LL*b[l]*b[l])%P;
f[i] = (2LL*f[i]+1LL*sum[i]*b[l])%P;
g[i] = (g[i]+1LL*b[l]*pw[ct[i]])%P;
s[i] = (2LL*s[i]+b[l])%P;
sum[i] = (sum[i]+b[l])%P,ct[i]++;
ans[i] = 1LL*(P+pw[ct[i]]-1-ct[i])*b[l]%P*b[l]%P*b[l]%P;
return ;
}
int mid = (l+r)>>1;
if (p <= mid) M1(l,mid,p,i<<1);
else M1(mid+1,r,p,i<<1|1);
pushup(i);
}
void M2(int l,int r,int p,int i)
{
if (l == r)
{
ct[i]--,sum[i] = (P+sum[i]-b[l])%P;
s[i] = 1LL*(P+s[i]-b[l])*inv2%P;
g[i] = ((g[i]-1LL*b[l]*pw[ct[i]])%P+P)%P;
f[i] = ((f[i]-1LL*sum[i]*b[l])%P*inv2%P+P)%P;
h[i] = ((h[i]-1LL*g[i]*b[l]-1LL*b[l]*b[l])%P+P)%P;
ans[i] = 1LL*(P+pw[ct[i]]-1-ct[i])*b[l]%P*b[l]%P*b[l]%P;
return ;
}
int mid = (l+r)>>1;
if (p <= mid) M2(l,mid,p,i<<1);
else M2(mid+1,r,p,i<<1|1);
pushup(i);
}
int main()
{
int n = read(),q = read(),B = n/sqrt(q)+1;
pw[0] = 1;for (int i = 1;i <= n;i++) pw[i] = (pw[i-1]*2)%P;
for (int i = 1;i <= n;i++) a[i] = read(),b[++cnt] = a[i],bl[i] = (i-1)/B+1;
sort(b+1,b+cnt+1),cnt = unique(b+1,b+cnt+1)-b-1;
for (int i = 1;i <= n;i++) a[i] = lower_bound(b+1,b+cnt+1,a[i])-b;
for (int i = 1;i <= q;i++) que[i] = {read(),read(),i};
sort(que+1,que+q+1,cmp);
int l = 1,r = 0;
for (int i = 1;i <= q;i++)
{
while (r < que[i].r) M1(1,cnt,a[++r],1);
while (r > que[i].r) M2(1,cnt,a[r--],1);
while (l < que[i].l) M2(1,cnt,a[l++],1);
while (l > que[i].l) M1(1,cnt,a[--l],1);
Ans[que[i].id] = ans[1];
}
for (int i = 1;i <= q;i++) printf("%d\n",Ans[i]);
return 0;
}
B: O Humor dos Pombos
Registrei a ideia durante a competição. ( d[i][S] ) é o número de arestas do ponto ( i ) para o conjunto ( S ). ( a[i][S] ) é o número de esquemas nos quais ( S ) forma uma cadeia com ponto final ( i ) (por padrão, o outro ponto final é o ponto com o menor número em ( S )). ( b[i][S] ) é a soma dos pesos das arestas de todos os esquemas nos quais ( S ) forma uma cadeia com ponto final ( i ). ( f[S] ) representa a soma dos pesos das arestas de todos os esquemas nos quais ( S ) é conectado e tem exatamente um ciclo simples. ( g[S] ) representa o número de esquemas nos quais ( S ) é conectado e tem exatamente um ciclo simples. ( h[S] ) representa o número de esquemas nos quais ( S ) é conectado arbitrariamente sem formar ciclos. ( s[S] ) representa o número de esquemas de árvore geradora de ( S ). A partir de ( a[i][S] ) e ( b[i][S] ), podemos calcular a soma dos pesos das arestas e o número de esquemas com exatamente um ciclo; este é o ciclo da nossa árvore de base. A outra parte, além da árvore de base, é o nosso ( h[S] ). ( h[S] ) pode ser calculado a partir de ( s[S] ) usando convolução de subconjuntos semi-online. Ou seja, em seguida, basta anexar várias árvores ao nosso ciclo para calcular a resposta, mas essa parte ainda não tem uma solução muito boa. A solução correta é considerar a contribuição de cada aresta para a resposta; é difícil de pensar. A fórmula é apresentada abaixo.
[\sum_{S}2^{|E_{\overline S}|}f(S)W(S) - \sum_{S}2^{|E_{\overline S}| - 1}W(S)\sum_{T\subset S} f(T) f(S - T)+\sum_{S}2^{|E_{\overline S}|}W(S)\sum_{T\subset S} f(T)W(T)f(S - T) ] 2025.2.22
A: Empresa
Onde está a dificuldade do problema? É no fluxo de custo que parece óbvio à primeira vista? É no ganancioso com reversão que não consigo pensar de jeito nenhum e considero a solução correta durante a competição? Acho que, ao ver correspondência ponderada de bipartido, nunca se pensou no Teorema de Hull para correspondência máxima. Para problemas de contagem de respostas ou otimização de respostas, primeiro considere a forma da resposta final ou as condições; depois, mantenha e opere sobre a condição de satisfazer essa restrição. Para qualquer intervalo, a soma das vezes de escolha fornecidas pelos segmentos que se cruzam com este intervalo deve ser maior ou igual à soma dos números escolhidos neste intervalo; esta é a condição necessária e suficiente da nossa resposta final. Portanto, devemos ser gananciosos mantendo essa condição necessária e suficiente. O primeiro problema a resolver é calcular rapidamente a soma das vezes de escolha fornecidas pelos segmentos que se cruzam com este intervalo. Usamos inclusão-exclusão simples. Seja ( A_i = \sum_j [l_j \le i] v_j ), ( B_i = \sum_j [r_j < i] v_j ). Para o intervalo ( [l, r] ), usar diretamente ( A_r - B_{l-1} ) é a resposta que desejamos. Como queremos ser gananciosos, certamente escolhemos pessoas por ( b_i ) em ordem decrescente. Se o índice da pessoa escolhida for ( i ), então o limite superior do número de vezes que escolhemos esta pessoa é ( \min(c_i, \min_{r \ge i}(A_r) - \max_{l \le i}(B_l)) ). A restrição desta condição necessária e suficiente é mantida usando uma árvore de segmentos.
B: Robô
Relações binárias, A então B, A então não B, B então A, B então não A, há solução? 2-SAT. Observando a monotonicidade, ordenamos as arestas e usamos dois ponteiros ( O(n^2) ) para enumerar os valores máximos dos dois lados e usamos 2-SAT para determinar, com complexidade de tempo ( O(n^4) ). O passo anterior é simples e é o que deve ser feito. Uma propriedade é que se uma aresta adicionada formar um ciclo par, as restrições adicionadas por esta aresta já foram restritas anteriormente; pulamos diretamente. Para um ciclo ímpar, é claro que não há solução. Sabendo dessa propriedade crucial, apenas ( O(n) ) arestas úteis permanecem. Cada uma é realizada uma vez com busca binária, com complexidade de tempo total ( Tn^3 \log n ). Para otimizar isso, é necessário uma conclusão: o número de prefixos máximos/mínimos em uma permutação aleatória de comprimento ( n ) é da ordem ( O(\log n) ). Portanto, as ( O(n) ) arestas úteis são extraídas, embaralhadas (shuffle) e então calculamos a resposta. Se não for possível atualizar a resposta, pulamos diretamente; a complexidade de tempo esperada é ( O(Tn^3) ).