2018 年网络赛小结

ACM

自闭的周末。

2018 年网络赛小结（南京）

除了签到就什么都不会了。。

Problem F

LCT 维护子树大小。

利用 Monte Carlo 方法， 答案是 $ 2 * \frac {sz_u-1} {d_u} $，其中 $sz_u$ 是联通块大小，$d_u$ 是度数。

以为维护子树大小， LCT 可以直接搞。。其实这有个严重的问题：LCT 维护的是虚拟的大小信息。
一个点$x$，它的子树大小等于在 splay 中，它右节点的子树大小加上所有非偏爱边指向它的点的子树大小。
可以把这两个分别维护。
那么在 access 时，会有所改变，注意处理。
link 的时候，也不能像简单的 LCT 那样 

1
2
makeroot(x); 
pf[x] = y;

因为 y 和它的祖先的子树大小变了，还需要

1
2
access(y);
splay(y, 0);

子树的度可以直接在 link 和 cut 维护。

AC 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<cstdio>
#include<cstring>
#include<iostream>
	
using namespace std;
	
typedef long long ll;
const int N=100010;
const ll MOD = 998244353;
int ch[N][2],q[N],pre[N],size[N],sz[N], deg[N];   //sz储存的是虚儿子的信息
bool rev[N];
int n,Q;
	
int get(int bh)
{
    return ch[pre[bh]][0]==bh? 0:1;
}
	
int isroot(int bh)
{
    return ch[pre[bh]][0]!=bh&&ch[pre[bh]][1]!=bh;
}
	
void update(int bh)
{
    if (!bh) return;
    size[bh]=size[ch[bh][0]]+size[ch[bh][1]]+sz[bh]+1;
}
	
void push(int bh)
{
    if (!bh) return;
    if (rev[bh])
    {
        if (ch[bh][0]) rev[ch[bh][0]]^=1;
        if (ch[bh][1]) rev[ch[bh][1]]^=1;
        swap(ch[bh][0],ch[bh][1]);
        rev[bh]^=1;
    }
}
	
void rotate(int bh)
{
    int fa=pre[bh];
    int grand=pre[fa];
    int wh=get(bh);
    if (!isroot(fa)) ch[grand][ch[grand][0]==fa? 0:1]=bh;
    pre[bh]=grand;
    ch[fa][wh]=ch[bh][wh^1];
    pre[ch[fa][wh]]=fa;
    ch[bh][wh^1]=fa;
    pre[fa]=bh;
    update(fa);
    update(bh);
}
	
void splay(int bh)
{
    int top=0;
    q[++top]=bh;
    for (int i=bh;!isroot(i);i=pre[i])
        q[++top]=pre[i];
    while (top) push(q[top--]);
    for (int fa;!isroot(bh);rotate(bh))
        if (!isroot(fa=pre[bh]))
            rotate(get(bh)==get(fa)? fa:bh);
}
	
void expose(int bh)
{
    int t=0;
    while (bh)
    {
        splay(bh);
        sz[bh]+=size[ch[bh][1]]-size[t];
        //x原来的右儿子的LCT子树信息加入x的虚子树信息，
        //把x的新的右儿子的LCT子树信息从x的虚子树信息中减去
        ch[bh][1]=t;
        update(bh);
        t=bh;
        bh=pre[bh];
    }
}
	
void makeroot(int bh)
{
    expose(bh);
    splay(bh);
    rev[bh]^=1;
}
	
void link(int x,int y)
{
    makeroot(x);
    makeroot(y);
    pre[x] = y;
    sz[y] += size[x];
    deg[x] ++, deg[y] ++;
    update(y);
}
	
void cut(int x, int y)
{
	makeroot(x);
    expose(y);
    splay(y);
    deg[x] --, deg[y] --;
    size[y] -= size[x];
    pre[x] = ch[y][0] = 0;
    update(y);
}
	
bool find(int x, int y)
{
    makeroot(x);
    expose(y);
    splay(x);
    while(pre[y]) y = pre[y];
    return x == y;
}
	
ll pow_mod(ll a, ll b, ll m = MOD)
{
	ll ans = 1;
	while(b)
	{
		if(b & 1) ans = a * ans % m;
		a = a * a % m;
		b >>= 1;
	}
	return ans;
}
	
