Solution. NOI Online 2022
上午自己打 NOIO，反正考的相当不太行，分数倒也不是太重要，但是至少觉得自己现在实力，尤其是思维能力实在是有待提高。
丹钓战
首先注意到丹钓战是单调栈的谐音。
一开始读题没读清楚，因为各种原因一度想用莫队做，实际上这个题简直简单到离谱。
从头到尾用单调栈把题目描述的过程跑一遍，然后对于第 $i$ 个元素我们记录在 pop 后栈顶元素的下标 $pre_i$。换言之，我们记录的就是 push 当前元素会使得哪些元素被弹出。
接下来，容易发现，在查询区间 $[l,r]$ 时，二元组 $i\in[l,r]$ 会对答案造成贡献当且仅当 $pre_i<l$。
于是做法也就显而易见了，我们希望查询 $[l,r]$ 中 $pre_i<l$ 的二元组个数，可以使用主席树进行维护。
离线做法更为简单，再将序列扫一遍，用一个树状数组对 $pre$ 进行计数，扫到 $i$ 的时候，对于所有 $l=i-1$ 的询问记录负贡献，$r=i$ 的记录正贡献。
复杂度 $O(n\log n)$。
namespace Main{
const int N = 500005;
int n, q, pre[N], ans[N];
pair<int, int> a[N];
stack<int> stk;
vector<int> ql[N];
vector<pair<int, int>> qr[N];
struct bit{
int t[N];
inline int lowbit(int x) { return x & -x; }
void add(int x) { for(int i = x; i < N; i += lowbit(i)) t[i]++; }
int query(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += t[i]; return res; }
}tree;
void Main(){
input(n, q);
for(int i = 1; i <= n; i++) input(a[i].first);
for(int i = 1; i <= n; i++) input(a[i].second);
for(int i = 1; i <= n; i++){
while(!stk.empty() && (a[stk.top()].first == a[i].first || a[stk.top()].second <= a[i].second)) stk.pop();
pre[i] = stk.empty() ? 0 : stk.top();
stk.push(i);
// cerr << pre[i] << ' ';
}
for(int i = 0, l, r; i < q; i++){
input(l, r);
ql[l-1].push_back(i);
qr[r].emplace_back(l, i);
}
for(int i = 1; i <= n; i++){
tree.add(pre[i] + 1);
for(int t: ql[i]) ans[t] -= tree.query(i + 1);
for(pair<int, int> t: qr[i]) ans[t.second] += tree.query(t.first);
}
for(int i = 0; i < q; i++) write(ans[i]), puts("");
return;
}
} // namespace值得一提的是这个题的思考方式，一方面很 naive，一方面也很有价值（至少对我而言），看了一下 fz 的 NOIO 游记似乎 fz 也没有做出来 t1，但是也有人发出 t1 应该评绿的暴论。
考虑这样一件事情，如果题目问的是，给出序列 $\{a_n\}$，每次抽出一个区间 $[l,r]$，询问其中有多少个数 $a_i$ 满足 $\forall j\in(i,r],\ a_i\ge a_j$。
容易发现，两个问题的本质是一样的。正难则反，一个数后面的所有数都没有自己大，也就意味着第一个比自己大的数在当前询问区间的后面，这个用单调栈可以轻而易举的解决，原题同理，本质上就是一个简单的转化。
讨论
这也应该是一个简单题。
题目给出的限制条件其实非常弱，考虑将集合从大到小排序，这样的话我们只需要保证后面的集合与前面的集合有交且不被包含，这一对集合就是满足题意的。
于是不难想到在从前往后遍历所有集合时，我们维护 $p_i$ 表示 $i$ 在第 $p_i$ 个集合中出现过。考虑当前集合 $S$，如果 $\forall a,b\in S$ 都有 $p_a=p_b$，那么 $S$ 被某个集合包含，或者 $S$ 与之前的所有集合不交（当且仅当 $\forall a\in S,\ p_a=0$），否则我们找到了一组合法解，输出即可。
这里注意一下细节，如果 $S$ 被包含，我们应该覆盖原来的标记而不是保留。
复杂度看起来像 $O(n^2)$，实际上是优秀的 $O(n+\sum k_i)=O(n+m)$
namespace Main{
const int N = 1000005;
int t, n, k[N], p[N];
pair<int, vector<int>> a[N];
void Main(){
input(t);
while(t--){
for(int i = 0; i < n; i++) a[i].second.clear();
memset(p, -0x3f, sizeof(p));
input(n);
for(int i = 0; i < n; i++){
input(k[i]);
a[i].first = i + 1;
for(int j = 0; j < k[i]; j++) a[i].second.push_back(read<int>());
// for InfOJ
sort(a[i].second.begin(), a[i].second.end());
a[i].second.erase(unique(a[i].second.begin(), a[i].second.end()), a[i].second.end());
}
sort(a, a + n, [](auto a, auto b){
return a.second.size() > b.second.size();
});
bool flag = false;
for(int i = 0; i < n && !flag; i++){
int num = -1;
for(int x: a[i].second){
if(num == -1) num = p[x];
else if(num != p[x]){
puts("YES");
write(a[i].first), putchar(' '), write(a[max(num, p[x])].first);
puts("");
flag = true;
break;
}
p[x] = i;
}
}
if(!flag) puts("NO");
}
return;
}
} // namespace如何正确的排序
$m=2$ 时答案为 $2n\sum a_{i,j}$，不多赘述。
$m=3$ 时考虑转化为求 $g(i,j)=a_{k,i}+a_{k,j}$ 使得 $a_{x,i}+a_{x,j}\le g(i,j)\le a_{y,i}+a_{y,j}$。
咕
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
