[ABC350F] Transpose 题解

FFTotoro · 2024-04-21 10:04:13 · 题解

ABC AKed。感觉这个题比暴力可过的 G 更有意义一点。

对于这种题考虑不正经做法。显然对于每个一开始连着的字符串我们需要考虑其大小写与翻转，即考虑它要“出”几次括号，即左边未匹配的括号数。出一次括号大小写变一次，所以它的大小写会变当且仅当其左边有奇数个未匹配的左括号。

发现翻转不好简单地维护，于是考虑暴力。把所有字母确定大小写后抽出来形成一个字母串 L，然后跑括号匹配，匹配到一对就把 L 对应区间抽出来翻转。如何快速翻转字符串？考虑文艺平衡树，但是我不会，所以考虑 __gnu_cxx::rope 暴做（可参考文艺平衡树题解区）。事实证明 5\times 10^5 400ms 无压通过。

放代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  string S; int n=0; cin>>S;
  rope<char> s,d;
  auto rev=[&](int l,int r){
    if(l==r)return; l++,r++;
    rope<char> t=s.substr(s.begin()+l-1,s.begin()+r);
    s=s.substr(s.begin(),s.begin()+l-1)+d.substr(n-r+d.begin(),n-l+d.begin()+1)+s.substr(s.begin()+r,s.end());
    d=d.substr(d.begin(),n-r+d.begin())+t+d.substr(n-l+d.begin()+1,d.end());
  }; // 翻转
  auto ch=[&](char c){
    if(isupper(c))return tolower(c);
    return toupper(c);
  }; // 变大小写
  stack<int> t;
  vector<int> mp(S.length()+1);
  for(int i=0;i<S.length();i++)
    if(isalpha(S[i]))mp[i]=n++; // 抽出字母
  mp[S.length()]=n;
  for(int i=S.length()-1;~i;i--)
    if(!isalpha(S[i]))mp[i]=mp[i+1];
  for(int i=0;i<S.length();i++){
    if(S[i]=='(')t.emplace(i);
    else if(S[i]==')')t.pop();
    else if(t.size()&1)S[i]=ch(S[i]);
  } // 跑第一遍匹配确定大小写
  for(char i:S)
    if(isalpha(i))s.append(i);
  for(int i=S.length()-1;~i;i--)
    if(isalpha(S[i]))d.append(S[i]);
  for(int i=0;i<S.length();i++){
    if(S[i]=='(')t.emplace(i);
    else if(S[i]==')')rev(mp[t.top()],mp[i]-1),t.pop();
  } // 跑第二遍匹配进行翻转
  for(char i:s)cout<<i;
  cout<<endl;
  return 0;
}