【日常小测】异或与区间加

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题又是一道多算法互补的题目
通过分类处理使复杂度达到$O((n+m)\sqrt{n})$
具体来讲是将以下两个算法结合:

1. 枚举右端点的值,若左端点的合法位置超过$\sqrt{n}$个

考虑每一个左右端点应该加减多少,使用前缀和技巧将复杂度优化到$O(n + m)$
具体细节不想写了,有点麻烦_(:з」∠)_
然后因为合法位置超过了$\sqrt{n}$个,所以这种情况至多出现$\sqrt{n}$个,复杂度符合要求

2. 其他情况

因为左端点不超过$\sqrt{n}$个,所以可以排序之后依次处理
使用分块来维护左端点的值,单次修改是$\sqrt{n}$的,单次查询是$O(1)$的

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int
using namespace std;

const int N = 150009;
const int MOD = 1073741824;
const int blk_sz = 800;

int n, m, k, a[N];
UI a1[N], ans[N], blk_tag[N], tag[N];
vector<int> num, pos_list[N];
vector<pair<int, int> > left_list[N], right_list[N];
struct Query{
	int l, r, w;
	inline bool operator < (const Query &QQQ) const {
		return r > QQQ.r;
	} 
}q[N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline int find(int x) {
	int l = 0, r = num.size() - 1, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (num[mid] == x) {
			return mid;
		} else if (num[mid] < x) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return -1;
}

inline void solve(int A, int B) {
	static UI a2[N], cur;
	memset(a2, 0, sizeof(a2));
	for (int i = 1; i <= n; i++) {
		a2[i] = a2[i - 1] + (a[i] == num[B]);
	}
	cur = 0;
	for (int i = n; i; i--) {
		if (a[i] == num[B]) {
			cur += a1[i];
		}
		if (a[i - 1] == num[A]) {
			ans[i] += cur;
		}
		for (int j = 0; j < (int)left_list[i].size(); ++j) {
			cur -= (UI)left_list[i][j].second * (a2[left_list[i][j].first] - a2[i - 1]);
		}
	}
	memset(a2, 0, sizeof(a2));
	for (int i = 1; i <= n; ++i) {
		a2[i] = a2[i - 1] + (a[i - 1] == num[A]);
	}
	cur = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i - 1] == num[A]) {
			cur -= a1[i];
		}
		if (a[i] == num[B]) {
			ans[i + 1] += cur;
		}
		for (int j = 0; j < (int)right_list[i].size(); ++j) {
			cur += (UI)right_list[i][j].second * (a2[i] - a2[right_list[i][j].first - 1]);
		}
	}
}

int main() {
	freopen("xor.in", "r", stdin);
	freopen("xor.out", "w", stdout);
	n = read(); m = read(); k = read();
	num.push_back(0);
	for (int i = 1; i <= n; ++i) {
		a[i] = a[i - 1] ^ read();
		num.push_back(a[i]);
	}
	sort(num.begin(), num.end());
	num.resize(unique(num.begin(), num.end()) - num.begin());
	for (int i = 0; i <= n; i++) {
		int pp = find(a[i]);
		pos_list[pp].push_back(i);
	}
	for (int i = 1, l, r, w; i <= m; ++i) {
		l = q[i].l = read();
		r = q[i].r = read();
		w = q[i].w = read();	
		left_list[l].push_back(make_pair(r, w));
		right_list[r].push_back(make_pair(l, w));
		a1[l] += w; 
		a1[r + 1] -= w;
	}
	sort(q + 1, q + 1 + m);
	for (int i = 1; i <= n; ++i) {
		a1[i] += a1[i - 1];
	}
	for (int i = 0; i < (int)num.size(); i++) {
		int r = i, l = find(num[i] ^ k);
		if (l != -1 && (int)pos_list[l].size() > blk_sz) {
			solve(l, r);
		}
	}
	for (int r = n, cur = 0; r; r--) {
		while (cur < m && q[cur + 1].r >= r) {
			++cur;
			for (int i = q[cur].l, lim = min(q[cur].r, (q[cur].l / blk_sz + 1) * blk_sz - 1); i <= lim; ++i) {
				tag[i] += q[cur].w;
			}
			for (int i = q[cur].l / blk_sz + 1, lim = q[cur].r / blk_sz - 1; i <= lim; ++i) {
				blk_tag[i] += q[cur].w;
			}
			for (int i = max(q[cur].r / blk_sz, q[cur].l / blk_sz + 1) * blk_sz; i <= q[cur].r; ++i) {
				tag[i] += q[cur].w;
			}
		}
		int t = find(a[r] ^ k);
		if (t != -1 && (int)pos_list[t].size() <= blk_sz) {
			for (int tt = 0; tt < (int)pos_list[t].size(); ++tt) {
				int l = pos_list[t][tt] + 1;
				if (l <= r) {
					ans[l] += tag[l] + blk_tag[l / blk_sz];
					ans[r + 1] -= tag[l] + blk_tag[l / blk_sz];
				} else {
					break;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		ans[i] += ans[i - 1];
		printf("%d ", ans[i] % MOD);
	}
	return 0;
}

【UOJ 246】[UER #7] 套路

相关链接

题目传送门:http://uoj.ac/contest/35/problem/246
官方题解:http://matthew99.blog.uoj.ac/blog/2085

解题报告

这题真™是套路深啊!
一言不合就根号大军了

具体来说的话,我们考虑答案的区间长度为 $ len$
并且钦定一个阀值 $ S$

  1. 考虑 $ len<S$ 的情况
    我们枚举右端点,暴力向左扫 $ S$ 个就可以了

  2. 考虑 $ len \ge S$ 的情况
    我们发现相似度不会超过 $ \frac{m}{{len – 1}}$
    于是考虑在权值上暴力向两边扫 $ S$ 个

这样的话,我们就可以在 $ O(nS + n\frac{m}{s})$ 的复杂度内解决这个问题了
不难发现,当 $ S = \sqrt m$ 时复杂度最优

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;

int n,m,K,S,a[N],gap[N],lst[N];
LL vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); m = read(); 
	K = read(); S = sqrt(m) + 1;
	for (int i=1;i<=n;i++) a[i] = read();
	
	memset(gap,60,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=i-1;j>=i-S&&j;--j) {
			gap[j] = min(gap[j], gap[j+1]);
			gap[j] = min(gap[j], abs(a[i] - a[j]));
			if (i-j+1 >= K) vout = max(vout, (LL)(i - j) * gap[j]);
		}
	}
	memset(gap,0,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=S;j++) {
			if (j) gap[j] = max(gap[j], gap[j-1]);
			if (a[i]-j >= 1) gap[j] = max(gap[j], lst[a[i]-j]);
			if (a[i]+j <= m) gap[j] = max(gap[j], lst[a[i]+j]);
			if (i-gap[j] >= K) vout = max(vout, (LL)(i-gap[j]-1) * (j+1)); 
		}
		lst[a[i]] = i;
	}
	printf("%lld\n",vout);
	return 0;
}