给定长度为 $n$ 的序列 $a_i$，元素两两不相等，等概率随机选一个非空子集 $b_i$。有另一人知道 $a$ 来猜测 $b$，每次可以询问一个 $a_k$，若在 $b$ 中无此数字，则告知“无”，否则告知 $b$ 中所有满足 $a_k^m \bmod p$ 的数（$m$ 为任意正整数）
现每次一定用最优方法猜测，问猜完 $b$ 所有数字的期望次数 $\times (2^n-1)$
$n \le 5000,p \le 10^{8}$，$p$ 为素数或 $q^k$ （$q$ 是素数，$k$ 为一正整数）
有一个 $n \times n$ 的正方形，每行每列都恰好有一个 $1$，计算有多少子正方形满足每行每列恰好有一个 $1$。
$n \le 10^5$
给定一个 $n \times m$ 的 $01$ 矩阵，现在可以无限次对某一行或一列的每个数字取反，求最少的 $1$ 的个数。
$n \le 20\ ,\ m \le 10^5$
题意：
现有 $n\times m$ 的一个矩形，第 $i$ 列有一个代价 $c_i$。如果现在你在 $(x,y)$，可以花费 $x^2$ 的代价到 $(x,y+1)$，或 $c_y$ 的代价到 $(x+1,y)$。
现有 $q$ 次询问，每次给定 $(x_i,y_i)$，求从 $(1,1)$ 到 $(x_i,y_i)$ 的最小代价。
$2\le n\le 10^9,2\le m,q\le 10^5$。
本题解提供两种做法，第一种是 $\text{B}\red{\text{enq}}$ 给出的正解，还有一种是更为无脑的保序回归。由于作者很懒所以只写了第二种的代码
听神仙zzm说本质是一样的 代码还差不多
本部分参照 $\text{B}\red{\text{enq}}$ 在 $\text{USACO}$ 发布的官方题解。
令从 $(1,1)$ 到 $(x,y)$ 的最小代价为 $\text{ans}_y(x)$，那么能够发现，对于一个固定的 $y$，其函数值随着 $x$ 单调增且 $\text{ans}_{y}(x)-\text{ans}_{y}(x-1)\le \text{ans}_{y}(x+1)-\text{ans}_{y}(x)$。可以这样解释：
考虑从 $\text{ans}_y(x)$ 转移到 $\text{ans}_{y+1}(x)$ 的时候：
对于操作 $2$，相当于拿一条斜率为 $c_y$ 的直线去切函数图像，然后把过高的部分砍下来。同时，看到 $1$ 中 $\text{ans}_{y+1}(x)$ 上加了 $x^2$ 就可以大概发现 $\text{ans}_{y}(x)-\text{ans}_{y}(x-1)\le \text{ans}_{y}(x+1)-\text{ans}_{y}(x)$ 的规律。
那么现在可以使用一个栈来维护这样一个类似凸壳的东西，每次在栈里二分找到被直线给砍掉的位置，然后加入一个新点。至于每次的 $1$ 操作，也就是 $+x^2$，可以记录一个时间戳，然后和当前时间戳作差。
是的代码咕了
本部分来自 $\text{zxyhymzg}$ 考场想法。
萌新刚学保序回归 有锅请轻喷
令 $s_i$ 为我们在第 $i$ 行处走到 $(i,s_i)$，其中 $s_0=1$。那么显然有 $s_{i-1}\le s_i$，因为只能向右或者向下走。
计算一下代价，对于从 $(1,1)$ 到 $(x,y)$，$\forall s_i\le x$，代价为：
$$\sum_{i=1}^{y-1} s_i^2+(s_i-s_{i-1})\times c_i$$
后面的部分交换和式，把一项变成只和 $s_i$ 相关：
$$x\times c_y-c_1+\sum_{i=1}^{y-1} s_i^2+(c_i-c_{i+1})\times s_i$$
和式外面是常数，那么只要最小化和式内部。发现是二次函数，先写成顶点式：
$$(s_i-\dfrac{c_{i+1}-c_i}{2})^2-\dfrac{(c_{i+1}-c_i)^2}{4}$$
后面的也是常数，不管。变成最小化：
$$\sum_{i=1}^{y-1} (s_i-\dfrac{c_{i+1}-c_i}{2})^2$$
$\dfrac{c_{i+1}-c_i}{2}$ 是常数，那么就变成了经典的保序回归中的特殊的 $L_2$ 问题，在 $\text{IOI2018}$ 国家候选队论文集中有写到。
需要注意的是，现在对于一个固定的 $y$，发现其 $s_i$ 是固定的。而我们要求 $1\le s_i\le x$，实际上可能会不满足。可以发现将 $s_i$ 向 $[1,x]$ 取整，同时浮点数四舍五入即可。
那么同样的，在保序回归该特殊情况的贪心求解中，我们需要维护一个单调栈，因此对于向 $[1,x]$ 取整的操作可以在单调栈上二分，取整后一段区间的贡献是可以 $\mathcal{O}(1)$ 计算的。
至此即可解决本题，时间复杂度 $\mathcal{O}(n\log n)$，实际上好像效率海星？
$\text{Code:}$
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define debug(x) cout << #x << " = " << x << endl
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define LINE() cout << "LINE = " << __LINE__ << endl
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define vec vector
const int MAXN = 2e5 + 10;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
struct Query {
int x, y, id;
Query(int _x = 0, int _y = 0, int _id = 0) : x(_x), y(_y), id(_id) {}
bool operator < (const Query &b) const {return y < b.y;}
} q[MAXN];
int n, m, qs, top;
int c[MAXN], sum[MAXN], stk[MAXN];
//为了尽量避免浮点数计算，sum数组中先不将c_{i+1}-c_i除2
int Ans[MAXN], num[MAXN], val[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
a *= f;
return 1;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
double aver(int l, int r) {
return 1. * (sum[r] - sum[l - 1]) / (2. * (r - l + 1));
}
int calc(int l, int r, int x) {
if(l > r) return 0;
return x * x * (r - l + 1) - x * (sum[r] - sum[l - 1]);
}
void Insert(int x) {
while(top && aver(stk[top - 1] + 1, stk[top]) + eps > aver(stk[top] + 1, x)) top--;
stk[++top] = x;
num[top] = (int)round(aver(stk[top - 1] + 1, stk[top]));
val[top] = val[top - 1] + calc(stk[top - 1] + 1, stk[top], num[top]);
}
signed main () {
#ifdef FILE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
read(n), read(m);
for(int i = 1; i <= m; ++i) read(c[i]);
for(int i = 1; i <= m; ++i) sum[i] = sum[i - 1] + c[i + 1] - c[i];
read(qs);
for(int i = 1, x, y; i <= qs; ++i) {
read(x), read(y);
q[i] = Query(x, y, i);
}
sort(q + 1, q + qs + 1);
int nowy = 0;
for(int p = 1; p <= qs; ++p) {
if(q[p].y == 1) {
Ans[q[p].id] = (q[p].x - 1) * c[1];
continue;
}
while(nowy + 1 < q[p].y) {
nowy++;
Insert(nowy);
}
Ans[q[p].id] = val[top] + q[p].x * c[q[p].y] - c[1];
int L = 0, R = top, mid;
while(L < R) {
mid = (L + R + 1) >> 1;
if(num[mid] > q[p].x) R = mid - 1;
else L = mid;
}
Ans[q[p].id] += calc(stk[L] + 1, nowy, q[p].x) - (val[top] - val[L]);
L = 1, R = top + 1;
while(L < R) {
mid = (L + R) >> 1;
if(num[mid] <= 0) L = mid + 1;
else R = mid;
}
Ans[q[p].id] += calc(1, stk[L - 1], 1) - val[L - 1];
}
for(int i = 1; i <= qs; ++i)
printf("%lld\n", Ans[i]);
return 0;
}题意：
已知现有一个长 $n$ 的数组，每个数字都是严格小于 $2^b$ 的非负整数，每次可以给定 $i,x$ 来询问 $a_i>x$ 是否成立。
需要在 $3\times(n+b)$ 次询问之内求出数组的最大值。
$n,k\le 200$，交互库自适应。