前置知识

显然，如果一个字母被奇数个括号嵌套，那么它就会改变大小写，否则不变，所以这一步很简单。

那么就剩一个区间反转，使用 FHQ-Treap 维护即可。

代码：

#include<bits/stdc++.h>
#define ls(p) tr[p].son[0]
#define rs(p) tr[p].son[1]
using namespace std;
struct node{
	int son[2];
	int siz;
	char val;
	bool tag;
	int pri;
};
node tr[500005];
int turn[500005];
int id,rt;
mt19937 rd(998535);
int make(char val){
	tr[++id].siz=1;
	tr[id].val=val;
	tr[id].pri=rd();
	return id;
}
void up(int root){
	tr[root].siz=tr[ls(root)].siz+tr[rs(root)].siz+1;
}
void down(int root){
	if(tr[root].tag){
		swap(ls(root),rs(root));
		tr[ls(root)].tag^=1;
		tr[rs(root)].tag^=1;
		tr[root].tag=0;
	}
}
void split(int p,int val,int &x,int &y){
	if(p==0){
		x=y=0;
		return;
	}
	down(p);
	if(tr[ls(p)].siz<val){
		x=p;
		split(rs(p),val-tr[ls(p)].siz-1,rs(p),y);
	}
	else{
		y=p;
		split(ls(p),val,x,ls(p));
	}
	up(p);
}
int merge(int x,int y){
	if(!x || !y){
		return x+y;
	}
	if(tr[x].pri<tr[y].pri){
		down(x);
		rs(x)=merge(rs(x),y);
		up(x);
		return x;
	}
	else{
		down(y);
		ls(y)=merge(x,ls(y));
		up(y);
		return y;
	}
}
void reverse(int l,int r){
	int x,y,z;
	split(rt,l-1,x,y);
	split(y,r-l+1,y,z);
	tr[y].tag^=1;
	rt=merge(merge(x,y),z);
}
void dfs(int root){
	if(!root)return;
	down(root);
	dfs(ls(root));
	cout<<tr[root].val;
	dfs(rs(root));
}
stack<int> st;
int main(){
	string s;
	cin>>s;
	int n=s.size();
	s="#"+s;
	int ji=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='('){
			ji++;
		}
		else if(s[i]==')'){
			ji--;
		}
		else{
			if(ji%2){
				s[i]=(s[i]>='a'?s[i]-'a'+'A':s[i]-'A'+'a');
			}
			rt=merge(rt,make(s[i]));
			turn[i]=id;
		}
	}
	int latest=0;
	for(int i=1;i<=n;i++){
		if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z')){
			latest=turn[i];
		}
		if(s[i]==')'){
			turn[i]=latest;
		}
	}
	for(int i=n;i>=1;i--){
		if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z')){
			latest=turn[i];
		}
		if(s[i]=='('){
			turn[i]=latest;
		}
	}
	for(int i=1;i<=n;i++){
		if(s[i]=='('){
			st.push(turn[i]);
		}
		if(s[i]==')'){
			auto t=st.top();
			st.pop();
			if(t!=0){
				reverse(t,turn[i]);
			}
		}
	}
	dfs(rt);
	return 0;
}