P3628:[APIO2010]特别行动队题解 & 斜率优化分析

暴力做法

我们首先来推下这道题普通的 DP 方程,显而易见,维护前缀和后,在\(f[i]\)时枚举一个点\(j\)划分即可:

\[ f[i] = max_{j\in [1,i-1]} \{f[j]+a(S[i]-S[j])^2+b(S[i]-S[j])+c\} \]

时间复杂度为\(O(n^2)\),GG。

斜率优化分析

第一步 – 写出斜率方程

这是所有斜率优化题目分析的第一步:给定两个量\(j_1<j_2\),写出斜率不等式得出单调关系。这一步进行参变分离即可,稍稍有点麻烦。

我们以本题为例,进行斜率方程的推导:

\[ f[j_1]+a(S[i]-S[j_1])^2+b(S[i]-S[j_1])+c>f[j_2]+a(S[i]-S[j_2])^2+b(S[i]-S[j_2])+c \\ (f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])>2a(S[j_1]-S[j_2])*S[i] \\ \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-*S[j_2])}>S[i] \]

注意\(a<0\)

第二步 – 队头的弹出条件

我们观察这个方程,当\(j_2\)比\(j_1\)更优时:

\[ \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-S[j_2])} \leq S[i] \]

因为\(S[i]\)随着\(i\)单调不下降,所以当\(j_2\)比\(j_1\)更优时,\(j_1\)永远不会被考虑,弹出。

第三步 – 队头转移

这个没什么好说的,直接将\(q[head]\)当做\(j\)来用即可。

第四步 – 队尾的处理

我们还需要保证这些直线斜率的单调性。首先,以本题为例,我们来对斜率单调性进行分析。

我们假设斜率函数为\(slope(j_1,j_2)\),函数的解析式就是我们上面推出来的式子,即:

\[ slope(j_1, j_2) = \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-S[j_2])} \]

我们假设直线的斜率必须要单调递增,也就是\(l<mid<r, slope(l,mid)<slope(mid,r)\)。我们在单调队列中只保留可能成为最优解的选项,也就是对于元素\(a_1,a_2,a_3\),\(a_1\)比\(a_2\)更优且\(a_2\)比\(a_3\)更优。所以,中间我们有:

\[ slope(l,mid)>S[i] \text{且} slope(mid,r)<S[i] \]

整理得:

\[ slope(l,mid)>slope(mid,r) \]

与假设相反。所以,我们处理队尾的时候其实就是在维护这个关系,所以弹出条件就是“如果这个斜率是单调递增的”:

\[ l<mid<r, slope(l,mid)<slope(mid,r) \]

所以,分析完毕。

代码

// P3628.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 2000;
ll n, xi[MAX_N], a, b, c, S[MAX_N], f[MAX_N], q[MAX_N], head, tail;
ll pow(ll num) { return num * num; }
double slope(int j1, int j2)
{
    return double((f[j1] - f[j2] + b * (S[j2] - S[j1]) + a * (pow(S[j1]) - pow(S[j2])))) / double(2 * a * (S[j1] - S[j2]));
}
int main()
{
    scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &xi[i]), S[i] = S[i - 1] + xi[i];
    head = 1, tail = 1;
    for (int i = 1; i <= n; i++)
    {
        while (head < tail && slope(q[head], q[head + 1]) <= S[i] * 1.0)
            head++;
        f[i] = f[q[head]] + a * pow(S[i] - S[q[head]]) + b * (S[i] - S[q[head]]) + c;
        while (head <= tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i))
            tail--;
        q[++tail] = i;
    }
    printf("%lld", f[n]);
    return 0;
}

BZOJ3450:Easy 题解

主要思路

一道非常好的题,适合我这种概率期望新手来搞。

