决策单调性优化

首先合并所有体积相同为s的,价值从大到小排序, $sum_i$ 表示使用i个体积为s的最优权值

我们对于%s意义进行分组

然后考虑同一余数下的转移,形式类似 $g_S=\max g_{i-1,T}+sum_{S-T}$

然后观察到 $sum_{S-T}$ 这个东西是凸的,随着 $S-T$ 增大,增量会单调不减

也就是说我们有凸函数,然后最大化,所以单调队列维护决策单调性优化即可

当然你看一眼就发现这个转移分层,所以直接分治决策单调性优化即可

//考虑mslogm
//对于%s不同余数单独处理
//不难发现转移系数是凸的,因此对于一个点最大化是很不错的
//单调队列决策单调性应该可以??因为不太是单调栈吧
//等等啊..老哥这个东西是分层的啊...不需要在线啊
//分治逝一逝吧
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_back

const int inf = 1e9 + 7;
const int MAXN = 2e6 + 7;
const int MAXM = 1e5 + 7;

int n, m, mS, s[MAXN], w[MAXN];
vi v[MAXM];
int sum[MAXN], g[MAXN], f[MAXN], h[MAXN];

bool cmp(int x, int y) {
	return x > y;
}

namespace fastIO {
#define BUF_SIZE (1<<22)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

//每次取出g,然后更新h
inline void solve(int l, int r, int L, int R) {
	if(L == R) {//只有一个决策点...
		for(int i = l; i <= r; ++i) {
			if(i >= L)
				h[i] = max(g[L] + sum[i - L], h[i]);
		}
		return ;
	}
	int mid = (l + r) >> 1;
	int tmp = 0, rc = 0;
	for(int i = L; i <= R; ++i) {//枚举所有转移点
		if(i > mid)break;
		if(tmp < sum[mid - i] + g[i]) {
			tmp = sum[mid - i] + g[i];
			rc = i;
		}
	}
	h[mid] = max(h[mid], tmp);
	if(l <= mid - 1)solve(l, mid - 1, L, rc);
	if(mid + 1 <= r)solve(mid + 1, r, rc, R);
}

signed main() {
	// freopen("jewelry.in", "r", stdin);
	// freopen("jewelry.out", "w", stdout);
	n = read();
	m = read();
	for(int i = 1; i <= n; ++i) {
		s[i] = read();
		w[i] = read();
		v[s[i]].pb(w[i]);
		mS = max(mS, s[i]);
	}
	for(int i = 1; i <= mS; ++i) {//枚举体积
		if(v[i].empty())continue;//直接跳
		sort(v[i].begin(), v[i].end(), cmp);
		sum[0] = 0;
		for(int j = 0; j < v[i].size(); ++j) {
			sum[j + 1] = sum[j] + v[i][j];
		}
		for(int k = 0; k < i; ++k) {//%i意义剩余系
			int l = 0;
			for(; l * i + k <= m; l++) {
				g[l] = f[l * i + k];
				h[l] = 0;
			}
			--l;
			for(int q = v[i].size() + 1; q <= l; ++q)
				sum[q] = -inf;
			solve(1, l, 0, l);//考虑我们也可以不放数啊
			l = 0;
			for(; l * i + k <= m; ++l) {
				f[i * l + k] = max(f[i * l + k], h[l]);
			}
		}
	}
	for(int i = 1; i <= m; ++i) {
		printf("%lld ", f[i]);
	}
	return 0;
}

CF809E Surprise me!

$\phi(ij)=\frac{\phi(i)\phi(j)gcd(i,j)}{\phi(gcd(i,j))}$

然后我们有

随便反演,枚举gcd有

然后莫反

合并两个东西d,k

f(T)是关于T的那些系数和,我们有最后

\sum \sum \frac{\phi(i)\phi(j)gcd(i,j)}{\phi(gcd(i,j))}dis(a_i,a_j)\\ =\sum \frac{d}{\phi(d)}\sum \sum \phi(i)\phi(j)[gcd(i,j)==d]dis(a_i,a_j)\\ =\sum \frac{d}{\phi(d)}\sum_{k|i,k|j} \mu(k) \phi(i)\phi(j)dis(a_i,a_j)\\ =\sum_T f(T)\sum_{i=1,T|i}^n\phi(i)\sum_{j=1,T|j}^n\phi(j)dis(a_i,a_j)

这个式子对于所有T的倍数建立虚树统计树上贡献即可,具体的,我们有

2\sum v_idep_i\sum v_j-2\sum v_i v_jdep_{lca}

照着这个式子写就好了

注意不能算因为LCA而产生的点的贡献!!就是第一个式子!!

然后建立虚树要好好想想

处理f函数千万别自然溢出了

//暴力虚树
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 6e5 + 7;

int n, a[MAXN], rt, b[MAXN];
struct rec {
	int x, y;
} e[MAXN];
int ccnt2, fst[MAXN], nxt2[MAXN], to2[MAXN];
int ccnt, nxt[MAXN], to[MAXN], home[MAXN];
vi v;
ll ans, ans1, f[MAXN], tmp, dp[MAXN], ans2;

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	to[ccnt] = y;
	home[x] = ccnt;
}

