[luogu8293]序列变换

若$s$中存在$)($则总可以扩展为$(A)(B)$，因此最终$s$必然形如$(((\cdots )))$

对括号序列建树，并分析操作的影响——

操作1：选择两个相邻的儿子，将后者及其所有儿子作为前者的儿子

操作2：交换相邻两个儿子，即所有儿子无序

注意到$(((\cdots )))$所对应的树即为一条链，进而操作1需要将所有儿子合并

在此基础上，显然总是从上到下依次处理，这样仅会增加更多的选择，总不劣

具体的，记$T_{i}$为深度为$i$的节点权值集合，则问题转换为以下模型——

初始$S$为空集，$\forall i\in [1,n]$依次执行以下操作：

1.将$T_{i}$加入$S$；2.选择$k\in S$，产生$\begin{cases}(|S|-2)\min_{x\in S}x+k&X=1\\\sum_{x\in S}x-k&Y=1\end{cases}$的代价并删除$k$

注意到$k$恰取遍所有权值，因此与$k$有关的项求和可以直接处理，进而$k$仅代表删除的元素

通常可以贪心删除最大值，但反例在于$|S|=1$时第一项系数为负

当$X=0$时该项不存在，当$X=Y=1$时两项抵消，因此上述贪心均正确

当$X=1$且$Y=0$时，考虑以下做法——

分析$|S|$的形式：对于其第一次递减的位置，在该位置以及之后每一次$|S|$恰减小1

仅考虑$|S|\le 2$的位置，即形如$11\cdots 1\ |\ 22\cdots 2\ |\ 若干\ge 3的元素\ |\ 21$

第1段的选择唯一，可以直接处理，以下不作考虑

第2段中本身无贡献，并枚举结束时$S$中（唯一的）元素$k$，求出对应的值——

第3段中总可以保留极值，进而每一个点的最小值是原最小值与$k$取$\min$，可以差分处理

第4段中$S$初始必然恰包含第3段和$\{k\}$并集的两个极值，进而删除最小值代价即$-最大值$

时间复杂度为$o(n\log n)$（贪心时的set），可以通过

事实上，可以利用$|S|$形式优化掉set，时间复杂度降为$o(n)$

 1 #include
 2 using namespace std;
 3 #define N 400005
 4 #define M 10000005
 5 #define ll long long
 6 int n,X,Y,x,a[N],b[N],tot[M],st[N];
 7 char s[N<<1];vector<int>v[N];
 8 namespace Subtask1{
 9     int cnt;ll sum,ans;
10     set<int>S;set<int>::iterator it;
11     void main(){
12         for(int i=1;i<=n;i++){
13             for(int j:v[i])cnt++,sum+=b[j],S.insert(j);
14             ans+=sum;if (X)ans+=(ll)(cnt-2)*b[*S.begin()];
15             x=(*--S.end()),cnt--,sum-=b[x],S.erase(x);
16         }
17         if (!X){
18             for(int i=1;i<=n;i++)ans-=b[i];
19         }
20         printf("%lld\n",ans);
21     }
22 };
23 namespace Subtask2{
24     int cnt[N],vis[N];ll ans,K[N],B[N];
25     void main(){
26         cnt[1]=v[1].size();
27         for(int i=2;i<=n;i++)cnt[i]=cnt[i-1]+v[i].size()-1;
28         int pos=1;
29         while (cnt[pos]==1)ans-=b[v[pos++][0]];
30         if (pos<=n){
31             if (cnt[pos]==2){
32                 vis[v[pos][0]]=vis[v[pos][1]]=1,pos++;
33                 while (cnt[pos]==2)vis[v[pos++][0]]=1;
34             }
35             int mn=n+1,mx=0;
36             while (cnt[pos]!=1){
37                 for(int i:v[pos])mn=min(mn,i),mx=max(mx,i);
38                 K[mn-1]+=cnt[pos]-2,B[mn]+=(ll)(cnt[pos]-2)*b[mn];
39                 pos++;
40             }
41             for(int i=n;i;i--)K[i]+=K[i+1];
42             for(int i=mx;i<=n;i++)K[i]--;
43             for(int i=1;i<=n;i++)B[i]+=B[i-1];
44             for(int i=1;ib[mx];
45             ll s=B[n]-b[mx];
46             for(int i=1;i<=n;i++)
47                 if (vis[i])s=min(s,K[i]*b[i]+B[i]);
48             ans+=s;
49         }
50         for(int i=1;i<=n;i++)ans+=b[i];
51         printf("%lld\n",ans);
52     }
53 };
54 int main(){
55     scanf("%d%d%d%s",&n,&X,&Y,s+1);
56     for(int i=1;i<=n;i++)scanf("%d",&a[i]),tot[a[i]]++;
57     for(int i=1;i1];
58     for(int i=n;i;i--)b[tot[a[i]]]=a[i],a[i]=tot[a[i]]--;
59     for(int i=1,j=0;i<=(n<<1);i++){
60         if (s[i]=='(')st[++st[0]]=a[++j];
61         else v[st[0]].push_back(st[st[0]]),st[0]--;
62     }
63     if ((!X)&&(!Y))printf("0\n");
64     if (Y)Subtask1::main();
65     if ((X)&&(!Y))Subtask2::main();
66     return 0;
67 }