2018.9.21校内测试

发表于

解题报告—9.21

$\text{T1}$ 相遇

反思

T1 考到了 LCA，之前觉得没必要学，虽然也看过些文章，但大部分都没看懂，所以一直都不会，结果今天出上了这样的一道题，真尴尬，想着写写暴力吧，发现暴力也是求 LCA，无奈，遂放弃，考完试的下午就开始学 LCA，以后有能力学的东西尽量学学，不能老想着偷懒。

解题思路

画几个图会发现 $a\rightarrow b,c\rightarrow d$ 两条路径如果能够相交的话，需要满足其中一对点的 $\text{LCA}$ 在另两个点之间的路径上。

而一个点 $x$ 在一条路径 $s\rightarrow t$ 上的充要条件是如下：

  • $depth[\text{LCA}(s,t)]\le depth[x]$
  • $\text{LCA}(x,s)=x \ ||\ \text{LCA}(x,t)=x$

然后我们就可以做 $\text{LCA}$ 进行求解，一组数据最多询问 $4$ 次。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 2e5+3;
int n, head[maxn], cnt, depth[maxn], T, fa[maxn][32], m;
struct edge {
	int to, nxt;
}ed[maxn], tmp;
struct P100 {
	inline void reset() {
		cnt = 0;
		tmp.to = tmp.nxt = 0;
		fill(ed+1, ed+1+maxn-3, tmp);
		memset(head, 0, sizeof(head));
		memset(depth, 0, sizeof(depth));
		memset(fa, 0, sizeof(fa));
	}
	inline void addedge(int x, int y) {
		ed[++cnt].nxt = head[x], head[x] = cnt, ed[cnt].to = y;
		ed[++cnt].nxt = head[y], head[y] = cnt, ed[cnt].to = x;
	}
	inline void init() {
		for(int j=1; 1<<j<=n; j++)
			for(int i=1; i<=n; i++)
				fa[i][j] = fa[fa[i][j-1]][j-1];
	}
	inline void dfs(int u) {
		for(int i=head[u]; i; i=ed[i].nxt) {
			if(ed[i].to == fa[u][0]) continue;
			fa[ed[i].to][0] = u;
			depth[ed[i].to] = depth[u] + 1;
			dfs(ed[i].to);
		}
	}
	inline int lca(int a, int b) {
		if(depth[a] > depth[b]) swap(a, b);
		int h = depth[b] - depth[a];
		for(int i=0; 1<<i<=h; i++)
			if((1<<i)&h) b = fa[b][i];
		if(a != b) {
			for(int i=(int)log2(n); i>=0; i--) {
				if(fa[a][i] != fa[b][i])
					a = fa[a][i], b = fa[b][i];
			}
			a = fa[a][0];
		}
		return a;
	}
	inline void solve() {
		dfs(1);
		init();
	}
	inline bool judge(int a, int b, int c, int d) {
		int x = lca(a, b), y = lca(c, d);
		if(depth[x] < depth[y]) swap(x, y), swap(a, c), swap(b, d);
		if(lca(x, c) == x || lca(x, d) == x) return true;
		return false;
	}
}p100;
int main() {
	freopen("railway.in", "r", stdin);
	freopen("railway.out", "w", stdout);
	scanf("%d", &T);
	while (T--) {
		p100.reset();
		scanf("%d%d", &n, &m);
		int x, y;
		for(int i=1; i<n; i++) {
			scanf("%d%d", &x, &y);
			p100.addedge(x, y);
		}
		p100.solve();
		int a, b, c, d;
		for(int i=1; i<=m; i++) {
			scanf("%d%d%d%d", &a, &b, &c, &d);
			if(p100.judge(a, b, c, d)) printf("YES\n");
			else printf("NO\n");
		}
	}
	fclose(stdin);
	fclose(stdout);
}

$\text{T2}$ 计数

反思

