T20201109

Posted on Edited on In Word count in article: 2.1k Reading time ≈ 8 mins.
大东辰的测试

T1(树上的数)

直观感觉是 \(\text{DFS}\) 序 + 线段树，时间复杂度 \(O(m\log n)\)，然后常数大的一批，\(\text{T}\) 成 \(60\) 分。

其实吧，可以直接每次暴力遍历整棵树，给一个永久标记即可

Code

Code 
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
#include <bits/stdc++.h>
#define ls (x << 1)
#define rs (x << 1 | 1)

using namespace std;

const int maxn = 5e6 + 10;

int cnt, cur, tot;
int head[maxn], edge[maxn], nxt[maxn];
bool have[maxn];

inline void addedge(int u, int v)
{
	nxt[++cur] = head[u];
	head[u] = cur;
	edge[cur] = v;
}

void dfs(int u)
{
	if (have[u]) return;
	--tot, have[u] = 1;
	for (int i = head[u]; i; i = nxt[i])
		dfs(edge[i]);
}

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x; 
}

int ans(0);
int main()
{
	freopen ("tree.in", "r", stdin);
	freopen ("tree.out", "w", stdout);
	int n = read(), m = read(), pf(1);
	tot = n;
	addedge(1, 2);
	int a = read(), b = read();
	for (int i = 3; i <= n; ++i) {
		pf = ((1ll * pf * a + b) ^ 19760817) % (i - 1) + 1;
		addedge(pf, i);
	}

	int q = read(), x = read(), y = read();
	for (int i = 1; i <= m; ++i) {
		dfs(q);
		ans ^= tot;
		q = (((1ll * q * x + y) ^ 19760817) ^ (i + 1 << 1)) % (n - 1) + 2;
	}
	printf ("%d\n", ans);
}

T2(时代的眼泪)

首先交换求和顺序，然后就可以发现诸多有用的性质。

算法一 (25分)

就是每次暴力查询，单次查询的时间复杂度为 \(O(n\log n)\)。

就是可以用树状数组维护，这一条链有多少个点的权值严格大于当前点，然后就可以加入贡献了。

Code 
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
int root, t[maxn];
ll ans;

inline void add(int x, int val) 
{
  while (x <= n) {
    t[x] += val;
    x += lowbit(x);
  }
}

inline int query(int x) 
{
  int res(0);
  while (x) {
    res += t[x];
    x -= lowbit(x);
  }
  return res;
}

void dfs(int u, int v, int dep)
{
  add (val[u], 1);
  ans += dep - query(val[u]);
  for (int i = head[u]; i; i = nxt[i]) {
    if (edge[i] == v) continue;
    dfs(edge[i], u, dep + 1);
  }
  add (val[u], -1);
}

int solve()
{
  while (m--) {
    root = read(), ans = 0;
    dfs(root, 0, 1);
    printf ("%lld\n", ans);
  }
}

算法二 (20分)

整张图是一个 \(1\sim n\) 的链，所以每个点的贡献是一定的，就可以 \(O(n\log n)\) 预处理出所有点贡献，做两次前缀和就可以了。

结合算法一，就可以获得 \(45\) 分的好成绩。

Code 

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
int root, ans;
ll l[maxn], r[maxn];
int t[maxn];

inline void add(int x, int val)
{
  while (x <= n) {
    t[x] += val;
    x += lowbit(x);
  }
}

inline int query(int x)
{
  int res(0);
  while (x) {
    res += t[x];
    x -= lowbit(x);
  }
  return res;
}

int solve()
{
  memset (l, 0, sizeof l);
  memset (r, 0, sizeof r);
  memset (t, 0, sizeof t);

  for (int i = 1; i <= n; ++i) {
    l[i] = l[i - 1] + query(val[i] - 1);
    add(val[i], 1);
  }

  memset (t, 0, sizeof t);
  for (int i = n; i; --i) {
    r[i] = r[i + 1] + query(val[i] - 1);
    add(val[i], 1);
  }

  while (m--) {
    root = read();
    printf ("%lld\n", l[root] + r[root]);
  }
}