首先,我们设\(dp[i]\)为以\(i\)结尾的期望长度。其次,我们发现\((x+1)^2-x^2=2x+1\),如果要求连续的根据字符的情况,有以下几种转移:

  1. 当\(str[i]=’o’\)时,那么\(dp[i] = dp[i-1]+1\),对答案的贡献为\(2dp[i-1]+1\)。
  2. 当\(str[i]=’x’\)时,不进行转移,对答案贡献为\(0\)。
  3. 当\(str[i]=’?’\)时,为\(o\)的概率为\(\frac{1}{2}\),转移为\(dp[i]=\frac{dp[i-1]+1}{2}\),对答案的贡献为\(\frac{2dp[i-1]+1}{2}\)。

乱搞即可。

代码

// BZ3450.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300200;
int n;
char str[MAX_N];
long double dp[MAX_N], ans;
int main()
{
    scanf("%d%s", &n, str + 1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        switch (str[i])
        {
        case 'o':
            dp[i] = dp[i - 1] + 1;
            ans += 2 * dp[i - 1] + 1;
            break;
        case 'x':
            dp[i] = 0;
            break;
        case '?':
            dp[i] = 1.0 * (dp[i - 1] + 1) / 2.0;
            ans += 1.0 * (2.0 * dp[i - 1] + 1) / 2.0;
            break;
        }
    printf("%.4Lf", ans);
    return 0;
}

Educational DP Contest : M – Candies 题解

主要思路

我这个傻逼还搞个多重集容斥恶心自己。

首先分析题意,不难想出转移方程:

\[ dp[i][j] = dp[i-1][j]+\sum_{k = limit[i]}^{j} dp[i-1][k] \]

然后考虑用\(O(n)\)的时间先预处理出前缀和\(dp[i-1][k-1]\),然后大的减小的\(O(1)\)查询即可。

代码

// M.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 110, MAX_K = 1e5 + 200, MOD = 1e9 + 7;
ll n, limit[MAX_N], dp[MAX_N][MAX_K], k, mxk, prefix[MAX_K];
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &limit[i]), dp[i][0] = 1;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        prefix[i] = 0;
        for (int j = 1; j <= k + 1; j++)
            prefix[j] = prefix[j - 1] + dp[i - 1][j - 1];
        for (int j = 1; j <= k; j++)
        {
            dp[i][j] = dp[i - 1][j] + prefix[j] - prefix[max(0LL, j - limit[i])];
            dp[i][j] %= MOD;
        }
    }
    printf("%d", dp[n][k]);
    return 0;
}

[Fortuna OJ]Feb 26th – Group A 解题报告

A – 礼物

说实话,这就是我最薄弱的一项,且在比赛中一览无余的暴露出来了。

我们可以把这道题转换一下,可以发现,这个喜悦值毫无关系,第二题的题意即为

给一些物品\(a_i\),每次操作有\(p_i\)的概率可能出现,求要使所有物品出现的期望操作次数。

考虑物品的个数很少,可以进行状压,压缩到\(S\)。对于每一个出现过物品\(i\)的情况,都可以从没有出现过的状态转移过来,即S^(1<<(i - 1))。对之前的情况乘上一个\(p_i\)即为这一部分的贡献。之后,因为\(\sum_{i} {p_i} \neq 1\),所以存在操作无效的情况,也就是\((1-\sum_{i\in S} p_i)*E_S\)。之后加上操作次数\(1\),式子全貌为:

\[ E_S = (\sum_{i\in S} p_i*E_{S’}) + (1-\sum_{i\in S} p_i)*E_S + 1 \]

移项合并可得:

\[ (\sum_{i\in S} p_i)*E_S = (\sum_{i\in S} p_i*E_{S’}) + 1 \\ E_S = \frac{(\sum_{i\in S} p_i*E_{S’}) + 1}{\sum_{i\in S} p_i} \]

代码

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 21;
int n, wi[MAX_N];
long long ans1;
double pi[MAX_N], dp[(1 << 20)];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%d", &pi[i], &wi[i]), ans1 += wi[i];
    for (int stat = 0; stat < (1 << n); stat++)
    {
        double psum = 0, ans = 0;
        for (int i = 1; i <= n; i++)
            if (stat & (1 << (i - 1)))
            {
                int prestat = stat ^ (1 << (i - 1));
                psum += pi[i];
                ans += pi[i] * dp[prestat];
            }
        if (psum != 0)
            dp[stat] = (ans + 1) / psum;
    }
    printf("%lld\n%.3lf", ans1, dp[(1 << n) - 1]);
    return 0;
}