inline void ct2(int x, int y) {
	ccnt2++;
	nxt2[ccnt2] = fst[x];
	to2[ccnt2] = y;
	fst[x] = ccnt2;
}

inline int add(int x, int y) {
	x += y;
	if(x >= P)x -= P;
	return x;
}


inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

int isp[MAXN], phi[MAXN], tot, pri[MAXN], dep[MAXN], mu[MAXN];
int dfn[MAXN], depp, fa[MAXN], siz[MAXN], son[MAXN], top[MAXN];

inline int LCA(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]])
			swap(x, y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])swap(x, y);
	return x;
}

inline void dfs2(int u, int topf) {
	top[u] = topf;
	if(!son[u])return ;
	dfs2(son[u], topf);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == fa[u] || v == son[u])continue;
		dfs2(v, v);
	}
	return ;
}

inline void dfs1(int u, int F) {
	dfn[u] = ++depp;
	dep[u] = dep[F] + 1;
	siz[u] = 1;
	fa[u] = F;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])son[u] = v;
	}
	return ;
}

inline void init() {
	phi[1] = 1;
	mu[1] = 1;
	for(int i = 2; i <= n; ++i) {
		if(!isp[i]) {
			isp[i] = 1;
			pri[++tot] = i;
			phi[i] = i - 1;
			mu[i] = -1;
		}
		for(int j = 1; j <= tot  && i * pri[j] <= n; ++j) {
			isp[i * pri[j]] = 1;
			if(i % pri[j] == 0) {
				phi[i * pri[j]] = phi[i] * pri[j];
				break;
			}
			mu[i * pri[j]] = -mu[i];
			phi[i * pri[j]] = (pri[j] - 1) * phi[i];
		}
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for(int d = 1; d <= n; ++d) {
		for(int i = d; i <= n; i += d) {
			f[i] = add(f[i], (1ll * d * ksm(phi[d], P - 2) % P * mu[i / d] % P + P) % P);
			f[i] = (f[i] + P) % P;
		}
	}
	return;
}

inline int gcd(int x, int y) {
	return y == 0 ? x : gcd(y, x % y);
}

bool cmp(int x, int y) {
	return dfn[x] < dfn[y];
}

int tp, st[MAXN], ance;

inline void ins(int x) {
	if(!tp) {
		rt = x;
		st[tp = 1] = x;
		return ;
	}
	ance = LCA(st[tp], x);
	if(dep[ance] < dep[rt]) {
		rt = ance;
	}
	while((tp > 1) && (dfn[ance] < dfn[st[tp - 1]])) {//-1!!
		ct2(st[tp - 1], st[tp]);
		--tp;
	}
	if(dfn[st[tp]] > dfn[ance]) {
		ct2(ance, st[tp]);
		--tp;
	}
	if(st[tp] != ance || (!tp))st[++tp] = ance;
	if(dep[x] < dep[rt])rt = x;
	st[++tp] = x;
}

int tl, q[MAXN], vis[MAXN];

inline void dfs(int u) {
	if(vis[u])
		ans1 = add(ans1, 2ll * phi[a[u]] % P * phi[a[u]] % P * dep[u] % P),	dp[u] = phi[a[u]];
	q[++tl] = u;
	ll tmp2 = 0;
	for(int i = fst[u]; i; i = nxt2[i]) {
		int v = to2[i];
		dfs(v);
		tmp2 = add(tmp2, dp[u] * dp[v] % P);
		dp[u] = add(dp[u], dp[v]);
	}
	ans2 = add(ans2, (4ll * tmp2 % P * dep[u] % P) % P);
	return ;
}

inline void solve() {
	for(int i = 1; i <= n; ++i) {
		if(i > n / 2)break;
		for(int j = i; j <= n; j += i)
			if(b[j]) {
				v.pb(b[j]);
			}
		//所有倍数
		if(v.empty())continue;
		sort(v.begin(), v.end(), cmp);
		tmp = 0;
		ll qwq = 0;
		for(auto u : v) {
			tmp = add(tmp, 1ll * phi[a[u]] * dep[u] % P);
			qwq = add(qwq, phi[a[u]]);
			vis[u] = 1;
			ins(u);
		}
		while(tp > 1) {
			--tp;
			ct2(st[tp], st[tp + 1]);
		}
		dfs(rt); //统计答案QAQ
		tmp = 1ll * tmp * qwq % P;
		ans = add(ans, ((tmp * 2ll % P - ans1 - ans2 + P + P) % P) % P * f[i] % P);
		tp = 0;
		ans1 = 0;
		ans2 = 0;
		ccnt2 = 0;
		for(int i = 1; i <= tl; ++i) {
			fst[q[i]] = 0;
			dp[q[i]] = 0;
			vis[q[i]] = 0;
		}
		tl = 0;
		v.clear();
	}
	return ;
}

int main() {
	// freopen("sm.in", "r", stdin);
	// freopen("sm.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		b[a[i]] = i;//反向权值
	}
	for(int i = 1; i < n; ++i) {
		scanf("%d%d", &e[i].x, &e[i].y);
		ct(e[i].x, e[i].y);
		ct(e[i].y, e[i].x);
	}
	init();
	solve();//枚举约数,建立虚树...然后虚树上dfs QAQ
	ans = ans * ksm(1ll * n * (n - 1) % P, P - 2) % P;
	printf("%lld\n", ans);
	return 0;
}

