20zr暑期AB班十连测day4

~~自己抄自己~~

50pts直接for就for过去了吧

100pts考虑选取一个素数p，然后mod p意义下只会有n^2/p个

然后先for第一个点，再for第二个点的第一维，然后就能算出y坐标是多少了，再去查表，看那个点是哪个点

你可以发现我们能够exgcd去解决，对于一个点，首先解出一个最小解，然后我们从这个解上去+a'找看有没有对应的，花费总解数solve，如果解很多的放入一个vector中就暴力一下

你会发现由于只有1e9所以很快的，大部分解都很少

很套路？分段权值为逆序对数+W

猜一下有决策单调性

结果我们没法在O(1)时间算出逆序对，其实可以莫队？的思路

决策单调性：单调栈/队列上二分

CDQ分治+决策单调性二分

决策单调性二分里面的操作可以参考CF868F Yet Another Minimization Problem

就能做到O(nlog^3n)

如果可以离线可以O(\sqrt n)修改O(1)分块

值域分块就是首先我们处理出每个块内部的前缀和，那么查询时块块之间前缀和+块内前缀和

然后强制在线可以可持久化分块，空间复杂度是带根号的，绝对完蛋啊

代码细节:移动端点的时候我们对于一个逆序对只在大的时候计算,work的时候找到区间最优决策点要另开变量因为不一定能update

code:


#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define ll long long
const int MAXN = 5e5 + 7;
int n, X, a[MAXN], q, p;
ll f[MAXN], b[MAXN], res;

inline void add(int x, int y) {
	for(; x <= n; x += lowbit(x)) {
		b[x] += y;
	}
	return ;
}

inline void chkmin(ll &x, ll y) {
	if(x > y)x = y;
}

inline ll query(int x) {
	ll ret = 0;
	for(; x; x -= lowbit(x)) {
		ret += b[x];
	}
	return ret;
}

inline ll get(int l, int r) {
	// printf("%d %d %d %d %d\n", l, r, p, q, res);
	while(q < r) {
		++q;
		res += q - p - query(a[q]);
		// printf("%d %d\n", q - p, query(a[q]));
		add(a[q], 1);
	}
	while(p > l) {
		--p;
		res += query(a[p]);
		add(a[p], 1);
	}
	while(q > r) {
		add(a[q], -1);
		res -= q - p - query(a[q]);//q>r,q变小,我们在大的时候计算逆序对
		q--;
	}
	while(p < l) {
		add(a[p], -1);
		res -= query(a[p]);
		p++;
	}
	return res;
}

inline void work(int l, int r, int L, int R) {//解决l,r的答案问题,利用L,R的决策点
	// if(l == r) {
	// 	for(int i = L; i <= R; ++i) {
	// 		chkmax(f[l], f[i] + get(i + 1, l));
	// 	}
	// 	return;
	// }
	// if(L == R) {
	// 	for(int i = l; i <= r; ++i) {
	// 		chkmax(f[i], f[L] + get(L + 1, i));
	// 	}
	// 	return ;
	// }
	// printf("qwq - >:l%d r%d L%d R%d\n", l, r, L, R);
	// for(int i = L; i <= R; ++i) {
	// 	printf("%d ", f[i]);
	// }
	// puts("");
	int mid = (l + r) >> 1, pos = -1;
	ll minx = 1e18;
	for(int i = L; i <= R; ++i) {
		ll tmp = f[i] + get(i + 1, mid) + X;
		// printf("%d?%d\n", tmp, f[mid]);
		if(tmp < minx) {
			minx = tmp;
			pos = i;
		}
	}
	chkmin(f[mid], minx);
	assert(~pos);
	if(l < mid)work(l, mid - 1, L, pos);
	if(r > mid)work(mid + 1, r, pos, R); //决策点单调不减
}

inline void solve(int l, int r) {
	if(l == r)return ;
	int mid = (l + r) >> 1;
	// printf("solve:%d?%d\n", l, r);
	solve(l, mid);
	work(mid + 1, r, l, mid);
	solve(mid + 1, r);
}

int main() {
	scanf("%d%d", &n, &X);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	memset(f, 0x3f3f3f3f, sizeof(f));
	f[0] = 0;
	// printf("%lld?%lld\n", f[1], f[2]);
	p = 1, q = 0;
	solve(0, n);
	printf("%lld\n", f[n]);
	return 0;
}

带花树

路径简单，而且颜色交替，而且端点不同，两两不交，端点标记，权值和最大

要么带权匹配，要么带权拟阵交

相当于拆下点然后路径要从黑到白从白到黑，而且两个点之间有一个被选用

并且我们对于两个拆出的点之间连一条边权为0的边

然后对于两个颜色不同的拆点，是一个端点，我们可以再拆出一个新建点来把
点权变成边权

然后对于那个新点连向的那两个拆点的边的边权就是那个点的点权

新建的点两两连边连成完全图，防止我们没有用上而没有完备匹配

然后如果有奇数个标记点我们就再额外开一个新建点，使得这个图有完美匹配

夏晓光(loveJY)的博客

20zr暑期AB班十连测day3