int main()
{
    scanf("%d%d",&n,&Q);
    for (int i=1;i<=n;i++) size[i]=1;
    int f, t, type, x, y;
    ll ans;
    for(int i = 1; i < n; ++ i)
    {
        scanf("%d %d", &f, &t);
        link(f, t);
    }
    for (int i=1;i<=Q;i++)
    {
        scanf("%d", &type);
        switch(type)
        {
            case 1:
            	scanf("%d %d", &x, &y);
            	if(find(x, y) || x == y) puts("-1");
            	else link(x, y);
            	break;
            case 2:
            	scanf("%d %d", &x, &y);
            	if(! find(x, y) || x == y) puts("-1");
            	else
                {
                    splay(y);
                    push(y);
                    int fa = ch[y][0];
                    push(fa);
                    while(ch[fa][1]) //右子树
                    {
                        fa=ch[fa][1];
                        push(fa);
                    }
                    cut(y, fa);
                }
            	break;
            case 3:
            	scanf("%d", &x);
            	makeroot(x);
            	ans = size[x] == 1 ? 0 : 2ll * (size[x] - 1) * pow_mod(deg[x], MOD - 2) % MOD;
            	printf("%lld\n", ans);
            	break;
            default:
            	//assert(false);
            	break;
        }
    }
    return 0;
}

Problem G

给定一个序列 $A$ ，给定一个参数 $m$ 。

每一轮，你可以利用 $m$ 消耗 $A_i$ 的代价将 $A_i$ 置为 $0$ ，直到 $m$ 比最大数还要小，此轮结束。

每一轮你已经将 $t$ 个数置 $0$ ，询问 $t, m$ 。

线段树维护区间最小值，然后 $A_i$ 置为 $0$ 的时候需要将 $m$ 去减 $A_i$ 即可。

AC 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 100009;
const int maxm = 300009;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
int min_n[maxn << 2], ans_o[maxn], ans_r[maxn];
int n, m, q;
	
void pre(int l, int r, int p)
{
	if(l == r)
	{
		scanf("%d", &min_n[p]);
		return ;
	}
	int mid = midf(l, r);
	pre(l, mid, DXA(p));
	pre(mid + 1, r, DXB(p));
	min_n[p] = min(min_n[DXA(p)], min_n[DXB(p)]);
}
	
int l, b, lamp;
void update(int nl, int nr, int p)
{
	if(nl == nr)
	{
		min_n[p] = 1e9 + 9;
		return ;
	}
	int mid = midf(nl, nr);
	if(l <= mid) update(nl, mid, DXA(p));
	else update(mid + 1, nr, DXB(p));
	min_n[p] = min(min_n[DXA(p)], min_n[DXB(p)]);
}
	
int query(int nl, int nr, int p)
{
	if(nl == nr) 
	{
		lamp -= min_n[p];
		return nl;
	}
	int mid = midf(nl, nr);
	if(min_n[DXA(p)] <= lamp) return query(nl, mid, DXA(p));
	else return query(mid + 1, nr, DXB(p));
}
	
int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	scanf("%d %d", &n, &m);
	pre(1, n, 1);
	lamp = 0;
	int np = 0;
	scanf("%d", &q);
	for(int i = 1; i <= 100000; ++ i)
	{
		if(np < n) lamp += m;
		while(lamp >= min_n[1] && np < n)
		{
			l = query(1, n, 1);
			++ np;
			update(1, n, 1);
		}
		ans_o[i] = lamp;
		ans_r[i] = np;
	}
	while(q --)
	{
		scanf("%d", &m);
		printf("%d %d\n", ans_r[m], ans_o[m]);
	}
	return 0;
}

Problem I

了解了一种新的数据结构。。

题解在里面

2018 年网络赛小结（沈阳）

好难啊。。

Problem J

题意： 给出一颗以$1$为根的树, 初始的时候每个节点上的点权都是$0$, 树的结点个数为$n \leq 100000$, 接下来是$m \leq 100000$次操作, 每次操作要么是将所有深度为$L$的结点上的点权增加一个值, 要么是询问以$x$为根的子树上的所有节点的点权和。

思路：树状数组+分块。

因为要输出的是以$x$为根的子树的结点和，所以不难想到将树转成线性结构，然后用树状数组维护前缀和。