算法三 (20分)

就是一个以 \(1\) 为中心的一个菊花图，这个手摸一下就可以发现，我们可以 \(O(n)\)，预处理出 \(1\) 作为根时的答案，然后在考虑根变成其他的时候的答案变化量，这个变化量的处理单词时间复杂度是 \(O(\log n)\)。

结合算法一、算法二就可以取得 \(65\) 分的好成绩。

Code 
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
int root, ans, jub(0);
int t[maxn];

inline void add(int x, int val) 
{
  while (x <= n) {
    t[x] += val;
    x += lowbit(x);
  }
}

inline int query(int x) 
{
  int res(0);
  while (x) {
    res += t[x];
    x -= lowbit(x);
  }
  return res;
}

void solve()
{
  for (int i = 1; i <= n; ++i)
    if (val[1] > val[i]) ++jub;

  for (int i = 1; i <= n; ++i)
    add(val[i], 1);

  while (m--) {
    root = read();
    if (val[root] < val[1]) --jub;
    if (root > 1) printf ("%d\n", jub + query(val[root] - 1));
    else printf ("%d\n", jub);
    if (val[root] < val[1]) ++jub;
  }
}

About 80

就是 \(Q=1\) 时，可以用算法一，这样一来就可以拿到 \(80\) 分的好成绩

我考场就是 \(Q=1\) 判错了就只有 \(65\)。。。

所以个人认为这道题十分的良心，给足了部分分，整整 \(80\)。

About 100

这其实是一个换根 \(dp\)，看上去也很像一个换根 \(dp\)，可惜当时就是没有推出来。

就是考虑，从一个根到另一个根，它少了些什么，它又该多一些什么。

⇓

可以发现，少的那一部分是现在的根对原来的根的贡献，而多的那一部分则是原来的根作为子树对现在的根的贡献。

首先，声明几个数组

  • \(f_i\) 表示在以 \(i\) 为根的子树中，有多少个点的点权严格小于当前节点
  • \(g_i\) 表示在以 \(i\) 为根的子树中，有多少个点的点权严格小于当前节点的父亲
  • \(k_i\) 表示在所有的点里面，有多少个点的点权严格小于当前节点

所有可以有如下转移： \[ ans_v = ans_u - g_v + k_v - f_v; \] 然后 \(f、g\) 的求法是十分的巧妙，它可以类似查分的形式出现，所以这道题就结束了。

Code

Code 
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

typedef long long ll;
int n, m, q, cur, fa[maxn];
int a[maxn], b[maxn];
int f[maxn], g[maxn], k[maxn];

int head[maxn], edge[maxn << 1], nxt[maxn << 1];

int t[maxn];
ll ans[maxn];

inline int read()
{
	int x(0);
	char o(getchar());
	while (o < '0' || o > '9') o = getchar();
	for (; o >= '0' && o <= '9'; o = getchar())
		x = (x << 1) + (x << 3) + (o ^ 48);
	return x;
}

inline void addedge(int u, int v) 
{
	nxt[++cur] = head[u];
	head[u] = cur;
	edge[cur] = v;
}

inline int lowbit(int x)
{
	return x & -x;
}

inline void add(int x, int val)
{
	while (x <= m) {
		t[x] += val;
		x += lowbit(x);
	}
}

inline int query(int x)
{
	int res(0);
	while (x) {
		res += t[x];
		x -= lowbit(x);
	}
	return res;
}

void dfs(int u, int father)
{
	int pre = query(a[u] - 1);
	add(a[u], 1);
	f[u] = -pre, fa[u] = father;
	for (int i = head[u]; i; i = nxt[i]) {
		if (edge[i] == father) continue;
		g[edge[i]] = -pre;
		dfs(edge[i], u);
		pre = query(a[u] - 1);
		g[edge[i]] += pre;
	}
	f[u] += pre;
}

void dfs(int u)
{
	for (int i = head[u], v; i; i = nxt[i]) {
		v = edge[i];
		if (v == fa[u]) continue;
		ans[v] = ans[u] - g[v] + k[v] - f[v];
		dfs(v);
	}
}

