cf2009 Codeforces Round 971 (Div. 4)

A. Minimize!

签到题。计算\((c-a)+(b-c)\)的最小值，其实值固定的，等于\(b-a\)。

int a, b;void solve()
{cin >> a >> b;cout << b - a << endl;
}

B. Osu!mania

签到题。给定一个4k下落式的网格，求#下落顺序。直接数组记录就好了。

int n;
const int N = 500;
char s[N][4];
int v[N];void solve(void)
{cin >> n;int vlen = 0;for (int i = 0; i < n; ++i){for (int j = 0; j < 4; ++j){cin >> s[i][j];if (s[i][j] == '#'){v[vlen++] = j + 1;}}}for (int i = vlen - 1; i >= 0; --i){cout << v[i] << " \n"[i == 0];}
}

C. The Legend of Freya the Frog

签到题。一个人从\((0,0)\)出发跳跃到\((x,y)\)。每步只能跳\(d\)格，\(0\leq d \leq k\)。并且，当朝着\(x/y\)方向跳了一次后，下次就会朝着\(y/x\)方向。这个人初始朝向\(x\)方向。给定\((x,y),k\)求跳的最小次数。

小学数学算一下是x->y->x->y->x还是x->y->x->y就行了。

ll x, y, k;void solve()
{cin >> x >> y >> k;ll dx = (x + k - 1) / k, dy = (y + k - 1) / k;ll res = -1;if (dx > dy){res = (dx << 1) - 1;}else{res = dy << 1;}cout << res << endl;
}

D. Satyam and Counting

水题。现在有一个1xn的网格，给出\(n\)个这个网格上已有的格点坐标。求这些格点能组成多少个直角三角形。分情况讨论再加起来就行。

1. 两个点能组成一条竖边，则剩下的\(n-2\)个点都可以和它们组成三角形。遍历所有点，记录竖边数量\(c_1\)，则这种三角形就有\(c_1\times (n-2)\)个。

   

2. 两个点能组成一条斜边。然后它们中间也有一个点。不要忘记(1,1)(2,0)(3,1)这样颠倒过来也能组成三角形就行了。遍历的时候记录一下即可。

int n;
const int N = 2e5 + 5;
int a[N][2];void solve()
{scanf("%d", &n);for (int i = 0; i <= n + 1; ++i){a[i][0] = a[i][1] = 0;}int p, q;for (int i = 0; i < n; ++i){scanf("%d%d", &p, &q);a[p][q] = 1;}ll one = 0, two = 0, three = 0;for (int i = 0; i <= n; ++i){if (a[i][0] && a[i][1]){one = one + n - 2;}if (i + 2 <= n && a[i][0] && a[i + 1][1] && a[i + 2][0]){two++;}if (i + 2 <= n && a[i][1] && a[i + 1][0] && a[i + 2][1]){three++;}}printf("%lld\n", one + two + three);
}

E. Klee's SUPER DUPER LARGE Array!!!

Klee有一个长度为n的序列[k,k+1,...,k+n-1]，他想选定一个下标\(i\)，使得\(x=|a_1+a_2+..+a_i-a_{i+1}-...-a_n|\)最小。\(2\leq n,k\leq 10^9\)。

水题，这个\(x\)随着\(i\)变大，必是单调增加的，所以二分即可。（狼狈回忆二分）

ll n, k;ll check(ll x)
{ll right = (n + k - 1) * (n + k) / 2LL - (x + 1) * x / 2LL;ll left = (x + 1) * x / 2LL - (k - 1) * k / 2LL;return right - left;
}void solve()
{cin >> n >> k;ll res = 1e18;ll l = 1, r = n + k - 1;while (l < r){ll mid = (l + r) >> 1;ll cur = check(mid);res = min(res, abs(cur));if (cur <= 0){r = mid;}else{l = mid + 1;}}cout << res << endl;
}

F. Firefly's Queries

小水题。有一个长度为\(n\)的数组\(a[n]\)。然后定义了一个cyclic shift的操作。（The x-th\((1\leq x\leq n)\) cyclic shift of the array a is \(a_x,a_{x+1},...,a_n,a_1,a_2,...,a_{x-1}\)）。\(c_i\)就代表了\(a\)的第\(i\)个cyclic shift数组。然后又创建数组\(b\)等于\(c_1,c_2,...,c_n\)（所有的\(c_i\) concatenation到一起）。现有\(q\)次查询，每次查询输出\(b[l:r]\)的元素和。