B – 通讯

啊,我*。

这道题很水,不讲。

代码

/// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 100400, MAX_M = 1e5 + 2000;
int head[MAX_N], current, dfn[MAX_N], low[MAX_N], tot, st[MAX_N], hd, aff[MAX_N];
int totp, n, m, tmpx, tmpy, tmpz, ufs[MAX_N], dist[MAX_N];
bool inst[MAX_N];
struct edge
{
    int to, nxt, weight, from;
    bool operator<(const edge &e) const { return weight > e.weight; }
} edges[MAX_M << 1];
int find(int x) { return (ufs[x] == x) ? x : ufs[x] = find(ufs[x]); }
void unite(int x, int y)
{
    if (find(x) != find(y))
        ufs[find(x)] = find(y);
}
int addpath(int u, int v, int weight)
{
    edges[current].to = v, edges[current].nxt = head[u];
    edges[current].from = u;
    edges[current].weight = weight, head[u] = current++;
    return current - 1;
}
void tarjan(int u)
{
    inst[u] = true, st[++hd] = u;
    dfn[u] = ++tot, low[u] = dfn[u];
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dfn[edges[i].to] == 0)
            tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
        else if (inst[edges[i].to])
            low[u] = min(low[u], dfn[edges[i].to]);
    if (dfn[u] == low[u])
    {
        int j;
        totp++;
        do
        {
            j = st[hd], aff[j] = totp;
            inst[j] = false;
        } while (st[hd--] != u);
    }
}
int main()
{
    while (scanf("%d%d", &n, &m) && n != 0 && m != 0)
    {
        memset(dist, 0x3f, sizeof(dist));
        memset(st, 0, sizeof(st)), memset(dfn, 0, sizeof(dfn)), hd = 0;
        for (int i = 1; i <= 2 * n; i++)
            ufs[i] = i;
        memset(head, -1, sizeof(head)), memset(aff, 0, sizeof(aff));
        totp = n, current = 0, tot = 0;
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx + 1, tmpy + 1, tmpz);
        tarjan(1);
        for (int i = 1; i <= n; i++)
            for (int e = head[i]; e != -1; e = edges[e].nxt)
                if (aff[i] != aff[edges[e].to])
                    dist[aff[edges[e].to]] = min(dist[aff[edges[e].to]], edges[e].weight);
        long long ans = 0;
        for (int i = n + 1; i <= totp; i++)
            if (aff[1] != i)
                ans += dist[i];
        printf("%lld\n", ans);
    }
    return 0;
}

C – 奇袭

这道题来自于 Codeforces,画风十分一至。

首先转换题意,这道题提示了每一个横纵坐标都只会存在一个点,求长为\(len\)且纵坐标最大最小值也为\(len\)的区间个数。我们可以用分治来搞一搞。首先定一个区间\([l,r]\),中点为\(mid\)。我们来探索跨这两个小区间的几种情况。

首先,我们在分类讨论之前设定几个数组:

  1. 设\(minl[i]\)为区间\([i,mid]\)的最小值,\(maxl[i]\)为区间\([i,mid]\)的最大值;

  2. 设\(minr[i]\)为区间\([mid+1,i]\)的最小值,\(maxr[i]\)为区间\([mid+1,i]\)的最大值。

那么,我们可以讨论跨越的情况:

  1. 最值都在左、右同一个区间内

  2. 最值分别在两个不同的区间

第一种情况比较好解决,在左区间的情况下:枚举一个左端点\(i\),可以根据最值之差算出右端点,进行检查并计数。

第二种稍稍麻烦一点:跨区间要考虑最值的两种分布方式,我们以最小值在左侧,最大值在右侧为例,假设有个点符合条件:

\[ maxr[j]-minl[i] = j-i \\ \text{移项得} \\ maxr[j]-j=minl[i]-i \]

可以枚举断点,把计算内容放到桶里去(注意负数,加上数域偏移),然后用两个指针判断合法区间,左端指针减一,右指针加一。

代码

// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50200, NUM_DOMAIN = 6e5;
pair<int, int> prs[MAX_N];
int arr[MAX_N], n, maxl[MAX_N], maxr[MAX_N], minl[MAX_N], minr[MAX_N], bucket[2 * NUM_DOMAIN + 1];
long long answer = 0;
void dq(int l, int r)
{
    if (l == r)
    {
        answer++;
        return;
    }
    int mid = (l + r) >> 1;
    // preprocessing;
    minl[mid] = arr[mid], maxl[mid] = arr[mid];
    maxr[mid + 1] = arr[mid + 1], minr[mid + 1] = arr[mid + 1];
    for (int i = mid - 1; i >= l; i--)
        minl[i] = min(minl[i + 1], arr[i]), maxl[i] = max(maxl[i + 1], arr[i]);
    for (int i = mid + 2; i <= r; i++)
        maxr[i] = max(maxr[i - 1], arr[i]), minr[i] = min(minr[i - 1], arr[i]);
    // make judges;
    // at the left:
    for (int i = mid; i >= l; i--)
    {
        int j = i + (maxl[i] - minl[i]);
        if (j > mid && j <= r && minr[j] > minl[i] && maxr[j] < maxl[i])
            answer++;
    }
    // at the right;
    for (int i = mid + 1; i <= r; i++)
    {
        int j = i - (maxr[i] - minr[i]);
        if (j <= mid && j >= l && minl[j] > minr[i] && maxl[j] < maxr[i])
            answer++;
    }
    // in the middle;
    // min|max:
    int ptr1 = mid + 1, ptr2 = mid;
    for (int i = mid; i >= l; i--)
    {
        while (minr[ptr2 + 1] > minl[i] && ptr2 < r)
            ptr2++, bucket[maxr[ptr2] - ptr2 + NUM_DOMAIN]++;
        while (maxl[i] > maxr[ptr1])
        {
            bucket[maxr[ptr1] - ptr1 + NUM_DOMAIN]--, ptr1++;
            if (ptr1 > r)
                break;
        }
        if (ptr1 > r)
            break;
        if (ptr1 <= ptr2)
            answer += bucket[minl[i] - i + NUM_DOMAIN];
    }
    for (int i = mid; i >= l; i--)
        bucket[minl[i] - i + NUM_DOMAIN] = 0;
    for (int i = mid + 1; i <= r; i++)
        bucket[maxr[i] - i + NUM_DOMAIN] = 0;
    // max|min:
    ptr1 = mid,
    ptr2 = mid + 1;
    for (int i = mid + 1; i <= r; i++)
    {
        while (minl[ptr2 - 1] > minr[i] && ptr2 > l)
            ptr2--, bucket[maxl[ptr2] + ptr2 + NUM_DOMAIN]++;
        while (maxr[i] > maxl[ptr1])
        {
            bucket[maxl[ptr1] + ptr1 + NUM_DOMAIN]--, ptr1--;
            if (ptr1 < l)
                break;
        }
        if (ptr1 < l)
            break;
        if (ptr2 <= ptr1)
            answer += bucket[minr[i] + i + NUM_DOMAIN];
    }
    for (int i = mid + 1; i <= r; i++)
        bucket[minr[i] + i + NUM_DOMAIN] = 0;
    for (int i = mid; i >= l; i--)
        bucket[maxl[i] + i + NUM_DOMAIN] = 0;
    dq(l, mid), dq(mid + 1, r);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &prs[i].first, &prs[i].second);
    for (int i = 1; i <= n; i++)
        arr[prs[i].first] = prs[i].second;
    dq(1, n);
    printf("%lld", answer);
    return 0;
}

[Fortuna OJ]Feb 25th – Group A 解题报告

A – Tourist Problem