两种修改方式：

  • 单点修改；（如果这一层的结点太多，会退化为 $O(n \log n)$）
  • 做一个标记 s，表示某一深度的权值都加了一个值。

对应的两种查询方式：

  • 树状数组求和即可；
  • 求出当前子树每个深度的节点数量然后乘以修改的值的和。（如果树的深度太深，退化成一条链的时候复杂度 $O(n \log n)$ ）

这两种算法都不是最优的。怎么把它们结合起来呢？

考虑用分块的思想结合这两种方式，当某一深度的节点数小于$\sqrt n$时，直接暴力树状数组修改，当某一深度的节点数大于等于 $\sqrt n$ 时，记录下这一深度，然后用第二种方式修改，因为节点数大于等于 $\sqrt n$ 的深度不会超过 $\sqrt n$ 个，所以最坏时间复杂度是 $O(m \sqrt n \ \log n)$ 。

是一道原题。。Gym 100589A

AC 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
#include <bits/stdc++.h>
	
# define in __Chtholly__
# define out __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
# define x1 __Darkcat__
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 100009;
const int maxm = 300009;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
namespace BIT
{
	ll tree[maxn];
	int n;
	inline int lowbit(int x){return x & -x;}
	void BIT(int p){n = p;}
	void update(int x, ll p)
	{
		for(; x <= n; x += lowbit(x)) tree[x] += p;
	}
	ll query(int x)
	{
		ll ans = 0;
		for(; x; x -= lowbit(x)) ans += tree[x];
		return ans;
	}
}
	
vi G[maxn], flr[maxn], large;
int in[maxn], out[maxn];
	
int n, q, type;
int pl;
	
void dfs(int dep, int fa, int now)
{
	in[now] = ++ pl;
	flr[dep].push_back(in[now]); //统计这一层有多少个结点 
	for(int i = 0; i < G[now].size(); ++ i)
	{
		if(G[now][i] == fa) continue;
		dfs(dep + 1, now, G[now][i]);
	}
	out[now] = pl;
}
	
const int MAX_SIZE = (int) sqrt(1.0 * 100000);
ll sum[maxn];
	
int main()
{
	int l, r, f, t;
	ll val, ans;
	scanf("%d %d", &n, &q);
	for(int i = 1; i < n; ++ i)
	{
		scanf("%d %d", &l, &r);
		G[l].push_back(r);
		G[r].push_back(l);
	}
	dfs(0, -1, 1);
	BIT :: BIT(n);
	for(int i = 0; i <= n; ++ i)
		if(flr[i].size() > MAX_SIZE)
			large.push_back(i);
	while(q --)
	{
		scanf("%d", &type);
		switch(type)
		{
			case 1:
				scanf("%d %lld", &l, &val);
				if(flr[l].size() <= MAX_SIZE)
					for(int i = 0; i < flr[l].size(); ++ i)
						BIT :: update(flr[l][i], val); //更新到每个点 
				else sum[l] += val; //更新这一层的 
				break;
			case 2:
				scanf("%d", &l);
				f = in[l], t = out[l];
				ans = BIT :: query(t) - BIT :: query(f - 1);
				for(int i = 0; i < large.size(); ++ i)
					ans += sum[large[i]] * (upper_bound(flr[large[i]].begin(), flr[large[i]].end(), t) - lower_bound(flr[large[i]].begin(), flr[large[i]].end(), f));
				printf("%lld\n", ans);
				break;
			default:
				assert(type == 1 || type == 2);
		}
	}
	return 0;
}

2018 年网络赛小结（徐州）

为什么我什么都不会啊。。正难则反的原理还是没有掌握清楚啊。。

Problem G

被降智打击。。

和队友正着算，算了四个小时。。

反着算直接就出来了。。

AC 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
	
using namespace std;
	
typedef long long ll;
typedef vector <long long> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 300009;
const int maxm = 300009;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
set <ll> xx, yy;
	
int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll ans = 0, xxm = 0, yym = 0, xxm2 = 0, yym2 = 0;
	int n;
	cin >> n;
	vi xd(n + 1), yd(n + 1);
	for(int i = 1; i <= n; ++ i)
	{
		cin >> xd[i] >> yd[i];
	}
	ans += xd[n] + yd[n];
	xx.insert(xd[n]), xx.insert(0), yy.insert(yd[n]), yy.insert(0);
	for(int i = n - 1; i >= 1; -- i)
	{
		xxm = * -- xx.lower_bound(xd[i]);
		yym = * -- yy.lower_bound(yd[i]);
		ans += xd[i] - xxm + yd[i] - yym;
		xx.insert(xd[i]);
		yy.insert(yd[i]);
	}
	cout << ans << endl;
	return 0;
}

