ABCD 略
E Insert or Erase
手写链表调了这么久。。链表模板。
F Earn to Advance
考虑 DP，但是我们发现不是很好转移，然后我们发现 \(n \le 80\)，我们观察一下题目的性质。
如果路径确定了，那么我们肯定会在最大值的地方使劲加到终点为止。
那么我们考虑直接按照那个路径最大值用 \(O(n^4)\) 来跳着转移。
我们 \(O(n^4)\) 预处理出所有两点之间的最小花费。
然后在记一个 \(dp_{i,j}\) 表示从 \((1,1)\) 走到 \((i,j)\) 的最小步数，还有一个 \(s_{i,j}\) 表示在最小步数的情况下最大的剩余值，然后我们用 \((i,j)\) 去更新 \(\forall (a,b)(i\le a \le n, j\le b \le n)\)，转移就比较简单了。
G Points and Comparison
我靠，为啥这个 G 3000+，赛事思考 5 分钟想出正解，30 min 没有调出来，(可能比较容易写挂)，就是我们考虑把式子变形一下:
那么我们可以将数对 \((X_i,Y_i)\) 视为一次函数，\((A_j,B_j)\) 视作限制。
那么题目求的东西也可以转换为对于一些 \(x\) 和一些一次函数，我们要求出对于每一个 \(x\)，求出 \(f_i(x)\) 的个数满足函数值小于等于某一个值。
如果直接暴力的话那复杂度就是 \(x\) 的个数 \(\times\) 函数的个数，即：\(O(qn)\)。
我们考虑优化。
就是考虑对于一次函数来排序，然后二分。
如果直接排序那就是负优化了。
我们可以这么做：
先对所有限制的 \(x\) 值进行排序。然后把每一对一次函数的交点处理出来，存进 vector，然后对于交点也按照 \(x\) 值排序。
于是我们可以类似扫描线，将限制的 \(x\) 从小到大来遍历
那么我们可以对于每一对一次函数求出交点，交点就相当于这两个一次函数需要类似于排序中的交换。但是直接交换似乎有问题，我们可以暴力将那些需要交换的一次函数取出来。然后暴力排序，在填入它们本来的位置即可。。（似乎非常暴力)。
这样我们就可以做到快速对于一次函数排序了。。
然后直接二分就做完了。
时间复杂度：\(O(n^2\log(n^2)+q\log(n))\)。
最后的最后，思考一下为什么最开始的式子需要变形。
因为如果不变形的话时间复杂度是 \(O(q^2\log(q^2)+n\log(q))\)。
变形就相当于将原题中的一次函数和限制交换了一下。
也就是让 \(n\) 和 \(q\) 交换了一下。所以才能保证通过。。
Difficulty: 3032，2400。
贴一下代码：
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for (int i = (l); i <= (r); i++)
#define per(i,r,l) for (int i = (r); i >= (l); i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define maxn(a, b) a = max(a, b)
#define minn(a, b) a = min(a, b)
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod = (1ll<<31)-1;
ll rp(ll a,ll b) {ll res=1%mod;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N = 5043;
const int Q = 1e7+1;
int n, q, Ra;
pair<int,ll> a[Q];
int g[Q*3], pos[N];
ll Rb;
array<int,3> f[N];
ll calc(array<int, 3> t, int x) {
return x * 1ll * t[0] + t[1];
}
db calc(const array<int, 3> &A, const array<int, 3> &B) {
return (B[1] - A[1]) * 1.0 / (A[0] - B[0]);
}
int main() {
scanf("%d", &n);
rep(i,1,n) {
scanf("%d%d", &f[i][0], &f[i][1]);
f[i][1]*=-1;
f[i][2]=i;
}
scanf("%d", &q);
scanf("%d%d%lld", &g[0], &Ra, &Rb);
rep(i,0,q*3) {
g[i + 1] = (48271ll * g[i]) % mod;
}
rep(i,1,q) {
a[i].fi = -Ra + (g[3*i-2]%(2ll*Ra+1));
a[i].se = -Rb + ((g[3*i-1]*mod+g[3*i]) % (2 * Rb + 1));
a[i].se*=-1;
}
sort(a + 1, a + 1 + q);
rep(i,1,n) pos[f[i][2]] = i;
vector<pair<db,pair<int,int>>> st;
rep(i,1,n) {
rep(j,i+1,n) if (f[i][0] != f[j][0]) {
st.push_back({calc(f[i], f[j]), mp(f[i][2], f[j][2])});
}
}
sort(all(st));
ll ans = 0;
int p = 0;
rep(i,1,q) {
set<int> pst;
while (p < SZ(st) && st[p].fi < a[i].fi) {
pst.insert(pos[st[p].se.fi]);
pst.insert(pos[st[p].se.se]);
p++;
}
if (i == 1) rep(j,1,n) pst.insert(j);
vector<array<int,3>> vst;
for (auto tp : pst) vst.pb(f[tp]);
sort(all(vst), [&](const array<int, 3> &A, const array<int, 3> &B) {
return calc(A, a[i].fi) > calc(B, a[i].fi);
});
assert(SZ(vst) == SZ(pst));
for (auto tp : pst) {
f[tp] = vst.back();
vst.pop_back();
pos[f[tp][2]] = tp;
}
int l = 1, r = n, res=0;
while (l <= r) {
int mid = l + r >> 1;
if (calc(f[mid], a[i].fi) <= a[i].se) {
res=mid;
l=mid+1;
} else r=mid-1;
}
ans+=res;
}
printf("%lld\n", ans);
return 0;
}