非常有趣的一道数学题,我们来分析一下。原讲稿:https://comfortablecom.wordpress.com/2017/10/06/jzoj-b%E7%BB%84-10-6-%E6%80%BB%E7%BB%93/

我们先设一种情况的答案为\(S_x\),显然,可以写成:

\[ S_x = |a_{x_1}-0|+|a_{x_2}-a_{x_1}|+|a_{x_3}-a_{x_2}|+|a_{x_4}-a_{x_3}|+\dots +|a_{x_n}-a_{x_{n-1}}| \]

这一长串的答案其实就是被减数与减数的组合。我们会发现,几乎每一个数都在这个式子中扮演了被减数与减数的角色,除了最后一个元素,即\(a_{x_n}\)。这个元素只充当了一次被减数,仅此而已。

我们考虑\(i\)对答案的贡献。首先,\(i\)作为被减数一共有\(n!\)中可能,其中减数缺了一部分的可能,这一缺失的部分就是\(i\)作为\(a_{x_n}\)的可能数,也就是\((n-1)!\)。之后,考虑在一种序列中\(i\)的贡献。当\(j<i\)时,包括\(0\),一共有\(i\)个数使\(i\)可以在不变号的情况下减去减数;而,当\(i<j\)时,情况就不同了,一共有\(n-i\)种数是的\(i\)在变号的情况下进行对答案的贡献。部分分析结束,总结为一个式子:

\[ a_i(n-1)!i+(-a_i)(n-1)!(n-i) \]

结合上面我所分析的可能方案数和不同情况下的讨论,请读者用心领悟。

而作为减数其实就是换汤不换药了。只要把正负的两种关系变化一下即可,计算式为:

\[ (-a_i)(n-1)!(n-i)+a_i(n-1)!(i-1) \]

注意,此式中最后一项中的\(i-1\)是因为\(0\)无法作为其被减数而造成的。有那么一点点不对称吧。

代码

// A.cpp
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int MAX_N = 100200;
int n, arr[MAX_N];
ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    sort(arr + 1, arr + 1 + n);
    ll x = 0;
    for (int i = 1; i <= n; i++)
        x = x + 1LL * arr[i] * (1LL * 4 * i - 1LL * 2 * n - 1);
    ll d = gcd(x, n);
    printf("%lld %lld", x / d, n / d);
    return 0;
}

B – 工作安排 Work

这道题其实在考场上连斜率式子都推完了,但是因为太懒而且不知道怎么隔着\(k\)进行转移所以弃疗,最后边界忘记检查 50 分傻*暴力都没拿到。

这道题的 DP 方程式可通过一眼法得出,其中需要先进行排序:

\[ dp[i] = min\{ f[j-1]+C+(f[i]-f[j])^2 \}, j-1 \in [0,i-k] \]

之后我们来思考如何进行斜率优化。斜率优化是一个非常常用的 DP 优化手段,建议深入了解。我们设\(k\)为我们想要的最优解,那它一定满足:

\[ f[k-1]+C+(f[i]-f[k])^2 < f[j-1]+C+(f[i]-f[j]))^2, j \in [1, i-k+1], j \neq k \\ (f[k-1]-f[j-1])+(f[k]^2-f[j]^2) < 2f[i](f[k]-f[j]) \]

判断时,注意正负号对不等式的影响。

代码

// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 2e6 + 20000;
const ll INF = (0x3f3f3f3f3f3f3f3f);
ll f[MAX_N], arr[MAX_N], n, k, c, q[MAX_N << 2];
int head = 1, tail = 0;
ll pow(ll num) { return num * num; }
double check(ll a, ll b)
{
    return ((f[b - 1] + pow(arr[b])) - (f[a - 1] + pow(arr[a]))) / (2.0 * (arr[b] - arr[a]));
}
void insert(int x)
{
    while (head <= tail && arr[q[tail]] == arr[x])
        if (f[x - 1] < f[q[tail] - 1])
            tail--;
        else
            return;
    while (head < tail && check(q[tail - 1], q[tail]) > check(q[tail], x))
        tail--;
    q[++tail] = x;
}
int main()
{
    freopen("work1.in", "r", stdin);
    scanf("%lld%lld%lld", &n, &k, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    f[0] = 0;
    sort(arr + 1, arr + 1 + n);
    for (int i = 1; i < k; i++)
        f[i] = INF;
    for (int i = k; i <= n; i++)
    {
        int x = i - k + 1;
        insert(x);
        while (head < tail && check(q[head], q[head + 1]) < arr[i])
            head++;
        f[i] = f[q[head] - 1] + c + pow(arr[q[head]] - arr[i]);
    }
    printf("%lld", f[n]);
    return 0;
}

C – 阿Q的停车场 Park

一道线段树的题目(我改题的时候差点下定决心整晚写个 Treap 的版本来搞,最后发现线段树绰绰有余)。我们维护左边极点、右边极点、最长空位长度和最佳停车点。线段树更新的时候选择左区间、合并区间和右区间进行比较即可。

代码

// C.cpp
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
using namespace std;
const int MAX_N = 200200, INF = 0x3f3f3f3f;
int n, m, tree_l[MAX_N << 2], tree_r[MAX_N << 2], tree_len[MAX_N << 2], tree_pt[MAX_N << 2], park[(int)1e6 + 2000];
int getFirst(int a, int b, int c, int d)
{
    if (a > 0)
        return a;
    if (b > 0)
        return b;
    if (c > 0)
        return c;
    if (d > 0)
        return d;
    return d;
}
void update(int qx, int l, int r, int p)
{
    if (l == r && l == qx)
    {
        tree_l[p] = l, tree_r[p] = r, tree_len[p] = 0, tree_pt[p] = 0;
        return;
    }
    if (qx <= mid)
        update(qx, l, mid, lson);
    else
        update(qx, mid + 1, r, rson);
    tree_l[p] = getFirst(tree_l[lson], tree_r[lson], tree_l[rson], tree_r[rson]);
    tree_r[p] = getFirst(tree_r[rson], tree_l[rson], tree_r[lson], tree_l[lson]);
    // check three intervals;
    // first;
    tree_len[p] = tree_len[lson], tree_pt[p] = tree_pt[lson];
    if (tree_l[rson] > 0 && tree_r[lson] > 0 && ((tree_l[rson] - tree_r[lson]) >> 1) > tree_len[p])
        tree_len[p] = (tree_l[rson] - tree_r[lson]) >> 1, tree_pt[p] = (tree_r[lson] + tree_l[rson]) >> 1;
    if (tree_len[rson] > tree_len[p])
        tree_len[p] = tree_len[rson], tree_pt[p] = tree_pt[rson];
}
void remove(int qx, int l, int r, int p)
{
    if (l == r && l == qx)
    {
        tree_l[p] = tree_r[p] = tree_len[p] = tree_pt[p] = 0;
        return;
    }
    if (qx <= mid)
        remove(qx, l, mid, lson);
    else
        remove(qx, mid + 1, r, rson);
    tree_l[p] = getFirst(tree_l[lson], tree_r[lson], tree_l[rson], tree_r[rson]);
    tree_r[p] = getFirst(tree_r[rson], tree_l[rson], tree_r[lson], tree_l[lson]);
    // check three intervals;
    // first;
    tree_len[p] = tree_len[lson], tree_pt[p] = tree_pt[lson];
    if (tree_l[rson] > 0 && tree_r[lson] > 0 && ((tree_l[rson] - tree_r[lson]) >> 1) > tree_len[p])
        tree_len[p] = (tree_l[rson] - tree_r[lson]) >> 1, tree_pt[p] = (tree_r[lson] + tree_l[rson]) >> 1;
    if (tree_len[rson] > tree_len[p])
        tree_len[p] = tree_len[rson], tree_pt[p] = tree_pt[rson];
}
int main()
{
    scanf("%d%d", &n, &m);
    while (m--)
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1)
        {
            if (tree_l[1] > 0)
            {
                int tmp = tree_len[1], key = tree_pt[1];
                if (tree_l[1] - 1 >= tmp)
                    key = 1, tmp = tree_l[1] - 1;
                if (n - tree_r[1] > tmp)
                    key = n, tmp = n - tree_r[1];
                park[x] = key;
            }
            else
                park[x] = 1;
            printf("%d\n", park[x]), update(park[x], 1, n, 1);
        }
        else
            remove(park[x], 1, n, 1);
    }
    return 0;
}

 