int main()
{
	freopen ("tears.in", "r", stdin);
	freopen ("tears.out", "w", stdout);
	n = read(), q = read();
	for (int i = 1; i <= n; ++i) 
		a[i] = b[i] = read();
	
	sort (b + 1, b + n + 1);
	m = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= n; ++i)
		a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;

	int u, v;
	for (int i = 1; i < n; ++i) {
		u =  read(), v = read();
		addedge(u, v), addedge(v, u);
	}

	dfs(1, 0);

	for (int i = 1; i <= n; ++i) 
		k[i] = query(a[i] - 1), ans[1] += f[i];

	dfs(1);
	while (q--) printf ("%lld\n", ans[read()]);
}

T3(传统艺能)

考场暴力 \(25\)，还行吧

就是考虑这么一个矩阵 \(A_{i,j}\) 表示以 \(i\) 开头以 \(j\) 结尾的方案数，但是这个 \(j\) 其实是不存在的。

所以当两个矩阵相乘的时候，刚好就表示了这个方案的转移，所以可以用线段树来维护，每一个节点就是一个矩阵，就这样结束了。

至于为什么它能保证本质不同呢？

这个与矩阵乘法的性质有关，就不赘述了。

Code

Code 
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<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define ll long long
inline 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-'0',ch=getchar();
	return x*f;
}
void wr(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>=10)wr(x/10);
	putchar('0'+x%10);
}
const ll MAXN=1e5+10,mod=998244353;
inline void tmod(ll &x){x%=mod;}
inline void rmod(ll &x){x+=x>>31&mod;}
struct Mat{
	ll a[4][4];
	inline Mat operator *(const Mat &b)const{
		Mat c;
		#define V(x) a[i][(x)]*b.a[(x)][j]
		c.a[0][0]=1;fp(i,1,3)c.a[0][i]=0;
		fp(i,1,3)
		fp(j,0,3)
		tmod(c.a[i][j]=V(0)+V(1)+V(2)+V(3));
		return c;
	}
}val[MAXN<<2];
#define lson o<<1
#define rson o<<1|1
Mat ask(ll o,ll l,ll r,ll ql,ll qr){
	if(ql==l&&qr==r)return val[o];
	ll mid=l+r>>1;
	if(qr<=mid)return ask(lson,l,mid,ql,qr);
	if(ql>mid)return ask(rson,mid+1,r,ql,qr);
	return ask(lson,l,mid,ql,mid)*ask(rson,mid+1,r,mid+1,qr);
}
void mdy(ll o,ll l,ll r,ll p,ll v){
	if(l==r){
		mem(val[o].a);
		fp(i,0,3)val[o].a[i][i]=val[o].a[v][i]=1;
		return;
	}
	ll mid=l+r>>1;
	if(p<=mid)mdy(lson,l,mid,p,v);
	else mdy(rson,mid+1,r,p,v);
	val[o]=val[lson]*val[rson];
}
char s[MAXN],ss[5];
void build(ll o,ll l,ll r){
	if(l==r){
		ll v=s[l]-'A'+1;
		fp(i,0,3)val[o].a[i][i]=val[o].a[v][i]=1;
		return;
	}
	ll mid=l+r>>1;
	build(lson,l,mid);build(rson,mid+1,r);
	val[o]=val[lson]*val[rson];
}
ll n,Q;
int main(){
	freopen("string.in","r",stdin);freopen("string.out","w",stdout);
	n=read();Q=read();
	scanf("%s",s+1);
	build(1,1,n);
	while(Q--){
		ll op=read();
		if(op==1){
			ll p=read();scanf("%s",ss);
			mdy(1,1,n,p,ss[0]-'A'+1);
		}
		else{
			ll l=read(),r=read();Mat t=ask(1,1,n,l,r);
			ll res=0;fp(i,1,3)tmod(res+=t.a[i][0]);
			wr(res);putchar('\n');
		}
	}
	return 0;