CSP-S2023
https://www.luogu.com.cn/contest/140859。
P9753
首先考虑一个串可以被消除时的结构：
- \(\textbf{xx}\) 可以被消除。
- 若 \(\textbf{A}\) 和 \(\textbf{B}\) 均可以被消除，则 \(\textbf{AB}\) 也可以被消除。
- 若 \(\textbf{A}\) 可以被消除，则 \(\textbf{xAx}\) 也可以被消除。
观察到这个东西跟“合法括号序列”的定义很像，所以我们考虑枚举左端点，然后移动右端点，开个栈去膜你，就得到了一个 \(\Theta(n^2)\) 的做法。
进一步的，考虑我们固定左端点为 \(1\)，当右端点移动到 \(k\) 时，当前栈里元素为 \(S\)；当右端点移动到 \(k'\) 时，栈里元素再一次变成 \(S\)。那么说明了什么？也就是说，\([k'+1,k]\) 范围内的字符串被完全消除了。
但其实这样子讲也不是很准确。
比如：字符串为 \(\text{aaa}\)，\(S_3=S_1=\text{a}\)，但是在我们膜你过程中，第 \(2\) 个 \(\text{a}\) 明明是和第 \(1\) 个 \(\text{a}\) 消除了，但是在我们的意思中，他似乎是和第二个 \(\text{a}\) 消除了，这样子不会多记/少记吗？
实际上并不会。感性理解一下，如果说我们加入了几个字符，把原来栈顶的几个元素给消掉了，那么我们要再加入几个字符，使得加入后得到的新栈和原来栈相等，那说明了什么？说明了加入的几个字符和消掉的几个字符是相等的。也就是新加入的所有字符可以互相抵消。
那么我们时时维护一个栈，每加入一个字符后计算一下其哈希值（可以时时维护），然后丢到一个 map 里，并且查一下 map 里有几个跟他相同的。
然后就做完了，复杂度 \(\Theta(n\log{n})\)，如果用 unordered_map 代替 map，理论上可以做到 \(\Theta(n)\)。
点击查看代码
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=3e6+5,m=3e6;
const ull base=1145141;
ull p[N];
char t[N];
void init() {
p[0]=1;
rep(i,1,m)
p[i]=p[i-1]*base;
}
map<ull,int> cnt;
signed main() {
init();
int n;
scanf("%d",&n);
scanf("%s",t+1);
stack<char> s; ++cnt[0];
ull res=0; ll ans=0;
rep(i,1,n) {
if(!s.empty()&&s.top()==t[i])
res-=s.top()*p[s.size()],s.pop();
else
s.push(t[i]),res+=s.top()*p[s.size()];
ans+=cnt[res];
++cnt[res];
}
printf("%lld\n",ans);
return 0;
}
P9755
首先一眼答案具有单调性，然后一眼二分答案，那么就要考虑 check 函数怎么写。
考虑我们现在在判断时刻 \(m\) 是否合法，那么我们对于每个点再去求一个值 \(t_i\) 代表最晚要在第 \(t_i\) 时刻把这个点的树种上。则 \(t_i=\max\limits_{\sum\limits_{j=x}^m \max\{b_i+j\cdot c_i,1\}\ge a_i}{x}\)。
则问题在于如何快速计算 \(f(m)=\sum\limits_{j=1}^m \max\{b_i+j\cdot c_i,1\}\)。
其实这是好做的（小学奥数/yiw），考虑到 \(\sum\limits_{j=1}^m b_i+j\cdot c_i\) 和 \(\sum\limits_{j=1}^m 1\) 都是好求的，那么我们要把那个 \(\max\) 给去掉。
方便起见，设 \(g(x)=\sum\limits_{i=1}^x i=\frac{x(x+1)}{2}\)。
观察到 \(b_i,c_i\) 和 \(1\) 是定值，则 \(y=b_i+c_i\cdot x\) 和 \(y'=1\) 至多只有一个交点：
-
当 \(c_i<0\) 时，若 \(y=y'\)，则 \(x_0=\lfloor\frac{1-b_i}{c_i}\rfloor\)。当 \(x\le x_0\) 时，\(\max\) 取 \(b_i+c_i\cdot x\)，当 \(x> x_0\) 时 \(\max\) 取 \(1\)。得 \(f(m)=g(x_0)\cdot c_i+x_0\cdot b_i+(m-x_0+1)\)。
-
当 \(c_i=0\) 时，\(y=b_i+c_i\cdot x=b_i+0\cdot x=b_i\)。得 \(f(m)=m\cdot b_i\)。
-
当 \(c_i>0\) 时，若 \(y=y'\)，则 \(x_0=\lfloor\frac{1-b_i}{c_i}\rfloor\)。当 \(x\le x_0\) 时，\(\max\) 取 \(1\)，当 \(x> x_0\) 时 \(\max\) 取 \(b_i+c_i\cdot x\)。得 \(f(m)=x_0+(g(m)-g(x_0))\cdot c_i+(m-x_0)\cdot b_i\)。
需要注意的是，笔者在代码实现中 \(x_0\) 是上取整，所以可能与刚才推的柿子略有不同。
此外 \(x_0\) 应当向 \(0\) 取 \(\max\)，向 \(m\) 取 \(\min\)。
由于 \(f(m)\) 具有单调性，则 \(f(m)-f(x)\) 同样具有单调性，对于 \(t_i\) 二分求即可。
得到 \(t_i\) 后，我们贪心地将所有点按 \(t_i\) 排序，然后依次从其一直向根节点种树。邻项交换易证。
但是由于我们每次种树是要将其到根节点全部种上树，而且每个节点不能重复种，相当于路径覆盖全 \(1\)，全局查询当前有几个 \(1\)。如果直接树剖暴力做，复杂度是 \(\Theta(n\log V\log^2 n)\) 的，显然过不去。
但是我们考虑到一个节点只会被种一次，而且如果某个节点已经被种过了，其所有祖先节点必然也被种过，所有我们每次只需要暴力跳父亲，然后打上一个代表已经填过的 tag，遇到如果某个父亲已经被种过就 return，均摊复杂度 \(\Theta(n)\)。
最终复杂度瓶颈在于两个二分和排序，时间复杂度为 \(\Theta(n\log V\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define ll long long
//#define int long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define cl(f,x) memset(f,x,sizeof(f))
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
using namespace std;
const int N=1e5+5;
int head[N],len;
struct node {
int to,nxt;
}; node edge[N<<1];
void add_edge(int u,int v) {
edge[++len]={v,head[u]}; head[u]=len;
}
int f[N];
void dfs(int u,int fa) {
f[u]=fa;
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to;
if(v!=fa)
dfs(v,u);
}
}
__int128 calc(__int128 x) {
return x*(x+1)/2;
}
const __int128 awa=1;
inline __int128 calc(__int128 a,__int128 b,__int128 c) {
__int128 x=max(awa,min(a+1,(__int128)ceil(1.0*(1-b)/c)));
if(c<0)
return (x-1)*b+calc(x-1)*c+(a-x+1);
else if(c==0)
return a*b;
else
return (x-1)+(a-x+1)*b+(calc(a)-calc(x-1))*c;
}
ll a[N],b[N],c[N];
int p[N],t[N],n;
bool used[N];
int update(int u) {
if(used[u])
return 0;
used[u]=true;
if(f[u])
return update(f[u])+1;
return 1;
}
bool check(int x) {
rep(i,1,n) {
used[i]=false;
__int128 val=calc(x,b[i],c[i]);
if(val<a[i])
return false;
int l=1,r=n,ans=-1;
while(l<=r) {
int mid=(l+r)>>1;
if(val-calc(mid-1,b[i],c[i])>=a[i])
ans=mid,l=mid+1;
else
r=mid-1;
}
t[i]=ans;
}
sort(p+1,p+n+1,[](const int &x,const int &y) {
return t[x]<t[y];
});
int res=0;
rep(i,1,n) {
res+=update(p[i]);
if(res>t[p[i]])
return false;
}
return true;
}
ll read() {
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
x=x*10+ch-48,ch=getchar();
return x*f;
}
int main() {
n=read();
rep(i,1,n)
a[i]=read(),b[i]=read(),c[i]=read(),p[i]=i;
rep(i,2,n) {
int u=read(),v=read();
add_edge(u,v);
add_edge(v,u);
}
dfs(1,0);
int l=n,r=1e9,ans=1e9;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid))
r=mid-1,ans=mid;
else
l=mid+1;
}
printf("%d\n",ans);
return 0;
}
CF1884
https://codeforces.com/contest/1884。
CF1884D
典题（？
考虑记 \(f_x=[\nexists k,a_k|x]\)，这个东西可以调和级数 \(\Theta(n\ln{n})\) 去求。
则题目要求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{\gcd(a_i,a_j)}\)，然后就是经典套路：
\[\begin{aligned} & \sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{\gcd(a_i,a_j)} \\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [\gcd(a_i,a_j)=d] \\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [\gcd(\frac{a_i}{d},\frac{a_j}{d})=1][d|a_i][d|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n \varepsilon(\gcd(\frac{a_i}{d},\frac{a_j}{d}))[d|a_i][d|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [d|a_i][d|a_j]\sum\limits_{t|\frac{a_i}{d}\bigwedge t|\frac{a_j}{d}} \mu(t)\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)\sum\limits_{i=1}^n\sum\limits_{j=1}^n [dt|a_i][dt|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)(\sum\limits_{i=1}^n[dt|a_i])^2\\ \end{aligned} \]最后这个 \(\sum\) 也可以 \(\Theta(n\ln{n})\) 去预处理，然后最终整个柿子也可以 \(\Theta(n\ln{n})\) 去算。
注意题目求的 \((i,j)\) 是无序对，所以最终答案要除以 \(2\)。
最终复杂度 \(\Theta(n\ln{n})\)。
点击查看代码
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e6+5,m=1e6;
int f[N],g[N],h[N],a[N];
bool is_prime[N];
int mu[N];
vector<int> prime;
void init() {
is_prime[1]=true; mu[1]=1;
rep(i,2,m) {
if(!is_prime[i])
prime.push_back(i),mu[i]=-1;
for(auto x:prime) {
if(x*i>m)
break;
is_prime[x*i]=true;
if(i%x==0)
continue;
mu[i*x]=-mu[i];
}
}
}
signed main() {
init();
int T;
scanf("%d",&T);
while(T--) {
int n;
scanf("%d",&n);
rep(i,1,n)
f[i]=g[i]=h[i]=0;
rep(i,1,n) {
scanf("%d",&a[i]);
++h[a[i]];
if(!f[a[i]]) {
rep(j,1,n/a[i])
f[j*a[i]]=1;
}
}
rep(i,1,n) {
rep(j,1,n/i)
g[i]+=h[i*j];
}
ll ans=0;
rep(i,1,n) {
if(f[i])
continue;
rep(j,1,n/i)
ans+=1ll*mu[j]*g[i*j]*g[i*j];
}
printf("%lld\n",ans/2);
}
return 0;
}