题解归档 - cf2223E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2223E
• 本地来源：problems/cf2223E/idea.md
• 题目链接：https://codeforces.com/contest/2223/problem/E
• 原始标题：cf2223E - Zhily and Permutation

思路

cf2223E - Zhily and Permutation

Local Findings

For an interval (l,r), one transition can be answered by two static RMQs:

• ia = argmax a[l+1..r-1];
• ib = argmax b[l+1..r-1];
• next interval is (min(ia, ib), max(ia, ib)).

The sequence contributing to f((l,r),k) is the increasing sequence of left
boundaries on this nested interval chain. Each boundary x contributes either
one zero if p[x] == 0, or p[x] consecutive ones otherwise. Therefore a query
needs the maximum subarray sum over positive-only runs along the first k
states of this chain.

Blocker

Naively simulating the chain is not safe: with a decreasing and b
increasing, (0,n+1) produces l = 0,1,2,..., so one query can have length
Theta(n).

The set of possible next pairs over all intervals is also not small; small
bruteforce reaches all n(n+1)/2 pairs for n<=6, so an explicit interval
state graph is not viable.

Next Attempts

• Find a compression of the nested RMQ chain, likely through the two Cartesian
  trees or a block/jump structure that supports point updates of p.
• Any proposed jump must preserve ordered monoid data:
  prefix positive sum, suffix positive sum, best positive run, total positive
  sum if all positive, and first/last zero status.
• Build a small brute/checker before replacing the current empty shell.

Checks Run

• python tools/math_reasoning_search.py --problem cf2223E -n 8 - required
  math precheck done.
• Local state-count experiments only; no accepted-complexity implementation
  yet.

代码

来源：problems/cf2223E/solution.cpp

/* Author: likely
 * Time: YYYY-MM-DD HH:MM:SS
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll s[maxn+5];
int main(){
    ll t,n,i,j,k,zc,pd,cur,dq,cnt,ans;
    cin>>t;
    while(t--){
        cin>>n;
        for(i=1;i<=n;i++) cin>>s[i];
    }
    return 0;
}