ABC 350F

没有 push_down 调了 15 分钟，然后在赛后 7 分钟过的，中间看到E是期望题就去打舟了，哎，再也不摆了（期望能不能别再出现了）

翻转?这我熟，fhq 啊!然后大写变小写?简单，再 lazytag 搞一下就好了。时间复杂度 \(O(n \log n)\)，带一个大常数，但是绰绰有余。

#include<bits/stdc++.h>
#define for1(i,a,b) for( int i=(a);i<=(b);i++)
#define for2(i,a,b) for( int i=(a);i<(b);i++)
#define for3(i,a,b) for( int i=(a);i>=(b);i--)
#define for4(i,a,b) for( int i=(a);i>(b);i--)
#define mx(a,b) max(a,b)
#define mn(a,b) min(a,b)
#define puba push_back
#define mem(a) memset((a),0,sizeof((a)))
#define int long long
using namespace std;
string s;
struct node{
   int rd;
   char val;
}p[500005];
int root,siz[500005],son[500005][2],la[500005],cnt=0,rx,ry,rz;
int stk[500005],top,pre[500005],nxt[500005];
void update(int rt){
	siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+1;
}
void change(char &x){
    if(x>='a'&&x<='z') x=x-'a'+'A';
    else x=x-'A'+'a';
}
void push_down(int rt){
    if(la[rt]){
        change(p[son[rt][0]].val);
        change(p[son[rt][1]].val);
        la[son[rt][0]]^=1;
        la[son[rt][1]]^=1;
        swap(son[rt][0],son[rt][1]);
        la[rt]=0;
    }
}
int add(char x){
	cnt++;
	siz[cnt]=1;
	p[cnt].val=x;
	p[cnt].rd=rand();
	return cnt;
}
void split(int rt,int siz1,int &x,int &y) {
	if(!rt){
		x=y=0;
		return;
	}
    push_down(rt);
    if(siz[son[rt][0]]>=siz1){
		y=rt;
		split(son[rt][0],siz1,x,son[rt][0]);
	}else{
		x=rt;
		split(son[rt][1],siz1-(siz[son[rt][0]]+1),son[rt][1],y);
	}
	update(rt);
}
int merge(int l,int r){
	if(!l||!r) return l+r;
    push_down(l);
    push_down(r);
	if(p[l].rd<p[r].rd){
		son[l][1]=merge(son[l][1],r);
		update(l);
		return l;
	}else{
		son[r][0]=merge(l,son[r][0]);
		update(r);
		return r;
	}
}
void dfs(int u){
    if(!u) return;
    push_down(u);
    dfs(son[u][0]);
    cout<<p[u].val;
    dfs(son[u][1]);
}
signed main(){
    srand(time(0));
    cin>>s;
    int len=s.size(),tot=0;
    for2(i,0,len){
        if(s[i]!='('&&s[i]!=')'){
            tot++;
            root=merge(root,add(s[i]));
        }
    }
    int st=tot+1;
    for3(i,len-1,0){
        if(s[i]!=')'&&s[i]!='(') st--;
        if(s[i]=='(') nxt[i]=st;
    }
    st=0;
    for2(i,0,len){
        if(s[i]!=')'&&s[i]!='(') st++;
        if(s[i]==')') pre[i]=st;
    }
    for2(i,0,len){
        if(s[i]=='('){
            top++;
            stk[top]=nxt[i];
        }if(s[i]==')'){
            int x=stk[top],y=pre[i];
            top--;
            split(root,x-1,rx,ry);
            split(ry,y-x+1,ry,rz);
            la[ry]^=1;
            change(p[ry].val);
            root=merge(merge(rx,ry),rz);
        }
    }
    dfs(root);
    
    
    return 0;
}