Educational Codeforces Round 65

Educational Codeforces Round 65 E: $f(l,r)$ 的定义为从 $a$ 中删除所有 $l\le a_i\le r$ 得到的数列，题意是要求出有多少对 $(l,r)$ 满足 $f(l,r)$ 非递减。 设 $G(p)$ 为删除 $a_i<p$ 所有数后得到的数列。设 $L(p)$ 为删除所有 $a_i>p$ 的所有数后得到的数列。可以看出 $f(l,r)=G(l)\cup L(r)$ 。对于每一个数组可以发现有一个固定的 $p^{\prime }$，当$p>p^{\prime }$ 时，$G(p)$ 才非递减，因此可以通过枚举非递减 $G(p)$，对每一个 $p$ 枚举一个最大的 $k$，使得 $F(k)$ 插入到 $G(p)$ 后整个数列非递减。将所有结果求和即为答案。

#include <bits/stdc++.h> using namespace std; const int N = 1e6+7; vector<int> num[N]; int a[N]; int main() { int n, x; scanf("%d%d", &n, &x); for(int i=1; i<=n; ++i) { int k; scanf("%d", &k); num[k].push_back(i); } int nl, nr; int mx=0; memset(a, 0, sizeof(a)); for(nl=1; nl<=x;++nl) { if(num[nl].size()) { bool ok = true; int tmp = mx; for(int k : num[nl]) { if(k<mx) ok = false; tmp = max(tmp, k); } if(!ok) break; for(int k : num[nl]) { a[k] = nl; } mx = tmp; } } --nl; int mn=n+1; for(nr=x;nr>=1;--nr) { if(num[nr].size()) { bool ok = true; int tmp = mn; for(int k : num[nr]) { if(k>mn) ok = false; tmp = min(tmp, k); } if(!ok) break; mn = tmp; } } ++nr; // cout << nl << " " << nr << endl; int l = min(nl,x-1); // 1 2 3 4 5 int p = n; long long ans = l+1; for(int i=x;i>=nr;--i) { if(num[i].size()) { // i表示选取[i,x]有序序列，截掉的最大串应该为[1, i-1] int mn = N; for(int k : num[i]) { mn=min(mn, k); } for(int i=mn; i<=p; ++i) { if(a[i]) l = min(l, a[i]-1); //删掉一些冲突的。 } p=mn-1; } ans += min(l+1, i-1); } printf("%I64d\n", ans); }

F: 通过观察可以发现 $$f(l,r)=\sum _{i=l}^r{a}_i\times (lower(l,r,a_i)+1)$$ 其中 $lower(l,r,x)$ 为在区间 $[l,r]$内小于 $x$ 的数的数量。然后经过一阵推导可以将问题转化为枚举所有 $a_i$ ，对lower求和的问题，对原问题进行了简化。解决这个问题的关键是能想到把枚举 $a_i$ 的求和式提到最外面来，从而转化为枚举 $a_i$ 计算的问题，简化了复杂度。 具体推导

#include <bits/stdc++.h> using namespace std; const int N = 5e5+7; using ll = long long; const ll mod = 1e9+7; int n; ll c[N]; ll L[N], R[N]; int a[N]; int b[N], rk[N]; int lowbit(int x) { return x&-x; } void update(int x, ll v) { for(; x<=n; x+=lowbit(x)) c[x]+=v; } ll query(int x) { ll res = 0; for(; x>0; x-=lowbit(x)) res+=c[x]; return res%mod; } int main() { scanf("%d", &n); for(int i=1; i<=n; ++i) scanf("%d", &a[i]); for(int i=1; i<=n; ++i) b[i]=i; sort(b+1, b+1+n, [](int l, int r){ return a[l]<a[r]; }); for(int i=1; i<=n; ++i) rk[b[i]]=i; for(int i=1; i<=n; ++i) { L[i] = query(rk[i]); // cout << L[i] << endl; update(rk[i], i); } memset(c, 0, sizeof(c)); for(int i=n; i>=1; --i) { R[i] = query(rk[i]); update(rk[i], n-i+1); } // for(int i=1; i<=n; ++i) { // printf("lr: %I64d %I64d\n", L[i], R[i]); // } ll ans = 0; for(int i=1; i<=n; ++i) { ans += 1LL*a[i]*(((n-i+1)*L[i]%mod+i*R[i]%mod)%mod)%mod; ans %= mod; ans += 1LL*a[i]*(n-i+1)%mod*i%mod; ans%=mod; // cout << ans << endl; } printf("%I64d\n", ans); }

G: 将碰撞看成两类：块与块的碰撞和块与线的碰撞，从而能进行分类讨论。 对于块与块的碰撞，可以观察到当且仅当两个块距离对折点的距离小于等于1时才会碰撞，且离对折点最近的块与块碰撞最先发生。因此可以枚举对折点两端块分布的bitset，按位与用 _Find_first 找到第一个碰撞点。不需要维护所有碰撞点，因为题目有块之间最大距离为d的限制，可以保证仅仅枚举左右两端各长为d的bitset，可以保证得到的最小弧度是 $arctan\frac{2}{d}$ ，bitset范围之外就算碰撞，最大弧度也只有 $arctan\frac{2}{d}$ 。 对于线与块的碰撞，分别找左右两边第一个块就行。

#include <bits/stdc++.h> using namespace std; const int N = 5e5+7; using ll = long long; const ll mod = 1e9+7; int n; ll c[N]; ll L[N], R[N]; int a[N]; int b[N], rk[N]; int lowbit(int x) { return x&-x; } void update(int x, ll v) { for(; x<=n; x+=lowbit(x)) c[x]+=v; } ll query(int x) { ll res = 0; for(; x>0; x-=lowbit(x)) res+=c[x]; return res%mod; } int main() { scanf("%d", &n); for(int i=1; i<=n; ++i) scanf("%d", &a[i]); for(int i=1; i<=n; ++i) b[i]=i; sort(b+1, b+1+n, [](int l, int r){ return a[l]<a[r]; }); for(int i=1; i<=n; ++i) rk[b[i]]=i; for(int i=1; i<=n; ++i) { L[i] = query(rk[i]); // cout << L[i] << endl; update(rk[i], i); } memset(c, 0, sizeof(c)); for(int i=n; i>=1; --i) { R[i] = query(rk[i]); update(rk[i], n-i+1); } // for(int i=1; i<=n; ++i) { // printf("lr: %I64d %I64d\n", L[i], R[i]); // } ll ans = 0; for(int i=1; i<=n; ++i) { ans += 1LL*a[i]*(((n-i+1)*L[i]%mod+i*R[i]%mod)%mod)%mod; ans %= mod; ans += 1LL*a[i]*(n-i+1)%mod*i%mod; ans%=mod; // cout << ans << endl; } printf("%I64d\n", ans); }