怎挖掘网站关键词,繁体版 企业网站,网站开发设计与实现,企业小型网站要多少钱CF653F. Paper task
简要题面
给定括号序列SSS#xff0c;求其中本质不同合法括号序列个数。(∣S∣≤5∗105|S|\leq 5*10^5∣S∣≤5∗105)
Solution
感觉用了一个很麻烦的方法。 我们可以考虑枚举本质不同串的右端点#xff0c;每次动态地在SAMSAMSAM里面加入末尾元素求其中本质不同合法括号序列个数。(∣S∣≤5∗105|S|\leq 5*10^5∣S∣≤5∗105)
Solution
感觉用了一个很麻烦的方法。 我们可以考虑枚举本质不同串的右端点每次动态地在SAMSAMSAM里面加入末尾元素新增的本质不同后缀个数rrr即为lenlst−lenfa[lst]len_{lst}-len_{fa[lst]}lenlst−lenfa[lst]显然新增的本质不同串的起点是[1,r][1,r][1,r]终点是iii。
现在我们考虑有多少起点在[1,r][1,r][1,r]中的序列合法我们对于1..i1..i1..i做一个括号匹配倘若有左括号没被消掉则起点只可能在没消掉的左括号右边令lmax(stk[i])lmax(stk[i])lmax(stk[i])表示最右边的未消掉的左括号。
此时起点在[l1,r][l1,r][l1,r]的串显然只需要满足一个条件——左右括号个数相等即可因为此时左括号个数不可能多于右括号因此建一个线段树维护区间内左右括号个数差即可。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-15;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN500005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
char st[MAXN];
int n,s[MAXN],stk[MAXN],top0;
PR S[MAXN2];
void build(int x,int l,int r)
{if (lr) { S[x]MP(s[l],1); return; }int mid(lr)1;build(x1,l,mid);build(x1|1,mid1,r);S[x].fimin(S[x1].fi,S[x1|1].fi),S[x].se0;if (S[x].fiS[x1].fi) S[x].seS[x1].se;if (S[x].fiS[x1|1].fi) S[x].seS[x1|1].se;
}
PR query(int x,int l,int r,int L,int R)
{if (lLrR) return S[x];int mid(lr)1;if (Rmid) return query(x1,l,mid,L,R);else if (Lmid) return query(x1|1,mid1,r,L,R);else{PR Xquery(x1,l,mid,L,mid),Yquery(x1|1,mid1,r,mid1,R);if (X.fiY.fi) return MP(X.fi,X.seY.se);return (X.fiY.fi)?X:Y;}
}
int len[MAXN1],t[MAXN1][2],fa[MAXN1],sz2,lst1;
void insert(int c)
{int plst,nplstsz;len[np]len[p]1;for (;p!t[p][c];pfa[p]) t[p][c]np;if (!p) { fa[np]1; return; }int qt[p][c];if (len[q]len[p]1) fa[np]q;else{int nqsz;len[nq]len[p]1;fa[nq]fa[q];fa[np]fa[q]nq;memcpy(t[nq],t[q],sizeof t[0]);for (;t[p][c]q;pfa[p]) t[p][c]nq;}
}
signed main()
{nread();scanf(%s,st1);for (int i1;in;i) s[i]s[i-1](st[i](?1:-1);build(1,0,n-1);ll ans0;for (int i1;in;i){if (st[i]() stk[top]i;else if (top) stk[top--]0;int lstk[top]1;insert(st[i]));int rlen[lst]-len[fa[lst]];if (lr){PR tquery(1,0,n-1,l-1,r-1);if (t.fis[i]) anst.se;}}printf(%lld\n,ans);return 0;
}
