题面：

有点可惜要是先看的A题说不定就过金牌线了。

L Beef Tripe in Soup Pot?

阅读理解题，我和另一个队友当时没看到有中文题面看了半天，就是在说有n种物品，每个有四个信息，第一个和第二个信息表示第一和第二个种类对应的值表示代价，第三个和第四个是这种物品的是属于第一种类还是第二种类。问你个每个物品划分完之后的最小代价。
就是排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
	int n;
    vector<int> a,p1,p2;
	cin>>n;
	for(int i = 0,x,y,u,v;i<n;++i){
		cin>>x>>y>>u>>v;
		if(u && v){
			if(x > y) a.push_back(y),p2.push_back(i);
			else a.push_back(x),p1.push_back(i);
		}else{
			if(u) a.push_back(x),p1.push_back(i);
			else a.push_back(y),p2.push_back(i);
		}
	}
	sort(all(p1),[&](int x,int y){return a[x] < a[y];});
	sort(all(p2),[&](int x,int y){return a[x] < a[y];});
	cout<<si(p1)<<' ';
	for(auto i : p1) cout<<i+1<<" \n"[i == p1.back()];
	cout<<si(p2)<<' ';	
	for(auto i : p2) cout<<i+1<<" \n"[i == p2.back()];	
}

H GG and YY’s Stone Game

一道很简单的博弈论，甚至在我小学就听说过。
先考虑谁是获胜者。必胜态：当前只剩下一个或者两个。进而推出必败态：当前还剩三个，因为不管拿多少都拿不完，下家一定能全部拿走。接着推广：剩四个，因为可以拿一个或者两个，拿两个的时候剩两个，下家必赢，这样拿此时的玩家是输的，拿一个的时候剩三个，下家必输，这样拿此时的玩家是赢的，因为存在必胜态，或者说此时的玩家可以把结果引导到下家的必败态，所以剩四个的时候此时的玩家必赢，同理剩五个此时的玩家也是必赢的，剩六个可以发现不管怎么拿下家都是必胜态，所以剩六个此时的玩家必败……所以当n%3 == 0，先手必败，否则必胜。
同样的推理可以知道拿石子的数量的关系：
当先手是必败的，即n%3 == 0先手为了尽可能的多拿，肯定要拿两个，而后手为了保证下一步是对手必败，只能拿一个，因为这样的话能保证轮到对手的时候n%3 == 0恒成立，所以此时赢家（即后手）最多拿n/3个。
当先手是必胜的，也是一样的，第一步先拿n%3的部分，这样n%3 == 0始终是对手的。而自己就成了先手必败的时候后手的状态，每次都要拿一个，所以总共是n%3 + n/3个。
代码就不放了没什么要写的。

E L-Covering Checker

