求助玄关:大样例能过,全WA:第一行太短。
  • 板块P10513 括号
  • 楼主I_sland
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/31 01:30
  • 上次更新2024/5/31 15:10:45
查看原帖
求助玄关:大样例能过,全WA:第一行太短。
1110135
I_sland楼主2024/5/31 01:30

求助各位大佬,小样例,大样例全过,交上去全部测试点都是WA:too short on line 1

#include<bits/stdc++.h> 
#define N 500050
using namespace std;
typedef long long ll;
struct U{
	ll a,b,c,d,e,f;
};
struct V{
	U u;
	ll L,R;
};
V tr[4*N];
ll lazy[4*N];
ll inp[N];
void pushup(ll k){
	U u1=tr[2*k].u;
	U u2=tr[2*k+1].u;
	tr[k].u.a=u1.a+u2.a+min(u1.c,u2.d);
	tr[k].u.c=u1.c+u2.c-min(u1.c,u2.d);
	tr[k].u.d=u1.d+u2.d-min(u1.c,u2.d);
	
	tr[k].u.b=u1.b+u2.b+min(u1.e,u2.f);
	tr[k].u.e=u1.e+u2.e-min(u1.e,u2.f);
	tr[k].u.f=u1.f+u2.f-min(u1.e,u2.f);
}
void pushdown(ll k){
	if(lazy[k]){
		swap(tr[2*k].u.a,tr[2*k].u.b);
		swap(tr[2*k].u.d,tr[2*k].u.f);
		swap(tr[2*k].u.c,tr[2*k].u.e);
		swap(tr[2*k+1].u.a,tr[2*k+1].u.b);
		swap(tr[2*k+1].u.d,tr[2*k+1].u.f);
		swap(tr[2*k+1].u.c,tr[2*k+1].u.e);
		lazy[k]=0;
		lazy[2*k]=!lazy[2*k];
		lazy[2*k+1]=!lazy[2*k+1];
	}
}
void build(ll k,ll l,ll r){
	tr[k].L=l;
	tr[k].R=r;
	if(l==r){
		tr[k].u.a=tr[k].u.b=0;
		if(inp[l]){
			tr[k].u.d=tr[k].u.e=0;
			tr[k].u.c=tr[k].u.f=1;
		}else{
			tr[k].u.d=tr[k].u.e=1;
			tr[k].u.c=tr[k].u.f=0;
		}
	}else{
		ll mid=(l+r)/2;
		build(2*k,l,mid);
		build(2*k+1,mid+1,r);
		pushup(k);
	}
} 
void change(ll k,ll sl,ll sr){
	ll L=tr[k].L;
	ll R=tr[k].R;
	if(sl<=L && R<=sr){
		swap(tr[k].u.a,tr[k].u.b);
		swap(tr[k].u.d,tr[k].u.f);
		swap(tr[k].u.c,tr[k].u.e);
		lazy[k]=!lazy[k];
		return;
	}
	pushdown(k);
	ll mid=(L+R)/2;
	if(sl<=mid){
		change(2*k,sl,sr);
	}
	if(mid+1<=sr){
		change(2*k+1,sl,sr);
	}
	pushup(k);
}
U get(ll k,ll sl,ll sr){
	ll L=tr[k].L;
	ll R=tr[k].R;
	if(sl<=L && R<=sr){
		U u=tr[k].u;
		//cout<<L<<" "<<R<<" = "<<u.a<<" "<<u.b<<" "<<u.c<<" "<<u.d<<" "<<u.e<<" "<<u.f<<" "<<endl;
		return tr[k].u;
	}
	pushdown(k);
	U u1,u2,u;
	u1.a=0;u1.b=0;u1.c=0;u1.d=0;u1.e=0;u1.f=0;u2.a=0;u2.b=0;u2.c=0;u2.d=0;u2.e=0;u2.f=0;u.a=0;u.b=0;u.c=0;u.d=0;u.e=0;u.f=0;
	ll mid=(L+R)/2;
	if(sl<=mid){
		u1=get(2*k,sl,sr);
	}
	if(mid+1<=sr){
		u2=get(2*k+1,sl,sr);
	}
	u.a=u1.a+u2.a+min(u1.c,u2.d);
	u.c=u1.c+u2.c-min(u1.c,u2.d);
	u.d=u1.d+u2.d-min(u1.c,u2.d);
	//cout<<L<<" "<<R<<"="<<u.a<<" "<<u.b<<" "<<u.c<<" "<<u.d<<" "<<u.e<<" "<<u.f<<" "<<endl;
	return u;
}
int main(){
	ios::sync_with_stdio(false);  
	ll n,m;cin>>n;
	char cc;
	for(int i=1;i<=n;i++){
		scanf("%c",&cc);
		if(cc=='('){
			inp[i]=1;
		}
	}
	build(1,1,n);
	
//	for(int i=1;i<=4*n;i++){
//		cout<<i<<' '<<tr[i].L<<" "<<tr[i].R<<"="<<tr[i].u.a<<" "<<tr[i].u.b<<" "<<tr[i].u.c<<" "<<tr[i].u.d<<" "<<tr[i].u.e<<" "<<tr[i].u.f<<" "<<endl;
//	}

	cin>>m;
	while(m--){
		ll op,sl,sr;
		scanf("%lld%lld%lld",&op,&sl,&sr);
		if(op==1){
			change(1,sl,sr);
		}else{
			U u=get(1,sl,sr);
			cout<<u.a<<endl;
		}
	}
	return 0;
}
2024/5/31 01:30
加载中...