CF1976D Invertible Bracket Sequences Solution

提供一种不同的做法。

将 ( 看作

1

，) 看作

-1

。设

s_i

表示前缀和，特殊的，规定

s_0=0

。

若

[l,r]

合法当且仅当

s_{l-1}-\max_{l\le i\le r}s_i\ge 0

，且

s_{l-1}=s_r

。

按

s

的最值分治，设

[L,R]

的最值点为

mid

，用 ST 表维护容易。按照套路，枚举较短的一边，另一边数据结构处理。

以枚举

l

为例，首先要满足

s_{l-1}-s_{mid}\ge 0

，然后相当于查询

[mid,R]

中有多少个

s_r=s_{l-1}

，用主席树容易维护。

枚举

r

同理，注意

s

有负数，在主席树上需要整体位移

n

个单位长度。

时间复杂度

O(n\log n\log V)

，可以通过本题。

余望余之神迹，搔首对天长叹，复高吟一绝云：

轮扁斫轮亦有言，应心妙处不可传。但能付汝皆糟粕，何必孜孜学圣贤！

CPP

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}

const int MOD(1e9+7);
template<typename T>
inline T add(T x){return x;}
template<typename T,typename... types>
inline T add(T x,types... y){T z=add<T>(y...);return x+z>=MOD?x+z-MOD:x+z;}
template<typename T>
inline T mul(T x){return x;}
template<typename T,typename... types>
inline T mul(T x,types... y){return (ll)x*mul<T>(y...)%MOD;}
inline int sub(int x,int y){return add(x-y,MOD);}

const int MAXN(2e5+10);

int n;
char t[MAXN];
int s[MAXN];
int T;

struct ST
{
	int st[MAXN][20],lg[MAXN];
	inline int cmp(int x,int y){return s[x]>s[y]?x:y;}
	inline void build()
	{
		lg[0]=-1;
		rep(i,1,n) st[i][0]=i,lg[i]=lg[i>>1]+1;
		rep(j,1,lg[n]) rep(i,1,n-(1<<j)+1) st[i][j]=cmp(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		return;
	} 
	inline int query(int x,int y)
	{
		int k=lg[y-x+1];
		return cmp(st[x][k],st[y-(1<<k)+1][k]);
	}
};
ST st;

int rt[MAXN];

namespace seg
{
	struct T{int ls,rs,sum;};
	T tree[MAXN*60];
	int tot;
	
	inline void init_()
	{
		rep(i,0,n+1) rt[i]=0;
		rep(i,0,tot) tree[i].ls=0,tree[i].rs=0,tree[i].sum=0;
		tot=0;
		return; 
	}
	
	inline int lc(int p){return tree[p].ls;}
	inline int rc(int p){return tree[p].rs;}
	
	inline void update(int&u,int pre,int l,int r,int p)
	{
		u=++tot;
		tree[u]=tree[pre];
		tree[u].sum++;
		if(l==r) return;
		int mid=(l+r)>>1; 
		if(p<=mid) update(tree[u].ls,lc(pre),l,mid,p);
		else update(tree[u].rs,rc(pre),mid+1,r,p);
		return;
	}
	
	inline int query(int u,int l,int r,int p)
	{
		if(!u) return 0;
		if(l==r) return tree[u].sum;
		int mid=(l+r)>>1;
		if(p<=mid) return query(lc(u),l,mid,p);
		else return query(rc(u),mid+1,r,p);
	}
}

inline int query(int l,int r,int k)
{
	if(l>r) return 0;
	else if(l-1<0) return seg::query(rt[r],0,n<<1,k+n);
	else return seg::query(rt[r],0,n<<1,k+n)-seg::query(rt[l-1],0,n<<1,k+n);
}

inline ll CDQ(int l,int r)
{
	if(l>=r) return 0ll;
	int mid=st.query(l,r);
	ll ans=0;
	if(mid-l<r-mid){rep(i,l,mid) if(2*s[i-1]-s[mid]>=0) ans+=query(mid,r,s[i-1]);} 
	else{rep(i,mid,r) if(2*s[i]-s[mid]>=0) ans+=query(l-1,mid-1,s[i]);} 
	return ans+CDQ(l,mid-1)+CDQ(mid+1,r);
}

inline void solve()
{
	scanf("%s",t+1);
	getchar();
	n=strlen(t+1);
	rep(i,1,n) s[i]=s[i-1]+(t[i]=='('?1:-1);
	st.build();
	seg::init_();
	seg::update(rt[0],rt[n+1],0,n<<1,0);
	rep(i,1,n) seg::update(rt[i],rt[i-1],0,n<<1,s[i]+n);
	printf("%lld\n",CDQ(1,n));
	return;
}

int main()
{
	T=read();
	while(T--) solve();
	return 0;
}

CF1976D Invertible Bracket Sequences Solution

文章操作

CF1976D Invertible Bracket Sequences Solution

相关推荐

评论

CF1976D Invertible Bracket Sequences Solution