APIO 2024 VP 记

# APIO 2024 VP 记
PS：时间线按照在机房的时间线走

## Day 1 5.25
zty 回来了，之前都是别的老师代课，有一个是清华的博士生，嫌我们太弱了，对于我们机房其他三位他不屑于一看，然后他评价我们竞赛月测的时候对我的评价是：“基础不错，那你今天应该可以听懂”。

zty 讲课还是一如既往地讲算法竞赛进阶指南，很舒服，刨去 dp 优化和计数类 dp 都讲的差不多了。

然后注意到 APIO 出分了，非常急的去看 HE 的诸位考的怎么样。

看到 ReTF 115 Cu 和 APJ 115 Cu 当场蚌埠住了，还有 耳朵龙 好像也寄掉了。然后我就去采访了一下 ReTF。

ReTF：“T1 通过率 97%，T2 部分分极其充足，T3 出的非常新颖”

PassName：“用一句话评价一下”

ReTF：“史”

由于没有拿到题，我一个场外选手也不好评价，继续找题去做了

## Day 2 5.30
经典阅读课不看红楼梦来机房。

打开题库发现 APIO 的题有了，于是决定写一手，卡了一下时间。

拿到 T1 当时就去考虑贪心，但是直接贪心我想不出来什么东西，所以考虑一些性质。对于每一位观察者，第 $i$ 个记录的叶子位置一定不低于第 $i-1$ 个记录的叶子位置，所以可以连边。然后如果能不等式连成一串，即这一层构成合法。建完图之后，强联通分量即合法，所以只需要统计强联通分量的个数即可。

```cpp
#include <bits/stdc++.h>

#define rint register int

using namespace std;

const int N = 1e5 + 5;
const int M = 1e6 + 5;

int h[N], e[M], ne[M], idx;
int dfn[N], low[N];
bool ins[N];
int stk[N], c[N];
vector<int> scc[N];
int num, cnt, top;

void add(int a, int b)
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

void tarjan(int x)
{
	dfn[x] = low[x] = ++num;
	stk[++top] = x, ins[x] = 1;
	for (rint i = h[x]; i; i = ne[i])
	{
		int y = e[i];
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (ins[y])
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x])
	{
		cnt++;
		int y;
		do 
		{
			y = stk[top--];
			ins[y] = 0;
			c[y] = cnt;
			scc[cnt].push_back(y);
		} while (x != y);
	}
}

int solve(int n, int m, vector<int> f, vector<vector<int>> s) 
{
    idx = num = cnt = top = 0;
    memset(h, 0, sizeof h);
    memset(dfn, 0, sizeof dfn);
    for (rint i = 0; i < m; i++) 
        for (rint j = 0; j < n - 1; j++) 
            if (j > 0)
			    add(s[i][j], s[i][j - 1]);
            
    for (rint i = 0; i < n; i++) add(f[i], i);
    
    for (rint i = 1; i < n; i++) 
        if (!dfn[i]) 
		    tarjan(i);
    
    return cnt;
}
```

开 T2 后迅速想到了 dp，$f_i$ 表示经过边 $i$ 到达点 $y_i$ 的最少代价。$f_i=C_i+\min_{{}x_i=y_j,b_j\le a_i}\{f_j+t_{x_i}\times  cost(b_j+1,a_i-1)\}$。显然需要优化。对于我这种低分选手，就会那么几种优化方式。斜率优化显然不可做，考虑四边形不等式，发现 $cost(i,j)$ 满足四边形不等式，但是维护的时候我并不会，所以写了暴力就弃掉了。T3 通信题更是没见过，写了 5pts 暴力滚蛋。

哈哈，到最后我不过也是个垫底 Cu 水平罢了。

但是 T1 只用了 20min 就过掉了， T3 暴力就打了 10min，T2 也就写了个暴力，时间还久，T2 就去考虑其他做法了，后来发现这个题好像不只是可以四边形不等式，存在其他做法。有一种比较暴力的想法，用线段树维护贡献再用分块维护决策，貌似可做？但是复杂度是 log + sqrt 的，赌一把，洛谷神机能过。于是就开始 rush 了。1.5h 后写出来了，交了一发 5pts。nb，每个测试点都是绿中带一点红，应该是小问题，没 T 就好，还有拯救空间。最后发现线段树出问题了，小改一手过了。