包含整个\(c_i\)的部分就是\(a[1:n]\)，然后再加上一个小尾巴就行了。

int n, q;
const int N = 2e5 + 5;
int a[N];
ll pre[N];ll cal(ll x)
{if (x < 0LL)return 0LL;ll p = x / n, q = x % n;if (p == 0){return pre[x];}ll left = pre[n - 1] * p;ll pos = (p + q) % n;ll right = 0;if (pos >= p){right = pre[pos] - pre[p - 1];}else{right = pre[n - 1] - pre[p - 1] + pre[pos];}return left + right;
}void solve()
{cin >> n >> q;for (int i = 0; i < n; ++i){cin >> a[i];pre[i] = (i == 0) ? (a[i]) : (pre[i - 1] + a[i]);}ll l, r;while (q--){cin >> l >> r;ll lres = cal(l - 2), rres = cal(r - 1);cout << rres - lres << endl;}
}

G1. Yunli's Subarray Queries (easy version)

有点思维的水题。题面：

对于任意数组\(b\)（下标从1开始），Yunli可以执行以下操作任意次：

• 选择下标\(i\)，令\(b[i]=x\)，\(x\)可以是任意整数。

设\(f(b)\)为她把\(b\)变成一个满足以下条件的数组的最小操作次数：存在长度\(\geq k\)的子序列\(b_{sub}\)（下标从1开始），\(\forall j>1, b_{sub}[j]=b_{sub}[j-1]+1\)。（consecutive subarray）

现给定数组\(a[n]\)以及\(q\)次查询，在每次查询时，输出\(\sum\limits^r_{j=l+k-1}f([a_l,a_{l+1},..,a_j])\)。在easy version中，\(r\equiv l+k-1\)。也就是说，输出的是\(f([a_l,a_{l+1},..,a_j])\)。

数据范围：\(n\leq 2\times 10^5, q\leq 2\times 10^5, 1\leq a[i]\leq n\)。

思路：

首先，我们要知道这样一件事：怎么找一个consecutive subarray？

(1)(2)(3)(4)(5)(6) k=32  3  4  9  6  11

对于这个\(a[n]\)，我们知道可以把2，3，4，x，6中的x改为5，也可以将9，x，11中的x改为10。或者我们可以换一种角度看问题：2，3，4，(x)，6是属于一组的，9，(x)，11是属于另一组的。想要判断数与数之间有没有属于同一组的机会，我们只要对数组\(a\)做一个简单的操作。

