data structure

这次总的来说有些懵逼，不知道系统，做出来的也有很大一部分乱搞的成分，赛后补题学到很多。

  • erase为O(n)的复杂度。
  • 根据一个条件排序后，二分查找满足另一个条件。
  • 区间过渡
  • 莫队算法
  • 差分
  • 线段树，树状数组

 

A. Cells Not Under Attack

 

 每次放棋子时，检查棋子所在的行和列是否已经有棋子，若没有，则将未受威胁的格子总数减去（行数+列数-1），若行或列上已经有棋子，则只减去行数或列数，分类讨论即可。

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
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
vector<int>x;
vector<int>y;
bool inx(int xi) {
	return binary_search(x.begin(), x.end(), xi);
}
bool iny(int yi) {
	return binary_search(y.begin(), y.end(), yi);
}
bool usedx[maxn];
bool usedy[maxn];
int numx, numy;
int main() {
	ll n, m;
	cin >> n >> m;
	long long T = n*n;
	for (int i = 0; i < m; i++) {
		int xi, yi;
		ll to_minus = 0;
		cin >> yi >> xi;
		if (T == 0) {
			cout << 0<<' ';
			continue;
		}
		if ((!usedx[xi]) && (!usedy[yi])) {
			to_minus = n + n - 1 - numx - numy;
			numx++;
			numy++;
			usedx[xi] = 1;
			usedy[yi] = 1;
		}
		else if ((!usedx[xi]) && usedy[yi]) {
			to_minus = n - numy;
			numx++;
			usedx[xi] = 1;
		}
		else if (usedx[xi] && (!usedy[yi])) {
			to_minus = n - numx;
			numy++;
			usedy[yi] = 1;
		}
		else if (usedx[xi] && usedy[yi])
			to_minus = 0;
		T -= to_minus;
		if (T < 0)
			T = 0;
		cout << T << ' ';
		//getchar();
	}
	//getchar();
	return 0;
}

 

B. Too Easy Problems

 

 由于本题只需要输出满足条件的一种答案，所以假设做的题目数等于最终得分数，即只做能得分的题目。

 将所有题目按照耗时从小到大排序，对要做的题目数二分查找，确定最终要做多少题目，确定题数之后，从头到尾确定做哪些题目，由于题目耗时从小到大排序，所以最后答案一定是最优。

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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 5;
int T, n, st, ed, times, cnt;
struct Node
{
	int most, time, index;
}nd[maxn];
bool cmp(Node a, Node b) {
	return a.time < b.time;
}
int main() {
	ios::sync_with_stdio(false);
	scanf("%d%d", &n, &T);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &nd[i].most, &nd[i].time);
		nd[i].index = i;
	}
	sort(nd + 1, nd + n + 1, cmp);
	st = 0, ed = n;
	while (st < ed) {
		int md = (ed + st + 1) >> 1;
		cnt = 0, times = 0;
		for (int i = 1; i <= n; i++) {
			if (nd[i].most >= md) {
				if (times + nd[i].time <= T) {
					times += nd[i].time, cnt++;
				}
				else break;
			}
		}
		if (cnt >= md) {
			st = md;
		}
		else ed = md - 1;
	}
	printf("%d\n%d\n", st, st);
	cnt = 0;
	for (int i = 1; i <= n&&cnt < st; i++) {
		if (nd[i].most >= st) { printf("%d ",nd[i].index); cnt++; }
	}
	return 0;
}

 

C. Minimum Array

 

 先利用lower_bound找到大于等于n−ain-a_i的数，并erase掉。

若未找到，则从头开始找到第一个不为0的数。指向开头的指针+1。

当所有元素b中都相等时，erase耗时太大，所以要选第一个。

注意先输出，再erase，否则会越界！！

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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int a[maxn];
vector<int>vc;
int main() {
	std::ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int st = 0;
	for (int i = 0; i < n; i++) {
		int tp;
		cin >> tp;
		vc.push_back(tp);
	}
	sort(vc.begin(), vc.end());
	for (int i = 0; i < n; i++) {
		int best = n - a[i];
		int pos = lower_bound(vc.begin() + st, vc.end(), best) - vc.begin();
		if (pos == vc.size() || vc[pos] == vc[0]) {	//针对所有数都相等的情况
			cout << (vc[st] + a[i]) % n<<' ';
			st++;
			continue;
		}
		if ((a[i] + vc[st] % n) < (vc[pos] + a[i]) % n) {
			cout << (a[i] + vc[st]) % n << ' ';
			st++;
		}
		else {
			cout << (a[i] + vc[pos]) % n << ' ';
			vc.erase(vc.begin() + pos);
		}
	}
	return 0;
}

 

D. Powerful array

 

 裸的普通莫队

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
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
const int maxn = 2e5 + 50;
int n, t;
int a[maxn];
int unit;
ll ans;
int cnt[1000005];
ll res[maxn];
struct Node
{
	int st, ed;
	int idt;
}que[maxn];
bool cmp(Node a, Node b) {
	return (a.st / unit == b.st / unit) ? (a.ed < b.ed) : (a.st / unit < b.st / unit);
}
void add(int x) {
	ans += ((cnt[a[x]] << 1) + 1)*a[x];
	cnt[a[x]]++;
}
void del(int x) {
	ans -= ((cnt[a[x]] << 1) - 1)*a[x];
	cnt[a[x]]--;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> t;
	unit = sqrt(t);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= t; i++) {
		cin >> que[i].st >> que[i].ed;
		que[i].idt = i;
	}
	sort(que + 1, que + t + 1, cmp);
	int L = 0, R = 0;
	for (int i = 1; i <= t; i++) {
		while (L < que[i].st)del(L++);
		while (L > que[i].st)add(--L);
		while (R > que[i].ed)del(R--);
		while (R < que[i].ed)add(++R);
		res[que[i].idt] = ans;
	}
	for (int i = 1; i <= t; i++) {
		cout << res[i] << endl;
	}
	return 0;
}

 

