\(\cal T_1\) 草莓蛋糕 / cake
Description
題目背景
題目描述
在一起將 \(\rm a\) 城的蛋糕店都吃過一遍后，你和唐芯都各自選出了自己最心儀的蛋糕店 —— "蘭璱辰" 店與 "澄璱辰" 店，下簡記為 \(\rm L\) 店與 \(\rm C\) 店。作為甜品的狂熱愛好者，唐芯每周都會去 \(\rm C\) 店買她心愛的草莓蛋糕來吃，不過，"兩個總比一個好"，所以她總是幫你去 \(\rm L\) 店也買一份，再 "順便幫你吃一點兒"。
對于每個草莓蛋糕都有兩個值 \(c,y\)，分別代表蛋糕的卡路里和美味度，奇怪的是，美味度越小代表蛋糕越美味。同時，兩家蛋糕店里賣的草莓蛋糕可以分別被表示成 多重集 \(L,C\).
蛋糕店里賣的草莓蛋糕不會是一成不變的。具體地，在唐芯相鄰兩次買蛋糕的時間間隔中，\(\rm L\) 店與 \(\rm C\) 店中會有一家店進行一個草莓蛋糕的上新或下架。另外需要強調的是，唐芯購買蛋糕并不會造成多重集 \(L,C\) 的變化。
由于唐芯會 "吃一點兒" 你的那份，所以對于一組買蛋糕方案 \(a\in L,b\in C\)，唐芯會增加的卡路里是 \(a_c+b_c\)，感受到的美味度是 \(a_y+b_y\). 作為一名女演員，唐芯必須控制她的體重，但她同時也不想在享受美食的過程中太委屈自己。也就是說，定義 \(\max\{a_c+b_c,a_y+b_y\}\) 為唐芯對一組買蛋糕方案的不喜愛度，她希望能找到一組買蛋糕方案，使得其不喜愛度最小。
由于唐芯馬上要趕去《鮫人淚》劇組進行拍攝，所以她將接下來 \(Q\) 周的買蛋糕任務交給了你。為了方便起見，你只需要告訴她每周的最小不喜愛度即可。
\(Q\leqslant 10^6,1\leqslant c,y\leqslant 10^9\).
Solution
一些閑話 & 免責聲明：
我真的 沒想過卡常，真的 沒想過卡常，真的 沒想過卡常 ???！
先開始設置成 \(\text{3 s}\) 確實不太合理（雖然也不是我設的（進行推鍋，后來改成 \(\text{4 s}\)，想著賽后重測應該都可以 A（真的是標程的兩倍啊），沒有想到還是有人沒有過 qwq（不過同隊的一位不愿透露姓名的同學的 \(\text{1 log}\) 做法沒有跑過 \(\text{2 log}\) 我也只能哈哈哈哈哈哈哈哈哈了）。總之被機房眾 D 了，
因為某種比較奇怪的原因這個 "被 D" 的 debuff 轉移到另一位出題人身上了，感覺挺抱歉的。總之，這里對因為被卡常沒有隨切這道題的同學說句對不起！我謝罪（滑跪）。
\(Q\leqslant 600\)
暴力維護 \(L,C\)，每次詢問進行兩家店蛋糕的兩兩匹配取 \(\min\)，復雜度 \(\mathcal O(Q^3)\).
\(Q\leqslant 5000\)
用兩個 \(\rm multiset\) 維護 \(L,C\)，再開一個 \(\rm multiset\) 維護 \(\max\{a_c+b_c,a_y+b_y\}\)，當上新/下架一個草莓蛋糕時，將這個蛋糕的信息與另一家店的所有蛋糕進行匹配，修改維護 \(\max\) 的 \(\rm multiset\) 的信息即可。復雜度 \(\mathcal O(Q^2\log Q)\).
\(Q\leqslant 10^6\)
題目要求 \(\min_{a\in L,b\in C}\max\{a_c+b_c,a_y+b_y\}\)，這個 \(\max\) 很煩人，把兩個蛋糕綁在一起，所以考慮分類討論去除 \(\max\)：若 \(a_c+b_c\geqslant a_y+b_y\)，也就是 \(a_c-a_y\geqslant b_y-b_c\)，對每個蛋糕記一個判據量 \(h\)，對于 \(a\in L\)，\(h=a_c-a_y\)；對于 \(b\in C\)，\(h=b_y-b_c\). 那么對于 \(a\in L\)，有集合 \(B=\{b_h\leqslant a_h,b\in C\}\)，\(a\) 與集合 \(B\) 中任意元素的最大值都是 \(a_c+b_c\)，顯然選擇集合 \(B\) 中 \(b_c\) 最小值是最優的。同時，如果從固定 \(b\in C\) 的角度來看，我們要選擇對應集合 \(A\) 中 \(a_c\) 的最小值。至此，我們成功地去除了 \(\max\).
考慮用線段樹維護這個過程。發現選哪邊作為最大值就是比較判據量的大小關系，所以開一個值域為 \(h\) 值域的線段樹，每個節點維護判據量在此區間的兩家蛋糕的信息。只需要分別維護兩家蛋糕的 \(\min c,\min y\) 以及最終答案即可。加入與刪除可以通過維護葉子節點的 \(\rm multiset\) 實現。復雜度 \(\mathcal O(Q\log Q)\).
這里更新一個彩蛋：賽時看到 \(\sf{Cirno\_9}\) 的 \(\color{red}{\text{wa 95}'}\) 的時候非常慌張，害怕把標程寫掛了。之后心驚膽戰地 debug 了一會后發現他沒有判等（等下為啥這個沒寫只 wa 了一組啊。
Code
# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template <class T>
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}
# include <set>
# include <iostream>
# include <algorithm>
using namespace std;
const int maxn = 1e6+5;
const int infty = 2e9+9;
int n,val[maxn];
struct Q { int opt,d,c,y; } s[maxn];
struct node {
int v[2][2], ans;
void pushUp() {
if(v[0][0]!=infty && v[1][0]!=infty)
ans = v[0][0]+v[1][0];
else ans = infty;
}
node operator + (const node& t) const {
node r;
for(int i=0;i<2;++i) for(int j=0;j<2;++j)
r.v[i][j] = min(v[i][j],t.v[i][j]);
r.ans = min(ans,t.ans);
if(v[0][1]==infty || t.v[1][1]==infty);
else r.ans = min(r.ans,v[0][1]+t.v[1][1]);
if(t.v[0][0]==infty || v[1][0]==infty);
else r.ans = min(r.ans,t.v[0][0]+v[1][0]);
return r;
}
} t[maxn<<2];
multiset <int> st[maxn][2][2];
void ins(int o,int l,int r,int p,int c,int y,bool d) {
if(l==r) {
st[l][d][0].insert(c),
st[l][d][1].insert(y);
t[o].v[d][0] = min(t[o].v[d][0],c),
t[o].v[d][1] = min(t[o].v[d][1],y);
t[o].pushUp(); return;
} int mid = l+r>>1;
if(p<=mid) ins(o<<1,l,mid,p,c,y,d);
else ins(o<<1|1,mid+1,r,p,c,y,d);
t[o] = t[o<<1]+t[o<<1|1];
}
void del(int o,int l,int r,int p,int c,int y,bool d) {
if(l==r) {
st[l][d][0].erase(st[l][d][0].lower_bound(c)),
st[l][d][1].erase(st[l][d][1].lower_bound(y));
if(st[l][d][0].empty()) t[o].v[d][0] = infty;
else t[o].v[d][0] = *st[l][d][0].begin();
if(st[l][d][1].empty()) t[o].v[d][1] = infty;
else t[o].v[d][1] = *st[l][d][1].begin();
t[o].pushUp(); return;
} int mid = l+r>>1;
if(p<=mid) del(o<<1,l,mid,p,c,y,d);
else del(o<<1|1,mid+1,r,p,c,y,d);
t[o] = t[o<<1]+t[o<<1|1];
}
void build(int o,int l,int r) {
for(int i=0;i<2;++i) for(int j=0;j<2;++j)
t[o].v[i][j] = infty; t[o].ans = infty;
if(l==r) return; int mid = l+r>>1;
build(o<<1,l,mid), build(o<<1|1,mid+1,r);
}
int main() {
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
n = read(9);
for(int i=1;i<=n;++i) {
s[i].opt=read(9), s[i].d=read(9),
s[i].c=read(9), s[i].y=read(9);
val[i] = s[i].d? s[i].y-s[i].c: s[i].c-s[i].y;
}
sort(val+1,val+n+1);
const int rane = unique(val+1,val+n+1)-val-1;
build(1,1,rane);
for(int i=1;i<=n;++i) {
int x = s[i].d? s[i].y-s[i].c: s[i].c-s[i].y;
int h = lower_bound(val+1,val+rane+1,x)-val;
if(s[i].opt) ins(1,1,rane,h,s[i].c,s[i].y,s[i].d);
else del(1,1,rane,h,s[i].c,s[i].y,s[i].d);
print(t[1].ans==infty? -1: t[1].ans,'\n');
}
return 0;
}
\(\cal T_2\) 矩陣補全 / completion
Description
本來今天小 Q 是想讓你補全一個矩陣的，但是他突然發現自己把矩陣剩下部分的信息也搞丟了。具體來講，他的矩陣是一個 \(n\) 行 \(m\) 列的 01 矩陣 \(A\)（下標從 \(0\) 開始），有如下性質：
- 把每一行的值拼起來形成一個二進制數，這個數屬于一個給定的集合 \(S\)，即滿足 \(\displaystyle ?0 \leqslant i < n, S ? \sum^{m?1}_{j=0} a_{ij}2^j\)；
- 對于每一列的性質，我們用兩個長度為 \(m\) 的數組 \(b\) 和 \(c,c_i ∈ [0, 1]\) 來描述。對于每個 \(0 \leqslant i < m\)：
- 若 \(b_i = 0\)，則滿足第 \(i\) 列的每個元素都等于 \(c_i\)；
- 若 \(b_i = 1\)，則滿足第 \(i\) 列的所有元素的按位或和等于 \(c_i\)；
- 若 \(b_i = 2\)，則滿足第 \(i\) 列的所有元素的按位與和等于 \(c_i\)；
- 若 \(b_i = 3\)，則滿足第 \(i\) 列的所有元素的按位異或和等于 \(c_i\).
不幸的是，小 Q 把數組 \(c\) 也給搞忘了，只記得 \(S\) 和 \(b\)，所以你需要幫助他回憶起數組 \(c\).
具體而言，他會向你詢問 \(Q\) 次，每次給出一個可能的 \(c\)，你需要回答滿足條件的矩陣的個數。
\(n\leqslant 10^9,m\leqslant 20\).
Solution
不妨先考慮 \(b_i=1\) 的情況，那么把每一行的元素看成一個數字，實際上就是對一個全為 \(1\) 的數組 \(P\) 進行 \(n\) 次或卷積得到 \(P'\)，每次詢問 \(c\) 就是 \(P'_c\)。這個可以用 \(\tt FWT\) + 快速冪加速到 \(\mathcal O((m+\log n)\cdot 2^m)\).
先拋出正解的寫法：在 \(\tt FWT\) 途中考慮每個 \(2\) 的冪，對應的 \(b\) 是什么就做什么 \(\tt FWT\)（\(b=0\) 時什么也不干）。為啥這是對的？考慮 \(\tt FWT\) 的過程實際上就是不斷將二進制位拆分的迭代，所謂遞推也是 模擬 此運算在這一位上如何運算，所以它本身就是可以被拆分的。
Code
# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template <class T>
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp] = x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}
const int MAXN = 1<<20;
const int mod = 1e9+7, iv = (mod+1>>1);
int qkpow(int x,int y,int r=1) {
for(; y; y>>=1, x=1ll*x*x%mod)
if(y&1) r=1ll*r*x%mod; return r;
}
int adj(int x) { return (x+mod)%mod; }
char str[MAXN];
int n, m, lim, f[MAXN], b[30];
void fwt(int* f,int opt=1) {
for(int w=0, l=2; w<m; ++w, l<<=1) if(b[w]) {
if(b[w]==1) {
for(int o=0, p=l>>1; o<lim; o+=l)
for(int i=o; i<o+p; ++i)
f[i+p] = (f[i+p]+f[i]*opt)%mod;
} else if(b[w]==2) {
for(int o=0, p=l>>1; o<lim; o+=l)
for(int i=o; i<o+p; ++i)
f[i] = (f[i]+f[i+p]*opt)%mod;
} else {
for(int o=0, p=l>>1; o<lim; o+=l)
for(int i=o; i<o+p; ++i) {
const int x=f[i], y=f[i+p];
f[i] = (x+y)%mod, f[i+p] = (x-y)%mod;
if(opt==-1) f[i] = 1ll*f[i]*iv%mod,
f[i+p] = 1ll*f[i+p]*iv%mod;
}
}
}
}
int main() {
freopen("completion.in","r",stdin);
freopen("completion.out","w",stdout);
n=read(9), m=read(9), scanf("%s",str); lim=1<<m;
for(int i=0;i<lim;++i) f[i] = str[i]-'0';
for(int i=0;i<m;++i) b[i]=read(9);
fwt(f); for(int i=0;i<lim;++i) f[i]=qkpow(f[i],n);
fwt(f,-1); for(int i=0;i<lim;++i) f[i] = adj(f[i]);
for(int Q=read(9); Q; --Q) print(f[read(9)],'\n');
return 0;
}
\(\cal T_3\) 萬靈藥 / elixir
Description
給定只包含 \(\text{a,b,c,d}\) 的長度為 \(n\) 的字符串 \(S\)，進行 \(Q\) 次操作 \((x,y)\)：
- 在集合中插入前綴 \(x,y\) 的 最長公共后綴（注意 \(x,y\) 可以相同），若集合已經存在相同的 字符串（注意不是相同 \(x,y\)），則在集合中刪除這個字符串；
- 定義一個集合的 親和指數 為集合中 所有字符串兩兩最長公共前綴 的長度之和，請輸出當前集合的親和指數。
\(n,Q\leqslant 5\cdot 10^5\).
Solution
首先建出 \(\rm sam\)，那么任意兩個前綴的最長公共后綴就是它們在 \(\text{parent tree}\) 上 \(\rm lca\) 的最長串。由于 \(\rm sam\) 點數級別是 \(\mathcal O(n)\) 的，所以實際上集合大小級別也是 \(\mathcal O(n)\) 的。
考慮用 \(\rm trie\) 樹維護這個集合，粗略來看插入復雜度是 \(\mathcal O(n^2)\) 的，然后就可以轉化為求 \(\rm trie\) 樹上兩兩關鍵節點的 \(\rm lca\) 的深度之和，這個問題有一個較為經典的解決方案 —— 插入點 \(u\) 時，查詢 \(u\) 到根的權值和，就是此次操作親和指數的增加量，然后將 \(u\) 到根路徑上每個點都加一，刪除同理，復雜度是兩只 \(\log\) 的。或者也可以用全局平衡二叉樹做到一只 \(\log\).
事實上，\(\rm trie\) 樹可以做到 \(\mathcal O(n)\) 建樹。考慮每個在 \(\text{parent tree}\) 上的節點 \(v\)，一定存在一個節點 \(u\) 可以通過在后面加一個字符轉移到 \(v\)，且 \(u\) 內最長字符串為 \(v\) 去掉最后一個字符的字符串。\(u,v\) 的關系就和 \(\rm trie\) 樹的父子關系非常類似了，這樣建樹即可做到 \(\mathcal O(n)\).
再提一嘴那個 \(\mathcal O(n^2)\) 的建樹方法，實際上是對 \(\rm sam\) 上每個節點都維護 \(\text{R}\) 表示在原串上的右端點。葉子節點的 \(\rm R\) 是已知的，可以直接上傳到 \(\text{parent tree}\) 上的父親。事實上這個暴力比正解難寫。
Code
雖然寫的是樹剖，但還是跑得挺快的，至少交上去和全局平衡二叉樹差不多來著。
# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template <class T>
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp] = x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}
# include <vector>
# include <cstring>
# include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 5e5+5;
const int MAXN = maxn<<1;
char str[maxn];
bool vis[MAXN];
int n, all, Ref[maxn];
namespace fwt {
ll c1[MAXN], c2[MAXN];
int lowbit(int x) { return x&-x; }
void add(int l,int r,int k) {
for(const int coe=(l-1)*k; l<=all; l+=lowbit(l))
c1[l] += k, c2[l] += coe; ++ r;
for(const int coe=(r-1)*(-k); r<=all; r+=lowbit(r))
c1[r] -= k, c2[r] += coe;
}
ll ask(int l,int r,ll ret=0) {
for(const int coe=r; r; r-=lowbit(r))
ret += c1[r]*coe-c2[r]; -- l;
for(const int coe=l; l; l-=lowbit(l))
ret -= c1[l]*coe-c2[l]; return ret;
}
}
struct HLD {
vector <int> e[MAXN];
int dep[MAXN], son[MAXN], sz[MAXN];
int Dfn, tp[MAXN], f[MAXN], dfn[MAXN];
void dfs1(int u) {
sz[u] = 1;
for(const auto& v:e[u]) {
dep[v] = dep[f[v]=u]+1;
dfs1(v), sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u]=v;
}
}
void dfs2(int u,int t) {
tp[u]=t, dfn[u]=++Dfn;
if(son[u]) dfs2(son[u],t);
for(const auto& v:e[u])
if(son[u]!=v) dfs2(v,v);
}
int lca(int x,int y) {
for(; tp[x]^tp[y]; x=f[tp[x]])
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
return dep[x]<dep[y]? x: y;
}
void modify(int x,int k) {
for(; tp[x]^1; x=f[tp[x]])
fwt::add(dfn[tp[x]],dfn[x],k);
fwt::add(2,dfn[x],k);
}
ll query(int x,ll ret=0) {
for(; tp[x]^1; x=f[tp[x]])
ret += fwt::ask(dfn[tp[x]],dfn[x]);
return ret+fwt::ask(2,dfn[x]);
}
} T, trie;
namespace sam {
int las=1, cnt=1;
struct node { int len,fa,to[4]; } t[MAXN];
void ins(int id) {
int c = str[id]-'a'; Ref[id] = cnt+1;
int cur=++cnt, p=las; t[cur].len=t[las].len+1;
for(; p && !t[p].to[c]; p=t[p].fa) t[p].to[c]=cur;
if(!p) t[cur].fa=1;
else {
int q = t[p].to[c];
if(t[q].len==t[p].len+1) t[cur].fa=q;
else {
int now = ++cnt; t[now]=t[q];
t[now].len = t[p].len+1;
t[cur].fa = t[q].fa = now;
for(; p && t[p].to[c]==q; p=t[p].fa) t[p].to[c]=now;
}
}
las=cur;
}
void consTree() {
for(int i=2;i<=cnt;++i)
T.e[t[i].fa].emplace_back(i);
for(int i=1;i<=cnt;++i) {
for(int j=0;j<4;++j) {
if(t[i].to[j] && t[t[i].to[j]].len==t[i].len+1)
trie.e[i].emplace_back(t[i].to[j]);
}
}
}
}
void CandyMyWife() {
static long long ans=0;
int x=read(9), y=read(9);
int z = T.lca(Ref[x],Ref[y]);
if(vis[z]) {
trie.modify(z,-1);
ans -= trie.query(z);
} else {
ans += trie.query(z);
trie.modify(z,1);
} vis[z] ^= 1;
print(ans,'\n');
}
int main() {
scanf("%s",str+1), n=strlen(str+1);
for(int i=1;i<=n;++i) sam::ins(i);
sam::consTree();
T.dfs1(1), T.dfs2(1,1), trie.dfs1(1), trie.dfs2(1,1);
all = T.Dfn;
for(int Q=read(9); Q; --Q) CandyMyWife();
return 0;
}
浙公網安備 33010602011771號