Problem J

造一个最便宜的迷宫，每条边的花费给定。然后如何花费最少？形成留下边的最大生成树即可。

询问两个点之间的距离，在树上询问就好了。

这种题一般是写 LCA 的，由于不会 LCA ，于是就写个树剖好了。。

树剖竟然可以求树上两点之间的距离。。怎么求啊？先求出当前点 u 与 ffather[u] 之间的距离，一步步往上跳，直到两个点在一条链上。如果两个点其实是一个点就可以返回答案，否则就计算 u 和 v 之间的距离即可。

AC 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 500009;
const int maxm = 250009;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
struct eddy
{
	int to, next;
}edg_2[maxn];
int fir[maxm], eddy_tot;
int deep[maxm], ffather[maxm], son[maxm], size[maxm], head[maxm];
	
void addedge(int f, int t)
{
	edg_2[++ eddy_tot].to = t;
	edg_2[eddy_tot].next = fir[f];
	fir[f] = eddy_tot;
}
	
void dfs1(int u, int pre, int d)
{
	deep[u] = d;
	ffather[u] = pre;
	son[u] = 0;
	size[u] = 1;
	for(int i = fir[u]; i; i = edg_2[i].next)
	{
		if(edg_2[i].to != pre)
		{
			dfs1(edg_2[i].to, u, d + 1);
			size[u] += size[edg_2[i].to];
			if(! son[u] || size[edg_2[i].to] > size[son[u]])
				son[u] = edg_2[i].to;
		}
	}
}
	
void getpos(int u, int sp)
{
	head[u] = sp;
	if(son[u]) getpos(son[u], sp);
	for(int i = fir[u]; i; i = edg_2[i].next)
	{
		if(edg_2[i].to != son[u] && edg_2[i].to != ffather[u])
			getpos(edg_2[i].to, edg_2[i].to); 
	}
}
	
int answer(int u, int v)
{
    int f1 = head[u], f2 = head[v], ans = 0;
    while(f1 != f2)
    {
        if(deep[f1] < deep[f2])
        {
            swap(f1, f2);
            swap(u, v);
        }
        ans += deep[u] - deep[f1] + 1;
        //deep[u] - deep[f1] 表示的是链长，+1 表示跳到上一条链 
        u = ffather[f1]; f1 = head[u];
    }
    if(u == v) return ans;
    if(deep[u] > deep[v]) swap(u, v);
    ans += deep[v] - deep[u];
    //求出两个点之间的距离 
    return ans;
}
	
int n, m;
struct node
{
	int from, to, cost;
	bool operator < (const node &b) const
	{
		return cost > b.cost;
	}
}edge[maxn];
int father[maxm];
	
int find(int x){return father[x] == x ? x : father[x] = find(father[x]);}
	
void Kruskal(int cnt)
{
	int p = n * m;
	for(int i = 1; i <= n * m; ++ i) father[i] = i;
	sort(edge + 1, edge + 1 + cnt);
	for(int i = 1; i <= cnt; ++ i)
	{
		if(find(edge[i].from) != find(edge[i].to))
		{
			addedge(edge[i].from, edge[i].to);
			addedge(edge[i].to, edge[i].from);
			edge[i].from = find(edge[i].from);
			edge[i].to = find(edge[i].to);
			father[edge[i].to] = edge[i].from;
			-- p;
		}
		if(p == 1) break;
	}
}
	