E. Interesting Array

 

 线段树，差分

 先根据所有条件构造答案数组，再用答案数组比对每一个询问，若有不符合的，输出NO。

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
#include<iostream>
using namespace std;
#define lson l,mid,2*id
#define rson mid+1,r,2*id+1
const int maxn = 150000;
struct Node
{
	int l, r, val;
}que[maxn];
int INF ;
int tree[maxn*4];
int a[maxn];	//构造出的数组
int n, m;
int sum[32][maxn];
int tot[32];

void push_up(int id) {
	//向上更新，树上存区间所有元素&
	tree[id] = tree[2 * id] & tree[2 * id + 1];
}
void build(int l, int r, int id) {
	//叶子上存该点数字
	if (l == r) {
		tree[id] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lson);
	build(rson);
	push_up(id);//向上更新
}
int query(int L,int R,int l,int r,int id) {
	if (L <= l && R >= r) {
		return tree[id];
	}
	int ans = INF;
	int mid = (l+r) >> 1;
	if (L <= mid)ans&=query(L, R, lson);
	if (R > mid)ans&=query(L, R, rson);
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	for (int i = 0; i <= 30; i++)INF += (1 << i);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int L, R, val;
		cin >> L >> R >> val;
		que[i].l = L; que[i].r = R, que[i].val = val;
		for (int j = 0; j <= 30; j++)
		{
			if ((val&((1 << j))) > 0)
			{	//差分数组
				sum[j][L]++;
				sum[j][R + 1]--;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		//tot存每个二进制位上是否为0
		//由于若不要求为1时，该位上可以为任意数，故不再设置tot数组为0
		int now = 0;
		for (int j = 0; j < 30; j++) {
			tot[j] += sum[j][i];
		}
		for (int j = 0; j < 30; j++) {
		//tot[j]>0说明有条件要求改二进制位上有1
			if (tot[j] > 0)now += (1 << j);
		}
		a[i] = now;
	}
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int val = que[i].val;
		int L = que[i].l, R = que[i].r;
		if (query(L, R, 1, n, 1) != val) {//有一个条件不符合
			cout << "NO";
			return 0;
		}
	}
	cout << "YES" << endl;
	for (int i = 1; i <= n; i++) {
		cout << a[i] << ' ';
	}
	return 0;
}

 

H. Subsegments

 

 要求只出现了一次且最大的数，从第一个长度为k的区间开始，记录区间中每个元素的出现次数，过渡到下个区间只要考虑减去的数于新增的数的出现次数，使用set自动排序存一段区间中只出现了一次的数。

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<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
set<int>st;
map<int, int>mp;
int main() {
	int n,k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < k; i++) {
		mp[a[i]]++;
		if (mp[a[i]] == 1)st.insert(a[i]);
		else if (mp[a[i]] == 2)st.erase(a[i]);
	}
	if (st.size() != 0)cout << *(--st.end()) << endl;
	else cout << "Nothing" << endl;
	for (int i = k; i < n ; i++) {
		mp[a[i]]++;
		if (mp[a[i]] == 1)st.insert(a[i]);
		else if (mp[a[i]] == 2)st.erase(a[i]);
		mp[a[i - k]]--;
		if (mp[a[i - k]] == 1)st.insert(a[i - k]);
		else if (mp[a[i - k]] ==0)st.erase(a[i - k]);
		if (st.size() != 0)cout << *(--st.end()) << endl;
		else cout << "Nothing" << endl;
	}
	return 0;
}

 

I. Little Girl and Maximum Sum

 

 差分+前缀和， 记录每个位置的出现次数，排序，将原数组排序，次数多的配上数字大的。

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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 2e5 + 5;
#define ll long long
typedef pair<int, int> pii;
ll a[maxn];
vector<pii>vc;
ll times[maxn];
ll rt[maxn];
int main() {
	ll n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < q; i++) {
		int m, n;
		cin >> m >> n;
		times[m]++;
		times[n + 1]--;
	}
	for (int i = 1; i <= n; i++) {
		rt[i] = rt[i - 1] + times[i];
	}
	sort(a+1, a + n+1);
	sort(rt + 1, rt + n + 1);
	ll ans=0;
	for (int i = 1; i <=n; i++) {
		ans += a[i] * rt[i];
	}
	cout << ans;
	return 0;
}

 

K. Queries about less or equal elements

 

 离线询问，先排序，对a，b都要从小到大排序，对于每一次询问，缩小在a中的搜索范围。

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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 2 * 1e5 + 5;
typedef pair<int, int> pii;
vector<int>a;
vector<pii>b;
int cnt[maxn];
bool cmp(pii a,pii b){
	return a.first < b.first;
}
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		int tp;
		cin >> tp;
		a.push_back(tp);
	}
	for (int i = 0; i < n; i++) {
		int tp;
		cin >> tp;
		b.push_back(pii(tp, i));
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end(), cmp);
	int st = 0;
	for (int i = 0; i < n; i++){
		int ans = upper_bound(a.begin() + st, a.end(), b[i].first) - a.begin();
		cnt[b[i].second] = ans;
		st=ans;
	}
	for (int i = 0; i < n; i++) {
		cout << cnt[i] << ' ';
	}
	return 0;
}