是最劣解！

Bitaro · 2023-11-01 10:45:17 · 题解

哥几个又来体验欧洲风味了。给大家提供一种不用脑子的想法，适合和我一样的青春哥。

这个表达式很神秘，所以我们把这个结构变成一棵二叉树的样子。问号为叶子节点，除了叶子节点以外的每个节点都有属性 opt 代表这个节点代表的运算是 \min 还是 \max。

如果要枚举每个排列然后去重显然不现实，但是发现可能答案只有 n 个，我们只要判断每个答案合不合法就行。

思考答案怎么来的：一个值为答案(题目保证了每个值只有一个)的叶子往上跳，一路过关斩将到了根节点，然后成为答案。

它是怎么过关斩将的呢？设这个值为 u，当跳到一个祖先时，如果祖先的运算为 \max，那它要比另一个儿子大，否则要比另一个儿子小。

现在我们看看它什么时候不合法。对于每个祖先都有一个限制，类似于它必须比另一个儿子大，或者它必须比另一个儿子小。这实际上都是对另一个儿子的值提出了限制。想要满足限制，就必须对儿子子树中的问号的值也提出限制。

限制是啥？实际上我们只关心值是大于 u 还是小于 u。如果小于 u 的数大于 u-1，就必然有限制不能被满足。于是就不合法了。同理，对于大于 u 的数，如果限制大于 n-u 项，也不合法。

于是我们有 f_{i,0/1,0/1} 表示这个点的值比答案小或者大时，小于或者大于的数有多少个，转移很简单，这里以运算为 \max 为例：

对于小于答案的情况，必须两个儿子都小于答案，对于答案大于答案的情况，只要有一个儿子大于答案就行。

求出了这个之后，我们就能一边遍历找出每个点作为答案时的最小的小于它的限制条数 mzero 与最小的大于它的限制条数 mone。根据前文，如果这个节点作为答案 u 且 u-1<mzero 或者 n-u<mone，那么就是不合法的。我们可以求出合法区间 [1+mzero,n-mone]。也就是说这个区间可以作为答案。

我们把所有能作为答案的区间取并就是最终的答案了。可以看到其他题解都要用到好多性质，我们的题解只要用到简单的动态规划。实在是青春至极。

/*
slow is fast
*/
#include<bits/stdc++.h>
#define pre(i,a,b) for(int i=a;i<=b;++i)
#define suf(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N=2e6+6,p=1e9+7;
namespace Y {
string s;
int n,cnt=1,opt[N];
vector<int> e[N];
//1:max,-1:min
//0:< 1:>
#define leaf(u) if(e[u].size()==0)
int f[N][2][2];
void dfs(int u) {
  for(auto v:e[u]) dfs(v);
  leaf(u) {
    f[u][0][0]=1;
    f[u][1][1]=1;
  } else {
    int ls=e[u][0],rs=e[u][1];
    if(opt[u]==1) {
      f[u][0][0]=f[ls][0][0]+f[rs][0][0];
      f[u][0][1]=f[ls][0][1]+f[rs][0][1];
      f[u][1][0]=min({f[ls][1][0]+f[rs][1][0],f[ls][0][0]+f[rs][1][0],f[ls][1][0]+f[rs][0][0]});
      f[u][1][1]=min({f[ls][1][1]+f[rs][1][1],f[ls][0][1]+f[rs][1][1],f[ls][1][1]+f[rs][0][1]});
    } else {
      f[u][0][0]=min({f[ls][0][0]+f[rs][0][0],f[ls][0][0]+f[rs][1][0],f[ls][1][0]+f[rs][0][0]});
      f[u][0][1]=min({f[ls][0][1]+f[rs][0][1],f[ls][0][1]+f[rs][1][1],f[ls][1][1]+f[rs][0][1]});
      f[u][1][0]=f[ls][1][0]+f[rs][1][0];
      f[u][1][1]=f[ls][1][1]+f[rs][1][1];
    }
  }
}
int c[N];
void add(int l,int r) { c[l]++,c[r+1]--; }
void findans(int u,int m0=0,int m1=0) {
  leaf(u) {
    add(1+m0,n-m1);
    return ;
  }
  int ls=e[u][0],rs=e[u][1];
  if(opt[u]==1) {
    findans(ls,m0+f[rs][0][0],m1+f[rs][0][1]);
    findans(rs,m0+f[ls][0][0],m1+f[ls][0][1]);
  } else {
    findans(ls,m0+f[rs][1][0],m1+f[rs][1][1]);
    findans(rs,m0+f[ls][1][0],m1+f[ls][1][1]);
  }
}
void MAIN() {
  cin>>s;
  int u=1;
  stack<int> sta;
  for(int i=0;i<s.size();++i) {
    if(s[i]=='?') { ++n;continue; }
    if(s[i]==')') continue;
    if(s[i]=='m') {
      sta.push(cnt+2);
      e[u].push_back(cnt+1);
      e[u].push_back(cnt+2);
      if(s[i+1]=='a') opt[u]=1;
      else opt[u]=-1;
      u=cnt+1;
      cnt+=2;
      i+=3;
    }
    if(s[i]==',') u=sta.top(),sta.pop();
  }
  dfs(1);
  findans(1);
  int now=0,ans=0;
  pre(i,1,n) {
    now+=c[i];
    if(now) ++ans;
  }
  cout<<ans<<endl;
}
};//namespace Y
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    while(T--) Y::MAIN();
    return 0;
}