对于矩形,我们可以考虑扫描线,这个还是很简单的..

对于每个顶点,先按照逆时针顺序排好

那么多边形的n条边就相当于n条有向线段,注意我们这里的方向是上凸壳向右,下凸壳向左!

先假设没有有向线段和x轴垂直,那么我们可以发现对于任意一条线段可以被放入成两个点之间区域

然后对于所有点,他们相邻的区域一起考虑,你会发现这些直线不可能有交点!

假设他们有交点,说明不可能是一个多边形内,那么如果是两个多边形内,这样就会导致有相交关系,就萎掉了

所以我们对于这个区域从上到下,按照 $x=v$ 交点的纵坐标排序,就能得到一个有序的有向线段排序结果

那么对于一个点(x,y),当扫描到 $X=x$ 时,我们有对应y点在某两个直线中间,将在他下面的线段(A,B)拿出来,判断从那个叉积是否大于0,如果大于等于0,说明他在那条线对应的多边形内

这个可以画图理解,当AB是正着的时候正好在内部,否则叉积小于0

然后考虑怎么实现这个,用set维护所有线段,然后每次访问到min(x,y)的时候加入,访问到max(x,y)的时候删除即可

然后查询,我们可以动态修改set的cmp函数,因为同一段内相对顺序不变的情况下,我们从 $X=v$ 交点纵坐标改为按照 $X=x$ 排序是没有问题的

对于垂直于x轴有向线段,我们还是枚举x坐标,然后取出 $x_a=x_b=i$ 的直线,从上到下排好,然后再去在纵坐标上二分第一个大于等于他的,看看有没有交点即可

复杂度 $O((\sum k + q)log\sum k)$

夏晓光(loveJY)的博客

某金牌训练营Day10

CF809E Surprise me!

注意不能算因为LCA而产生的点的贡献!!就是第一个式子!!

处理f函数千万别自然溢出了

某金牌训练营Day9