Microsoft on MWC 2019 – 观后感

Computing is embedded in our life.

It is not combined in a single device.

在 MWC 上鲜有露面的 Microsoft 此次请出了老大 Satya Nadella 来做一个产品发布,意义一定不一般。媒体在发布会之前已经猜测此次 Microsoft 会发布下一代的 HoloLens,引入更多的改进,加速 Mixed Reality 融入这个世界,和进入这个巨大的市场。各大科技博主和 YouTuber 解读预热视频为:碳纤维框架、新的芯片。

在一堆废话之后,Julia 女士上场了。她主要介绍了微软的云服务状态。介绍了 Azure 服务之前给客户的解决方案,提到了 IoT 和一些其他正常人不太在意的东西。微软现在 2B 服务做的很不错。

之后就是令人兴奋到窒息的环节了:HoloLens 2。外观其实差不多,不是最夺目的特征。其实于我个人而言,Alex Kipman 的每次出场都意味着微软在计算机图形方面的巨大进步,而且其本人的能力也是非常超群的,履历上的 Kinect 开发经验就已经意味着可以胜任这个方面的负责人。

Alex Kipman 的出场

首先,Alex Kipman 给我们看了 HoloLens 2 的外观。

HoloLens 2

之后,Alex Kipman 从三个方面说明了本代 HoloLens 的改进:FOV(视场)、舒适度和一个不太记得的东西。

Field of View 相比于上一代变大了一倍,从可怜的 40° 提升到了 80°。这个是最大的提升;跟据 Alex ,这代 HoloLens 2 在你的眼前塞下了一块 2K 屏幕。

FOV 和像素密度的提升,实现 2K 分辨率

舒适度主要集中在碳纤维的机身和其先进的交互方式。这是真正的人机交互方式,Microsoft 的设想是“在人完全不知道这玩意怎么用的情况下快速上手”,并且集成了更加强大的 Kinect 类的扫描系统。得益于这个更新过的技术,我们的双手能在系统内被完全建模,让我们的双手有了触摸全息图像的能力。

更人性化的交互方式

这些都非常令人激动的革新,让很多人离他们梦寐以求的未来世界又近了一步。

之后,Microsoft 邀请了几个合作伙伴上台,一起来叙说 HoloLens 带给世界的价值。这些公司里包括 Spatial, Trimble(我很感兴趣的公司之一), Epic Games。我认为,HoloLens 不会缺少应用的机会的,无论是建筑、医疗还是娱乐。

作为一个跟随 Microsoft 多年的开发者,我个人非常关注其生态系统的布局。而 Alex Kipman 则在叙述愿景之后给出了 Three Principles。我说实话,粉微软,我没后悔过。

三开放政策:「开放的应用商店」、「开放的网络浏览」和「开放的平台」

对于这三个 Open,我真的很开心。我可以梦想到有一天,技术会以人类的方式帮助人类做任何事情。这一次,又重新激起了我奋斗的目的:为的就是学习和开发这样的技术,与这样的人共事。

最后发表一下我对微软的感情吧,作为一个从 Build 2012 开始看的 00 后开发者,我每年都能见到微软的新东西。2012 的 Windows 8,2015 的 HoloLens 1 和 Windows 10 及其 UWP 大一统野心(虽然凉掉了),之后的 Fluent Design,再到如今的 HoloLens 2,每一次都能让我疯狂一段很长的时间。

我就是喜欢好的技术啊。

晚安,祝你一路顺利,我会努力来找你的,Microsoft。