A Tokitsukaze and Bracelet

考点：分类
条件判断即可，签到题

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int t;cin >> t;
	while(t --)
    {
		int res = 0;
		int a,b,c;
		cin >> a >> b >> c;
		if(a >= 150) res ++;
		if(a >= 200) res ++;
		if(b >= 34) res ++;
		if(b >= 45) res ++;
		if(c >= 34) res ++;
		if(c >= 45) res ++;
		cout << res << '\n';
	}
    return 0;
}

F Tokitsukaze and Eliminate (hard)

考点：贪心，STL，线段树
这是线段树解法

#include <bits/stdc++.h>
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
using i64 = long long;
const int N = 200005;
const i64 INF = 0x3f3f3f3f;
vector<int> a[N], arr(N), sum(4*N, 0);
void update(int x) 
{
    sum[x] = min(sum[ls], sum[rs]);
}

void build(int l, int r, int x) 
{
    if(l == r) 
    {
        sum[x] = (a[l].empty() ? INF : a[l].back()); 
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid+1, r, rs);
    update(x);
}

int query(int A, int B, int l, int r, int x) 
{
    if(A > B) return INF; 
    if(A <= l && B >= r) return sum[x];
    int mid = (l + r) >> 1, ans = INF;
    if(A <= mid) ans = min(ans, query(A, B, l, mid, ls));
    if(B > mid) ans = min(ans, query(A, B, mid+1, r, rs));
    return ans;
}

void change(int pos, int v, int l, int r, int x) 
{
    if(l == r) 
    {
        sum[x] = v; 
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) change(pos, v, l, mid, ls);
    else change(pos, v, mid+1, r, rs);
    update(x);
}

void solve() {
    int n; cin >> n;
    for(int i = 1; i <= n; ++i) a[i].clear();
    for(int i = 1; i <= n; ++i) 
    {
        cin >> arr[i];
        a[arr[i]].push_back(i);
    }
    build(1, n, 1);
    int res = 0;
    int r = n;
    while(r) 
    {
        int new_r = query(1, n, 1, n, 1); 
        res += 1;
        for(int k = r; k >= new_r; --k) 
        {
                a[arr[k]].pop_back();
                if (a[arr[k]].empty())
                    change(arr[k], INF, 1, n, 1);
                else
                    change(arr[k], a[arr[k]].back(), 1, n, 1);
        }
        r = new_r - 1; 
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}