int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	char ch;
	int val, ss = 0;
	cin >> n >> m;
	for(int i = 1; i <= n; ++ i)
	{
		for(int j = 1; j <= m; ++ j)
		for(int k = 1; k <= 2; ++ k)
		{
			cin >> ch >> val;
			switch(ch)
			{
				case 'X':
					break;
				case 'D':
					++ ss;
					edge[ss].from = ((i - 1) * m) + j;
					edge[ss].to = i * m + j;
					edge[ss].cost = val;
					break;
				case 'R':
					++ ss;
					edge[ss].from = ((i - 1) * m) + j;
					edge[ss].to = ((i - 1) * m) + j + 1;
					edge[ss].cost = val;
					break;
				default:
					assert(ch == 'X' || ch == 'D' || ch == 'R');
			}
		}
	}
	Kruskal(ss);
	dfs1(1, 0, 1);
	getpos(1, 1);
	//for(int i = 1; i <= n * m; ++ i) cout << deep[i] << ' '; cout << endl;
	int q, x1, x2, y1, y2;
	cin >> q;
	while(q --)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		x1 = (x1 - 1) * m + y1;
		x2 = (x2 - 1) * m + y2;
		cout << answer(x1, x2) << '\n';
	}
	return 0;
}

2018 年网络赛小结（焦作）

线段树卡了。。思维还是不够活啊。

Problem E

区间加、区间乘、区间数取反、区间求 $\texttt{MOD} \ 2^{64}$

区间数取反可以转换：计原来的和为 $s$ ，加法标记为 $a = -1$，乘法标记为 $m = -1$ ，这个操作可以转换为 $sa + m$

队友告诉我：不是所有问题都能 $O(1)$ 可解的，即使是 $O(1)$ 可解的也是比较麻烦的，只要时间不强制让你 $O(1)$ 可解，能不 $O(1)$ 尽量不要 $O(1)$ 。