不开 long long 见祖宗，写了个 $60$ 分的暴力，因为没开 long long 所以 WA 成了 30 分，以后做题先看好数据范围，可以为了以防万一，能开 long long 就开 long long 。

解题思路

在考场上写了个线段树维护区间最大最小值。然后 $N^2$ 枚举，左右端点，求和。算上查询的时间是 $\log N$ 总时间复杂度为 $N^2\log N$ 可以过 60 分。

再说正解：

题目大意可以简化为求下面这个式子的值：
$$
\sum_{r=1}^{n}\sum_{l=1}^{r}max(a[x]-a[y],l\le x,y\le r)
$$
观察上面的式子，其实可以从 $1\rightarrow n$ 算出每个数对答案的影响，相加就是答案。

那么怎么算贡献呢。用单调栈维护，一个点被弹出后就将其贡献减去，被压入后，就将其贡献加上。

求作为最大值的贡献和求作为最小值的贡献其实差不多，求最小值时将数组变成负数就又变成了求最大值的问题。

所以可以用一个函数解决。

代码

60 分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1e5+3, inf = 2147483647;
typedef long long LL;
LL T, n, a[maxn];
struct Tree {
	LL l, r, mx, mn;
}tree[400003], tmp;
LL ans_mn = inf, ans_mx;
struct P60 {
	inline void init() {
		tmp.l = tmp.r = tmp.mx = 0;
		tmp.mn = inf;
		fill(tree+1, tree+400001, tmp);
	}
	inline void build(int k, int ll, int rr) {
		tree[k].l = ll, tree[k].r = rr;
		if(ll == rr) {
			scanf("%d", &tree[k].mn);
			tree[k].mx = tree[k].mn;
			return ;
		}
		int mid = (ll + rr) >> 1;
		build(k << 1, ll, mid);
		build((k << 1)+1, mid+1, rr);
		tree[k].mx = max(tree[k<<1].mx, tree[(k<<1)+1].mx);
		tree[k].mn = min(tree[k<<1].mn, tree[(k<<1)+1].mn);
	}
	inline void check(int k, int ll, int rr) {
		if(tree[k].l >= ll && tree[k].r <= rr) {
			ans_mn = min(ans_mn, tree[k].mn);
			ans_mx = max(ans_mx, tree[k].mx);
			return ;
		}
		int mid = (tree[k].l + tree[k].r) >> 1;
		if(mid >= ll) check(k << 1, ll, rr);
		if(mid < rr) check((k<<1)+1, ll, rr);
	}
	inline LL solve() {
		init();
		build(1, 1, n);
		LL Ans = 0;
		for(int i=1; i<=n; i++) {
			for(int j=i; j<=n; j++) {
				ans_mx = 0, ans_mn = inf;
				check(1, i, j);
				Ans += ans_mx - ans_mn;
			}
		}
		return Ans;
	}
}p60;
int main() {
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);
	cin>>T;
	while (T--) {
		cin>>n
		cout<<p60.solve()<<endl;
	}
	fclose(stdin);
	fclose(stdout);
}

100 分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1e5+3;
typedef long long LL;
LL s[maxn], n, a[maxn], T;
struct P100 {
	inline LL solve() {
		LL h = 1, t = 0, sum = 0, ans = 0;
		for(int i=1; i<=n; i++) {
			while (h <= t && a[i] > a[s[t]]) sum -= a[s[t]] * (s[t]-s[t-1]), t--;
			s[++t] = i;
			sum += a[i] * (i-s[t-1]);
			ans += sum;
		}
		return ans;
	}
}p100;
int main() {
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);
	cin>>T;
	while (T--) {
		cin>>n;
		for(int i=1; i<=n; i++)
			cin>>a[i];
		LL ans = p100.solve();
		for(int i=1; i<=n; i++) a[i] = -a[i];
		cout<<ans + p100.solve()<<endl;
	}
	fclose(stdin);
	fclose(stdout);
}