```cpp
#include <bits/stdc++.h>

#define ll long long
#define rint register int

using namespace std;

const int N = 2e5 + 5;
const int M = 2e2 + 5;
const ll inf = 1e18;

vector<ll> v[M], h[N];
ll integrate[N], cnt, L[N], R[N];
vector<ll> A[N], B[N], q[N];

struct Segment_tree
{
	ll n;
	/*struct node
	{
		ll v;// v is minn
		ll lazy;
	}t[N << 2];*/
	#define ls p << 1
	#define rs p << 1 | 1
	ll *v;
	ll *lazy;
	void push_up(ll p)
	{
		v[p] = min(v[ls], v[rs]) + lazy[p];
	}
	void build(ll p, ll l, ll r)
	{
		if (l == r)
		{
			v[p] = inf;
			return ;
		}
		ll mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		push_up(p);
	}
	void change_1(ll p, ll l, ll r, ll x, ll y, ll d)
	{
	    if (x <= l && r <= y) 
		{
	        v[p] += d;
	        lazy[p] += d;
	        return ;
	    }	
	    ll mid = (l + r) >> 1;
	    if (x <= mid) 
	        change_1(ls, l, mid, x, y, d);
	    if (y > mid)
	        change_1(rs, mid + 1, r, x, y, d);
	    push_up(p);
	}
	void change_2(ll p, ll l, ll r, ll x, ll y)
    {
		if (l == r)
		{
			v[p] = y;
			return ;
		}
		ll mid = (l + r) >> 1;
		y -= lazy[p];
		if (x <= mid)
		    change_2(ls, l, mid, x, y);
		else 
		    change_2(rs, mid + 1, r, x, y);
		push_up(p);
	}
	void new_build(ll x)
	{
		n = x;
        v = new ll[4 * x + 5];
        lazy = new ll[4 * x + 5];
		//t = new node[4 * x + 5];
		build(1, 1, n);
	}
	#undef ls
	#undef rs
}tr[M];

ll ans[N], color[N], pos[N];
ll num, g[N], s;
vector<ll> id[N];
ll final_ans = inf;

#define eb emplace_back
#define up upper_bound
#define lb lower_bound

struct tag_block 
{
    ll tag[N], add[N];
    void change(ll x, ll y) 
	{
        ll blk = (x - 1) / s;
        for (rint i = 0; i < blk; i++) tag[i] += y;
        for (rint i = blk * s + 1; i <= x; i++) add[i] += y;
    } 
	ll ask(ll x) 
	{
        return tag[(x - 1) / s] + add[x];
    }
} p;

ll solve(int n,int m,int w,vector<int>t,vector<int>x,vector<int>y,vector<int>a,vector<int>b,vector<int>c,vector<int>l,vector<int>r) 
{
    for (rint i = 0; i < m; i++)
    {
        integrate[++cnt] = a[i];
		integrate[++cnt] = b[i];		
	}
    sort(integrate + 1, integrate + cnt + 1);
    cnt = unique(integrate + 1, integrate + cnt + 1) - integrate - 1;
    for (rint i = 0; i < m; i++)
    {
        a[i] = lb(integrate + 1, integrate + cnt + 1, a[i]) - integrate;
		b[i] = lb(integrate + 1, integrate + cnt + 1, b[i]) - integrate;
        A[a[i]].push_back(i);
		B[b[i]].push_back(i);		
	}
    for (rint i = 0; i < w; i++)
    {
        l[i] = lb(integrate + 1, integrate + cnt + 1, l[i]) - integrate - 1;
		r[i] = up(integrate + 1, integrate + cnt + 1, r[i]) - integrate;
        q[r[i]].push_back(l[i]);
		L[r[i]]++;
		R[l[i]]++;		
	}

for (rint i = 1; i <= cnt; i++) L[i] += L[i - 1];
    for (rint i = cnt; i >= 1; i--) R[i] += R[i + 1];

for (rint i = 0; i < m; i++) 
	{
        if (!x[i]) ans[i] = L[a[i]] * t[0];
        else ans[i] = inf;
    }

for (rint i = 0; i < m; i++) h[y[i]].eb((int)i);

for (rint i = 0; i < n; i++) 
	{
        if (h[i].size() <= 2e3) continue;
        color[i] = ++num;
        pos[num] = i;
        sort(h[i].begin(), h[i].end(), [&](ll x, ll y) {return b[x] < b[y];});
        ll _cnt1 = 0;
        for (auto j : h[i])
        {
            g[j] = ++_cnt1;
	    	v[num].eb(b[j]);			
		}
        tr[num].new_build(h[i].size());
    }

s = sqrt(cnt);
    for (rint i = 1; i <= cnt; i++) 
	{
        for (auto j : q[i]) 
		{
            p.change(j, 1);
            for (rint k = 1; k <= num; k++) 
			{
                ll _k = up(v[k].begin(), v[k].end(), j) - v[k].begin();
                if (_k) tr[k].change_1(1, 1, tr[k].n, 1, _k, t[pos[k]]);
            }
        }
        
        for (auto j : B[i]) 
		{
            if (color[y[j]]) tr[color[y[j]]].change_2(1, 1, tr[color[y[j]]].n, g[j], ans[j]);
            else id[y[j]].eb(j);
        }

for (auto j : A[i]) 
		{
            if (color[x[j]]) ans[j] = min(ans[j], tr[color[x[j]]].v[1]);
            else
            {
                for (auto k : id[x[j]])
                {
                    ans[j] = min(ans[j], ans[k] + p.ask(b[k]) * t[x[j]]);					
				}				
			}
            ans[j] += c[j];
        }
    }

for (rint i = 0; i < m; i++)
    {
        if (y[i] == n - 1)
        {
            final_ans = min(final_ans, ans[i] + t[n - 1] * R[b[i]]);			
		}	
	}
    return (final_ans < inf) ? final_ans : -1;
}
```

T3 还想去尝试想一想，但是这种题我是真没经验，最后时间到了也没搞出来。

$100 + 100 + 5 = 205pts$

如果我到了场上，T2 大概率写不出来，VP 和 正赛感觉是天差地别的，在场上我可能没有勇气写那个做法或者想到四边形不等式就去死扣了。不太了解 APIO 赛制，好像是 1.5 h 后分数就不公开了？所以场上也不会知道自己 T2 写挂了。

可惜，当时上高一的时候在是否回归 OI 上犹豫太久，错过了 NOIP，也就错过了 WC 和 APIO

也好，避免了和 APJ 和 fzj 正面交手，等我高二了他们就都退赛了。

并不甘心四边形不等式写不出来，于是去学了一学。

但是发现栈上二分维护决策点这个操作我并不会，也懒得学了。

后来开始逛 耳朵龙 的专栏，看到了 P10536 的题解，之后题解区第二篇也用到了 二分栈，我到现在都不理解这到底是个什么东西，问 ReTF 他说具体题目具体分析，这玩意儿是真没见过，我除了线段树什么的优化 dp 和一些算法竞赛进阶指南上讲的东西以外全不会，三年 OI 光学这本书了。本来打算学一手，但是时间不够了，得回宿舍了。欠着，下辈子补上。