AC 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
#include <bits/stdc++.h>
#else
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#endif
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
using namespace std;
typedef unsigned long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
const int MOD = 1e9 + 7;
const int maxn = 300009;
const int maxm = 300009;
const double pi = acos(-1.0);
const double eps = 1e-6;
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
struct node
{
	ll sum, add, mul;
	//bool rev;
}tree[maxn];
void pushup(int p, int l, int r)
{
	tree[p].sum = tree[DXA(p)].sum + tree[DXB(p)].sum;
}
void pre(int l, int r, int p)
{
	tree[p].add = 0;
	tree[p].mul = 1;
	//tree[p].rev = false;
	tree[p].sum = 0;
	if(l == r)
	{
		return ;
	}
	int mid = midf(l, r);
	pre(l, mid, DXA(p));
	pre(mid + 1, r, DXB(p));
}
void pushdown(int p, int l, int r)
{
    if(tree[p].add == 0 && tree[p].mul == 1)return ;
    int mid = midf(l, r);
    tree[DXA(p)].add = (tree[DXA(p)].add * tree[p].mul + tree[p].add);
    tree[DXB(p)].add = (tree[DXB(p)].add * tree[p].mul + tree[p].add);
    tree[DXA(p)].mul = (tree[p].mul * tree[DXA(p)].mul);
    tree[DXB(p)].mul = (tree[p].mul * tree[DXB(p)].mul);
    tree[DXA(p)].sum = (tree[DXA(p)].sum * tree[p].mul + (mid - l + 1) * tree[p].add);
    tree[DXB(p)].sum = (tree[DXB(p)].sum * tree[p].mul + (r - mid) * tree[p].add);
    tree[p].add = 0;
    tree[p].mul = 1;
}
int l, r;
ll val;
void update_add(int nl, int nr, int p)
{
    if(l <= nl && nr <= r)
    {
        tree[p].add = (tree[p].add + val);
        tree[p].sum = ((nr - nl + 1) * val + tree[p].sum);
        return ;
    }
    pushdown(p, nl, nr);
    int mid = midf(nl, nr);
    if(l <= mid)update_add(nl, mid, DXA(p));
    if(mid < r) update_add(mid + 1, nr, DXB(p));
    pushup(p, nl, nr);
}
void update_mul(int nl, int nr, int p)
{
    if(l <= nl && nr <= r)
    {
        tree[p].mul = (tree[p].mul * val);
        tree[p].add = (tree[p].add * val);
        tree[p].sum = (tree[p].sum * val);
        return ;
    }
    pushdown(p, nl, nr);
    int mid = midf(nl, nr);
    if(l <= mid)update_mul(nl, mid, DXA(p));
    if(mid < r) update_mul(mid + 1, nr, DXB(p));
    pushup(p, nl, nr);
}
ll query(int nl, int nr, int p)
{
	if(l <= nl && nr <= r) return tree[p].sum;
	pushdown(p, nl, nr);
	int mid = midf(nl, nr);
	ll ans = 0;
	if(l <= mid) ans += query(nl, mid, DXA(p));
	if(mid < r)  ans += query(mid + 1, nr, DXB(p));
	return ans;
}
int n, m, type;
int v[maxm], prevv[maxm];
int info[maxn], deep[maxn], size[maxn];
int father[maxn], head[maxn], len[maxn], son[maxn], id[maxn], pid[maxn];
bool vis[maxn];
int ans, cnt;
int N, nedge;
struct edg
{
	int f, t, cost;
}edge[maxn];
inline void insert(int x, int y)
{
	++ nedge;
	v[nedge] = y;
	prevv[nedge] = info[x];
	info[x] = nedge;
}
void dfs1(int u, int pre, int d)
{
	deep[u] = d;
	father[u] = pre;
	son[u] = 0;
	size[u] = 1;
	for(int i = info[u]; i; i = prevv[i])
	{
		if(v[i] != pre)
		{
			dfs1(v[i], u, d + 1);
			size[u] += size[v[i]];
			if(! son[u] || size[v[i]] > size[son[u]])
				son[u] = v[i];
		}
	}
}
void getpos(int u, int sp)
{
	head[u] = sp;
	id[u] = ++ cnt;
    pid[id[u]] = cnt;
	if(son[u]) getpos(son[u], sp);
	for(int i = info[u]; i; i = prevv[i])
	{
		if(v[i] != son[u] && v[i] != father[u])
			getpos(v[i], v[i]); 
	}
}
void init()
{
    RESET(info);
    RESET(prevv);
    RESET_(deep, -1);
    RESET(size);
    RESET(father);
    RESET(head);
    RESET(len);
    RESET(son);
    RESET(id);
    RESET(pid);
    RESET(v);
    cnt = 0;
    nedge = 0;
}
void __add__(int u, int v)
{
    int f1 = head[u], f2 = head[v];
    while(f1 != f2)
    {
        if(deep[f1] < deep[f2])
        {
            swap(f1,f2);
            swap(u,v);
        }
        //operation(id[f1], id[u]);
        l = id[f1], r = id[u];
        update_add(1, n, 1);
        u = father[f1]; f1 = head[u];
    }
    if(deep[u] > deep[v]) swap(u, v);
    l = id[u], r = id[v];
    //operation(id[u], id[v]);
    update_add(1, n, 1);
}
void __mul__(int u, int v)
{
    int f1 = head[u], f2 = head[v];
    while(f1 != f2)
    {
        if(deep[f1] < deep[f2])
        {
            swap(f1,f2);
            swap(u,v);
        }
        //operation(id[f1], id[u]);
        l = id[f1], r = id[u];
        update_mul(1, n, 1);
        u = father[f1]; f1 = head[u];
    }
    if(deep[u] > deep[v]) swap(u, v);
    //operation(id[u], id[v]);
    l = id[u], r = id[v];
    update_mul(1, n, 1);
}
ll __query__(int u, int v)
{
    int f1 = head[u], f2 = head[v];
    ll ans = 0;
    while(f1 != f2)
    {
        if(deep[f1] < deep[f2])
        {
            swap(f1,f2);
            swap(u,v);
        }
        //ans += operation(id[f1], id[u]);
        l = id[f1], r = id[u];
        ans += query(1, n, 1);
        u = father[f1]; f1 = head[u];
    }
    if(deep[u] > deep[v]) swap(u, v);
    l = id[u], r = id[v];
    ans += query(1, n, 1);
    return ans;
}
int main()
{
	int f, t;
	while(~ scanf("%d", &n))
	{
		init();
		pre(1, n, 1);
		for(int i = 2; i <= n; ++ i)
		{
			scanf("%d", &r);
			insert(i, r);
			insert(r, i);
		}
		dfs1(1, -1, 0);
		getpos(1, 1);
		scanf("%d", &m);
		while(m --)
		{
			scanf("%d", &type);
			switch(type)
			{
				case 1:
					scanf("%d %d %llu", &l, &r, &val);
					//update_mul(l, r, 1, n, val, 1);
					__mul__(l, r);
					break;
				case 2:
					scanf("%d %d %llu", &l, &r, &val);
					//update_add(l, r, 1, n, val, 1);
					__add__(l, r);
					break;
				case 3:
					scanf("%d %d", &f, &t);
					//update_rev(l, r, 1, n, 1);
					//update_mul(l, r, 1, n, -1, 1);
					//update_add(l, r, 1, n, -1, 1);
					val = -1;
					__mul__(f, t);
					__add__(f, t);
					break;
				case 4:
					scanf("%d %d", &l, &r);
					printf("%llu\n", __query__(l, r));
					break;
				default:
					break;
			}
			//for(int p = 1; p <= 10; ++ p) cout << "ADD = " << tree[p].add << ", MUL = " << tree[p].mul << ", SUM = " << tree[p].sum << endl;
		}
	}
	return 0;
}
/*
7
1 1 1 2 2 4
5
2 5 6 1
1 1 6 2
4 5 6
3 5 2
4 2 2
2
1
4
3 1 2
4 1 2
3 1 1
4 1 1
*/