模拟题队伍里有是模拟仙人在我题还没看懂就写完了。
代码是队友的。

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
void solve() {
	int n, m;
	cin >> n >> m;
	string s[n + 1];
	for (int i = 1; i <= n; ++i)cin >> s[i], s[i] = "0" + s[i];
	int dot = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (s[i][j] == '.')dot++;
	if (dot == 1 and s[1][m] == '.') {
		bool a[n + 1][m + 1];
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				a[i][j] = false;

		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				if (s[i][j] == 'C') {
					a[i][j] = true;
					int num = 0;
					if (i - 1 >= 1 and s[i - 1][j] == 'D')
						a[i - 1][j] = true, num++;
					if (j - 1 >= 1 and s[i][j - 1] == 'R')
						a[i][j - 1] = true, num++;

					if (j + 1 <= m and s[i][j + 1] == 'L')
						a[i][j + 1] = true, num++;

					if (i + 1 <= n and s[i + 1][j] == 'U')
						a[i + 1][j] = true, num++;
					if (num != 2)
						return cout << "No" << endl, void();
				}
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				if (s[i][j] != '.')
					if (a[i][j] == false)
						return cout << "No" << endl, void();
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

给你能力值为 1 到 5 的精灵的数量，问你最多能连接召唤出多 少能力值为 6 的精灵，注意这道题的召唤规则：选 k 只精灵出来，每个能力值为 x 的精灵当做x或者1，不是所有小于等于x的数。求和为 s, 并得到能力值为 s 的精灵一只。
直接贪心模拟就行。写起来比较复杂，先考虑2只就能合成6的，这个只有可能是能力5的精灵和其他能力的精灵，然后考虑能力是4的精灵和其他小于4的任选两只。注意能力值小于等于3的精灵，变成1和别的凑和直接(a[1] * 1 + a[2] * 2 + a[3] * 3)/6是一样的，因为考虑什么时候有剩余：对于3而言，肯定是自己两两一组最划算，否则和1 2的和至少要三个一组。对于2而言，和1组合至少要4个这一组，不如直接自己先组合。这样就剩了这些可能：3只能剩一个，在3剩余的情况下，合法的1和2的组合有(0,2),(3,0)，因为直接累加能多的只有是多一个2的贡献，也就是说直接加得到的是比变成1要多1；当3一个不剩的时候，剩下的各种情况都是直接凑是最优的，可以发现直接累加后多出来的部分不影响结果，所以上面的式子是正确的。
看出这个式子写起来会简单些。

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
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll t,a[6],m;
int main(){
    cin>>t;
    while (t--){
        int sum=0;
        for (int i=1;i<=5;++i)cin>>a[i];
        for (int i=1;i<=2;++i){
            m=min(a[i],a[6-i]);
            sum+=m,a[i]-=m,a[6-i]-=m;
        }
        sum+=a[3]/2;
        a[3]%=2;
        if(a[5]>0){
            m=min(a[5],a[2]+a[3]+a[4]);
            sum+=m;
            a[5]-=m;
            if(a[2]>m)a[2]-=m;
            else {
                m-=a[2],a[2]=0;
                if(a[3]>m)a[3]-=m;
                else{
                    m-=a[3],a[3]=0;
                    if(a[4]>m)a[4]-=m;
                    else m-=a[4],a[4]=0;
                }
            }
            if(a[5]>0){
                sum+=a[5]/2;
                a[5]%=2;
                a[1]+=a[5];
                a[5]=0;
            }
        }
        if(a[4]>0){
            m=min(a[4],(a[1]+a[3])/2);
            sum+=m;
            a[4]-=m;
            m*=2;
            if(a[1]>m)a[1]-=m;
            else {
                m-=a[1],a[1]=0;
                if(a[3]>m)a[3]-=m;
                else m-=a[3],a[3]=0;
            }
            if(a[4]>0){
                sum+=a[4]/3;
                a[4]%=3;
                if(a[4]==2){
                    a[1]++,a[4]--;
                    m=min(a[4],(a[1]+a[3])/2);
                    sum+=m;
                    a[4]-=m;
                    m*=2;
                    if(a[1]>m)a[1]-=m;
                    else {
                        m-=a[1],a[1]=0;
                        if(a[3]>m)a[3]-=m;
                        else m-=a[3],a[3]=0;
                    }

                }
                if(a[4]>0)a[1]++,a[4]=0;
            }
        }
        sum += (a[1] * 1 + a[2] * 2 + a[3] * 3)/6;
        cout<<sum<<endl;
    }
    return 0;
}

*F Isoball: 2D Version

队友没调出来

*I Container Scheduling

大模拟懒得看

A Reverse Pairs Coloring

单杀的题，一眼扫描线。
观察第一个样例（5 9 1 8 2 6 4 7 3），可以发现每一行拆开来看的话长这样：
第一步 ：5，后面有1,2,3,4，涂色：

第二步：9，后面有1,2,3,4，6,7,8，涂色：

第三步：1，后面小于它的没有。

第四步：8，后面有2,3,4，6,7，涂色：

按照行来看，把二维的面积压成一条数轴，则前面4步数轴上的值可以表示为：
1:[1,1,1,1,0,0,0,0,0]，产生了1个块
2:[1,1,1,1,0,1,1,1,0]，多产生了1个块
3:[1,1,1,1,0,1,1,1,0]，多产生了0个块
4:[1,1,1,1,0,1,1,1,0]，多产生了2个块
可以发现第i行对于第i-1行而言，能够多出来的数只有是这个位置的前面闭上一行的多出来的连续1的 段数。
所以统计每一行从序号0开始到$a_i-1$为止连续1的段数，记为$p_i$,每行对答案的贡献为$max(0,p_i - p_{i-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
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
#include <bits/stdc++.h>
//#define endl '\n'
#define int long long
//#define N 103
#define fi first
#define se second
#define si(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug cout<<"*******\n";
using namespace std;

typedef pair<int, int> PII;

template<class Info>
struct SegmentTree {
	int n;
	std::vector<Info> info;
	SegmentTree() : n(0) {}
	SegmentTree(int n_, Info v_ = Info()) {
		init(n_, v_);
	}
	template<class T>
	SegmentTree(std::vector<T> init_) {
		init(init_);
	}
	void init(int n_, Info v_ = Info()) {
		init(std::vector(n_, v_));
	}
	template<class T>
	void init(std::vector<T> init_) {
		n = init_.size();
		info.assign(4 << std::__lg(n), Info());
		std::function<void(int, int, int)> build = [&](int p, int l, int r) {
			if (r - l == 1) {
				info[p] = init_[l];
				return;
			}
			int m = (l + r) / 2;
			build(2 * p, l, m);
			build(2 * p + 1, m, r);
			pull(p);
		};
		build(1, 0, n);
	}
	void pull(int p) {
		info[p] = info[2 * p] + info[2 * p + 1];
	}
	void modify(int p, int l, int r, int x, const Info &v) {
		if (r - l == 1) {
			info[p] = v;
			return;
		}
		int m = (l + r) / 2;
		if (x < m) {
			modify(2 * p, l, m, x, v);
		} else {
			modify(2 * p + 1, m, r, x, v);
		}
		pull(p);
	}
	void modify(int p, const Info &v) {
		modify(1, 0, n, p, v);
	}
	Info rangeQuery(int p, int l, int r, int x, int y) {
		if (l >= y || r <= x) {
			return Info();
		}
		if (l >= x && r <= y) {
			return info[p];
		}
		int m = (l + r) / 2;
		return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
	}
	Info rangeQuery(int l, int r) {
		return rangeQuery(1, 0, n, l, r);
	}
};

struct Info {
	int l = 1;
	int r = 1;
	int cnt = 0;
};

Info operator+(Info a, Info b) {
	if (a.r == 0 && b.l == 0) {
		a.cnt += b.cnt - 1;
		a.r = b.r;
	} else {
		a.cnt += b.cnt;
		a.r = b.r;
	}
	return a;
}

void solve() {
	int n;
	cin >> n;
	vector<Info> init(n);
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		init[i].l = 0, init[i].r = 0, init[i].cnt = 1;
	}
	SegmentTree<Info> seg(init);
	int cnt = 0,pre = 0;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int p = a[i];
		p--;
		seg.modify(p, {1, 1, 0});
		Info info = seg.rangeQuery(0, p);
		cnt = info.cnt;
		ans += max(cnt - pre,0ll);
		pre = cnt;
	}
	if (cnt) ans += cnt;
	cout << ans << endl;
}

signed main() {
//	freopen("in.txt", "r", stdin);
	cin.tie(nullptr), cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;
	int T = 1;
//	cin >> T;
	while (T--) solve();
	return 0;
}