令\(a'[i]=a[i]-i\)，此时

(1)(2)(3)(4)(5)(6) k=31  1  1  5  1  5

能看出这件事，这道题就结束了。做一个长度为\(k\)的滑动窗口，记录目前的窗口中数量最多的元素即可。

int n, k, q;
const int N = 2e5 + 5;
int a[N], res[N];void solve()
{cin >> n >> k >> q;for (int i = 0; i < n; ++i){cin >> a[i];}int last = a[0];map<int, int> mp;set<pii, greater<pii>> s;for (int i = 0; i < n; ++i){if (i >= k){res[i - k] = k - s.begin()->first;}// add nxtif (mp.count(a[i] - i)){pii cur = pii(mp[a[i] - i], a[i] - i);if (s.count(cur))s.erase(cur);}mp[a[i] - i]++;s.insert(pii(mp[a[i] - i], a[i] - i));// erase lastif (i >= k){s.erase(pii(mp[last - i + k], last - i + k));if (mp[last - i + k] == 1){mp.erase(last - i + k);}else{mp[last - i + k]--;s.insert(pii(mp[last - i + k], last - i + k));}last = a[i - k + 1];}}res[n - k] = k - s.begin()->first;while (q--){int l, r;cin >> l >> r;cout << res[l - 1] << endl;}
}

G2. Yunli's Subarray Queries (hard version)

这题是上题的困难版本，其中\(r\)的条件改变为\(r\geq l+k-1\)，求\(\sum\limits^r_{j=l+k-1}f([a_l,a_{l+1},..,a_j])\)。

这题需要用到上一题的结论，令\(p_i\)为滑动窗口的起始位置为\(i\)时，记录的\(a'[i:i+k-1]\)重复数量最多的元素数。\(c_i=k-p_i\)，也就是\(c_i=f([a_l,a_{l+1},..,a_{l+k-1}])\)。则\(f([a_l,a_{l+1},..,a_j])=\min(c_l, c_{l+1},..,c_{j-k+1})\)。

区间求最值可以用线段树or树状数组来做，但是还要解决另一个事情，我们要求的是\(\sum\limits^r_{j=l+k-1}\min\{c[l:j-k+1]\}\)，还有个区间求和。再进一步观察，可以看到另一条性质。假设数组\(c\)如下：

(1)(2)(3)(4)(5)(6)(7)1  3  7  4  5  3  6

现在我们算\(c[4]\sim c[7]\)这段的值

(1)(2)(3)(4)(5)(6)(7)4  4  3  3

可以看到，值是单调非增的。也就是说，当\(l=4\)时，\(c[4]=4\)，这个值会一直覆盖后面的值，直到发现了\(c[6]<4\)，则再往后更新就用\(c[6]\)的值更新后面的。那我们就可以想到用一个单调栈来解决这件事。从后往前遍历，当遍历到\(c[cur]\)时，弹出栈顶元素\(c[top]\)，直到\(c[top]<c[cur]\)。然后将\(c[cur]\sim c[top-1]\)的值都更新为\(c[cur]\)。然后再通过区间求和算出此时的\(\sum\limits _{i=cur} ^{r}c_i\)即可，时间复杂度\(O(n\log n)\)。

int n, k, q;
const int N = 2e5 + 5;
ll a[N], c[N];
ll res[N];struct node{int l, r;ll v, lz;
};
node seg[N<<2];void pushup(int oo){seg[oo].v = seg[ls].v + seg[rs].v;
}void pushdown(int oo){int mid = seg[oo].l + seg[oo].r >> 1;seg[ls].v = seg[oo].lz * (mid - seg[oo].l + 1LL);seg[rs].v = seg[oo].lz * (seg[oo].r - mid);seg[ls].lz = seg[rs].lz = seg[oo].lz;seg[oo].lz = 0;
}void build(int oo, int l, int r){seg[oo] = node{l, r, 0LL, 0LL};if (l >= r) return;int mid = l + r >> 1;build(ls, l, mid);build(rs, mid+1, r);pushup(oo);
}void update(int oo, int x, int y, ll val){int l = seg[oo].l, r = seg[oo].r;if (x <= l && y >= r){seg[oo].v = val * (r - l + 1);seg[oo].lz = val;return;}int mid = l + r >> 1;if (seg[oo].lz) pushdown(oo);if (mid >= x) update(ls, x, y, val);if (y > mid) update(rs, x, y, val);pushup(oo);
}ll query(int oo, int x, int y){int l = seg[oo].l, r = seg[oo].r;if (x <= l && y >= r){return seg[oo].v;}ll ans = 0;int mid = l + r >> 1;if (seg[oo].lz) pushdown(oo);if (x <= mid) ans += query(ls, x, y);if (y > mid) ans += query(rs, x, y);return ans;
}void calc(){map<int, int> mp;set<pii, greater<pii> > st;for (int i = 1; i <= n; ++i){// pop lastif (i > k){int last = a[i - k] - i + k;st.erase(pii(mp[last], last));mp[last]--;if (mp[last] == 0) mp.erase(last);else st.insert(pii(mp[last], last));}// push curst.erase(pii(mp[a[i] - i], a[i] - i));mp[a[i] - i]++;st.insert(pii(mp[a[i] - i], a[i] - i));// calculate c valueif (i >= k){pii x = *st.begin();c[i - k + 1] = - x.first;}}
}void solve(){cin >> n >> k >> q;vector<vector<pii> > vec(n - k + 2);for (int i = 1; i <= n; ++i){cin >> a[i];}int l, r;for (int i = 1; i <= q; ++i){cin >> l >> r;vec[l].push_back(pii(r - k + 1, i));}calc();build(1, 1, n - k + 1);stack<int> stk;for (int i = n - k + 1; i >= 1; --i){while (!stk.empty() && c[i] <= c[stk.top()]){stk.pop();}int ed = stk.empty() ? (n - k + 1) : (stk.top() - 1);stk.push(i);update(1, i, ed, c[i]);for (auto p: vec[i]){res[p.second] = 1LL * (p.first - i + 1) * k + query(1, i, p.first);}}for (int i = 1; i <= q; ++i){cout << res[i] << endl;}
}