Problem J

判断 $n, \frac {n (n - 1)} {2}$ 两个数是不是完全平方数

有人拆位过的，有人 Newton 迭代法过的

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
import java.math.*;
import java.util.*;
public class Main {
	public static void main(String args[])
	{  
        Scanner cin=new Scanner(System.in);
        int T=cin.nextInt();
        for(int i=0;i<T;i++)
        {
        	BigInteger n=cin.nextBigInteger();
        	BigInteger x=cal(n);
        	BigInteger y=n.multiply(n.subtract(BigInteger.valueOf(1))).divide(BigInteger.valueOf(2));
        	BigInteger z=cal(y);
        	if(x.multiply(x).equals(n)==true)
        	{
        		if(z.multiply(z).equals(y)==true)
        			System.out.println("Arena of Valor");
        		else
        			System.out.println("Hearth Stone");
        	}
        	else
        	{
        		if(z.multiply(z).equals(y)==true)
        			System.out.println("Clash Royale");
        		else
        			System.out.println("League of Legends");
        	}
        	
        }
	}
	static BigInteger cal(BigInteger x) //Newton 迭代法求 sqrt(x)
	{
		BigInteger ans=BigInteger.valueOf(0);
		if(x.equals(BigInteger.valueOf(0))==true)return ans;
		BigInteger rt=BigInteger.valueOf(1);
		BigInteger lst=BigInteger.valueOf(-1);
		while(true)
		{
			BigInteger nxt=rt.add(x.divide(rt)).shiftRight(1);
			if(nxt.equals(lst)==true)
			{
				if(lst.compareTo(rt)==-1)
					return lst;
				else return rt;
			}
			lst=rt;
			rt=nxt;
		}
    }
}

未解决的问题

2018 年网络赛小结（南京）

Problem F

需要看看 LCT 维护子树。。

2018 年网络赛小结（沈阳）

Problem B

应该是个表达式匹配吧。。

Problem J

分块了解一下

2018 年网络赛小结（徐州）

Problem B

记忆化搜索了解一下，然后，为什么可以搞记忆化搜索？

本文标题:2018 年网络赛小结

文章作者:Babydragon

发布时间:2018-09-09, 22:00:00

最后更新:2018-09-15, 23:34:13

原始链接:http://baolintian.github.io/2018/09/09/2018-年网络赛小结/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2018 年网络赛小结（南京）
    1. 1.1. Problem F
      1. 1.1.1. AC Code
    2. 1.2. Problem G
      1. 1.2.1. AC Code
    3. 1.3. Problem I
  2. 2. 2018 年网络赛小结（沈阳）
    1. 2.1. Problem J
      1. 2.1.1. AC Code
  3. 3. 2018 年网络赛小结（徐州）
    1. 3.1. Problem G
      1. 3.1.1. AC Code
    2. 3.2. Problem J
      1. 3.2.1. AC Code
  4. 4. 2018 年网络赛小结（焦作）
    1. 4.1. Problem E
      1. 4.1.1. AC Code
    2. 4.2. Problem J
  5. 5. 未解决的问题
    1. 5.1. 2018 年网络赛小结（南京）
      1. 5.1.1. Problem F
    2. 5.2. 2018 年网络赛小结（沈阳）
      1. 5.2.1. Problem B
      2. 5.2.2. Problem J
    3. 5.3. 2018 年网络赛小结（徐州）
      1. 5.3.1. Problem B
{{ live2d() }}