A

The problem involves matrices and their properties. The key insight is to treat four types of brackets as distinct invertible matrices.

Two strings can be concatenated if their product equals the identity matrix. While this is a necessary condition, it's not sufficient. However, hashing can serve as an effective heuristic.

We maintain prefix products and their enverses for matrices. Matrix multiplication is non-commutative, so order matters.

A hash map stores these values for efficient lookup.

#include <bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
#define pb push_back
#define pii pair<int,int>
#define st first
#define nd second
#define mpr make_pair
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f^=ch=='-';
    for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
    return f?x:-x;
}
pii operator + (pii x,pii y){return mpr(x.st+y.st,x.nd+y.nd);}
pii operator - (pii x,pii y){return mpr(x.st-y.st,x.nd-y.nd);}
pii operator * (pii x,pii y){return mpr(x.st*y.st,x.nd*y.nd);}
pii operator % (pii x,pii y){return mpr(x.st%y.st,x.nd%y.nd);}
bool operator != (pii x,pii y){return x.st!=y.st||x.nd!=y.nd;}
const int N=5e5+5,inf=1e9;
const pii bas=mpr(2909,3881),mo=mpr(1e9+7,1e9+9);
inline pii qpow(pii x,int t){
    pii ret=mpr(1,1);
    for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
    return ret;
}
inline int fpow(int x,int t,int mo){
    int  ret=1;
    for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
    return ret;
}
int n,m,a[N],l[N],r[N],match[N],rev[N],ans;
char str[N];
map<pii,int> tms;
vector<int> qry[N];
set<int> ban;
pii pw[N],ipw[N];
inline void red(pii &x){
    if(x.st>=mo.st)x.st-=mo.st;
    if(x.nd>=mo.nd)x.nd-=mo.nd;
}
void mul(pii &a,pii b){a=a*b%mo;}
void add(pii &a,pii b){red(a=a+b);}
struct SegmentTree1{
    pii ADD[N<<2],MUL[N<<2];
    void clear(int p,int l,int r){
        ADD[p]=mpr(0,0),MUL[p]=mpr(1,1);
        if(l==r)return;
        int mid=(l+r)>>1;
        clear(lc,l,mid);
        clear(rc,mid+1,r);
    }
    void pushdown(int p){
        mul(MUL[lc],MUL[p]),mul(ADD[lc],MUL[p]);
        mul(MUL[rc],MUL[p]),mul(ADD[rc],MUL[p]);
        add(ADD[lc],ADD[p]),add(ADD[rc],ADD[p]);
        MUL[p]=mpr(1,1),ADD[p]=mpr(0,0);
    }
    void modify(int p,int l,int r,int L,int R,pii d,int t){
        if(L<=l&&r<=R){
            if(t)mul(ADD[p],d),mul(MUL[p],d);
            else add(ADD[p],d);
        }else{
            int mid=(l+r)>>1;
            pushdown(p);
            if(L<=mid)modify(lc,l,mid,L,R,d,t);
            if(mid<R)modify(rc,mid+1,r,L,R,d,t);
        }
    }
    pii query(int p,int l,int r,int x){
        if(l==r)return ADD[p];
        pushdown(p);
        int mid=(l+r)>>1;
        if(x<=mid)return query(lc,l,mid,x);
        else return query(rc,mid+1,r,x);
    }
}Tree;
struct SegmentTree2{
    pii hash[N<<2];
    int siz[N<<2];
    void clear(int p,int l,int r){
        hash[p]=mpr(0,0);
        siz[p]=0;
        if(l==r)return;
        int mid=(l+r)>>1;
        clear(lc,l,mid);
        clear(rc,mid+1,r);
    }
    void pushup(int p){
        siz[p]=siz[lc]+siz[rc];
        red(hash[p]=hash[lc]+pw[siz[lc]]*hash[rc]%mo);
    }
    void insert(int p,int l,int r,int x,int t,int v){
        if(l==r){
            if(t)hash[p]=mpr(v,v),siz[p]=1;
            else hash[p]=mpr(0,0),siz[p]=0;
        }else{
            int mid=(l+r)>>1;
            if(x<=mid)insert(lc,l,mid,x,t,v);
            if(mid<x)insert(rc,mid+1,r,x,t,v);
            pushup(p);
        }
    }
    pii query(){return hash[1];}
}arr;
int sgn(char x){
    return x=='('||x=='['||x=='{'||x=='<';
}
int mth(char x,char y){
    if(!sgn(x))return 0;
    if(x=='(')return y==')';
    else if(x=='[')return y==']';
    else if(x=='{')return y=='}';
    else return y=='>';
}
int mp(char x){
    if(x=='(')return 2;
    else if(x=='[')return 3;
    else if(x=='{')return 5;
    else return 7;
}
void debug(pii x){printf("<%lld,%lld>\n",x.st,x.nd);}
void work(int turns){
    for(int i=1;i<=n;++i){
        match[i]=rev[i]=0;
        qry[i].clear();
    }
    for(int i=1;i<=m;++i)qry[l[i]].pb(r[i]);
    str[n+1]='*',match[n+1]=-(n+1);
    for(int i=n;i>=1;--i){
        if(sgn(str[i])){
            int pos=i+1;
            while(sgn(str[pos])&&match[pos]>0)
                pos=match[pos]+1;
            if(sgn(str[pos]))match[i]=match[pos];
            else match[i]=mth(str[i],str[pos])?pos:-pos;
            if(match[i]>0)rev[match[i]]=i;
        }
    }
    ban.clear();
    for(int i=1;i<=n;++i)
        if(!sgn(str[i])&&!rev[i])ban.insert(i);
    arr.clear(1,1,n),Tree.clear(1,1,n);
    for(int i=1;i<=n;++i){
        if(sgn(str[i]))
            arr.insert(1,1,n,i,1,mp(str[i]));
        else if(rev[i])
            arr.insert(1,1,n,rev[i],0,0);
        Tree.modify(1,1,n,i,i,arr.query(),0);
    }
    for(int i=1;i<=n;++i){
        int f=ban.empty()?n+1:(*ban.begin());
        for(int x:qry[i])if(x<f){
            if(turns==1){
                pii cnm=Tree.query(1,1,n,x);
                ++tms[cnm];
            }
            if(turns==2){
                pii tmp=Tree.query(1,1,n,x);
                if(tmp!=mpr(0,0)&&tms[tmp]>0){
                    --tms[tmp];
                    ++ans;
                }
            }
        }
        while(ban.size()&&(*ban.begin())<=i)
            ban.erase(ban.begin());
        if(sgn(str[i])){
            pii d=mo-mpr(mp(str[i]),mp(str[i]));
            if(match[i]>0){
                ban.insert(match[i]);
                Tree.modify(1,1,n,i,match[i]-1,d,0);
                Tree.modify(1,1,n,i,match[i]-1,ipw[1],1);
            }else{
                Tree.modify(1,1,n,i,n,d,0);
                Tree.modify(1,1,n,i,n,ipw[1],1);
            }
        }
    }
    if(turns==2)ans+=tms[mpr(0,0)]/2;
}
int flip(char x){
    if(x=='(')return ')';
    else if(x==')')return '(';
    else if(x=='[')return ']';
    else if(x==']')return '[';
    else if(x=='{')return '}';
    else if(x=='}')return '{';
    else if(x=='<')return '>';
    else return '<';
}
void solve(){
    n=read(),m=read();
    scanf("%s",str+1);
    for(int i=1;i<=m;++i){
        l[i]=read(),r[i]=read();
    }
    ans=0;
    tms.clear();
    work(1);
    for(int i=1;i<=n;++i)str[i]=flip(str[i]);
    for(int i=1;i<=n;++i)if(i<=n-i+1)
        swap(str[i],str[n-i+1]);
    for(int i=1;i<=m;++i){
        l[i]=n+1-l[i],r[i]=n+1-r[i];
        swap(l[i],r[i]);
    }
    work(2);
    printf("%lld\n",ans);
}
signed main(){
    pw[0]=ipw[0]=mpr(1,1);
    for(int i=1;i<N;++i){
        pw[i]=pw[i-1]*bas%mo;
        if(i==1){
            ipw[i].st=fpow(pw[i].st,mo.st-2,mo.st);
            ipw[i].nd=fpow(pw[i].nd,mo.nd-2,mo.nd);
        }
    }
    int u=read();
    for(int G=1;G<=u;++G){
        solve();
    }
}

B

To sort a range in ascending order such that: $$ \begin{align} &a_i + a_{m-i+1} = a_1 + a_m \ \iff & a_i = (a_1 + a_m) - a_{m-i+1} \end{align} $$

Define $ b_i = -a_i $. Then: $$ \begin{align} a_i - b_i = a_1 + a_m \end{align} $$

For dynamic maintenance, we use generating functions: $$ F_{[l,r]}(x) = \sum_{i\in[l,r]} x^{a_i},\quad G_{[l,r]}(x) = \sum_{i\in[l,r]} x^{b_i} $$

Check if: $$ F_{[l,r]}(x) \equiv G_{[l,r]}(x) \cdot x^{a_1 + a_m} $$

Instead of full polynomials, use hash values at random points.

C

Consider derangements:

If $ n $ is even, the minimal derangement swaps adjacent pairs.

If $ n $ is odd, there exists a triple $ (2r+1, 2r+2, 2r+3) $ that cycles, with others swapped.

Each derangement corresponds to $ (r, 0/1) $.

Use greedy approach to find the k-th lexicographical one, maintaining segment tree for constraints.

D

Use $ n+1 $ dynamic segment trees. Index 0 represents free space, others represent occupied segments.

Operations may add up to $ O(n) $ new segments. Each split creates $ O(\log n) $ nodes. Total nodes are bounded by $ O(n \log n) $.

Merge operations take time proportional to deleted nodes. Queries use a set of segments to locate positions efficiently.

E

Standard segment tree merging template.

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f^=ch=='-';
    for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
    return f?x:-x;
}
inline void chmax(int &x,int y){x=max(x,y);}
const int N=2e5+5,LOG=20,S=1e7+5;
struct SegmentTree{
    int lc[S],rc[S],f[S],g[S],pool;
    void pushdown(int p){
        if(!g[p])return;
        if(lc[p]){
            f[lc[p]]+=g[p];
            g[lc[p]]+=g[p];
        }
        if(rc[p]){
            f[rc[p]]+=g[p];
            g[rc[p]]+=g[p];
        }
        g[p]=0;
    }
    void pushup(int p){
        if(lc[p])chmax(f[p],f[lc[p]]);
        if(rc[p])chmax(f[p],f[rc[p]]);
    }
    void insert(int &p,int l,int r,int x){
        if(!p)p=++pool;
        if(l==r)return;
        int mid=(l+r)>>1;
        if(x<=mid)insert(lc[p],l,mid,x);
        else insert(rc[p],mid+1,r,x);
    }
    void modify(int p,int l,int r,int L,int R,int d){
        if(!p)return;
        if(L<=l&&r<=R){
            f[p]+=d;
            g[p]+=d;
            return;
        }
        pushdown(p);
        int mid=(l+r)>>1;
        if(L<=mid)modify(lc[p],l,mid,L,R,d);
        if(mid<R)modify(rc[p],mid+1,r,L,R,d);
        pushup(p);
    }
    int ask(int p){return f[p];}
    int query(int p,int l,int r,int L,int R){
        if(!p)return 0;
        if(L<=l&&r<=R)return f[p];
        pushdown(p);
        int mid=(l+r)>>1,ret=0;
        if(L<=mid)chmax(ret,query(lc[p],l,mid,L,R));
        if(mid<R)chmax(ret,query(rc[p],mid+1,r,L,R));
        return ret;
    }
    void merge(int &p,int q,int l,int r){
        if(!p||!q)p|=q;
        else{
            if(l==r){
                chmax(f[p],f[q]);
                return;
            }
            int mid=(l+r)>>1;
            pushdown(p);
            pushdown(q);
            merge(lc[p],lc[q],l,mid);
            merge(rc[p],rc[q],mid+1,r);
            pushup(p);
        }
    }
}Tree;
vector<pii> edge[N],oper[N];
vector<int> v[N],l[N];
int dist[N],nxt[N][LOG],n,m,root[N],k[N],s[N];
void dfs1(int u,int fa){
    nxt[u][0]=fa;
    for(int i=1;i<LOG;++i)
        nxt[u][i]=nxt[nxt[u][i-1]][i-1];
    for(auto [v,w]:edge[u])if(v!=fa){
        dist[v]=dist[u]+w;
        dfs1(v,u);
    }
}
int FIND(int x,int len){
    int y=x;
    for(int i=LOG-1;i>=0;--i){
        if(dist[x]-dist[nxt[y][i]]<len)
            y=nxt[y][i];
    }
    return y;
}
void dfs2(int u,int fa){
    int tot=0;
    for(auto [v,w]:edge[u])if(v!=fa){
        dfs2(v,u);
        tot+=Tree.ask(root[v]);
    }
    Tree.modify(root[u],1,m,1,m,tot);
    for(auto [v,w]:edge[u])if(v!=fa){
        int x=tot-Tree.ask(root[v]);
        Tree.modify(root[v],1,m,1,m,x);
        Tree.merge(root[u],root[v],1,m);
    }
    for(auto [id,val]:oper[u])
        Tree.modify(root[u],1,m,id,id,val);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<n;++i){
        int x=read(),y=read(),w=read();
        edge[x].pb(mpr(y,w));
        edge[y].pb(mpr(x,w));
    }
    dfs1(1,0);
    for(int i=1;i<=m;++i){
        k[i]=read(),s[i]=read(); 
        v[i].resize(k[i]+1,0);
        l[i].resize(k[i]+1,0);
        for(int j=1;j<=k[i];++j)v[i][j]=read();
        for(int j=1;j<=k[i];++j){
            l[i][j]=read()+l[i][j-1];
            oper[FIND(s[i],l[i][j])].pb(mpr(i,v[i][j]));
        }
        Tree.insert(root[s[i]],1,m,i);
    }
    dfs2(1,0);
    printf("%lld\n",Tree.ask(root[1]));
}

F

Block-based optimization. For sequence $ b_i = \gcd(i, b_i) $, modifications are limited to $ O(n \log \log n) $ due to prime factorizations.

Maintain block state with jump positions and accumulated weights. Update blocks when needed with complexity $ O(B) $ where $ B = 400 $.

G

Track blue ball intervals using segment tree merging to handle updates efficiently.

H

Suffix GCDs have at most $ \log $ unique values. Use a set to track them.

#include <bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
#define pb push_back
#define pii pair<int,int>
#define st first
#define nd second
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f^=ch=='-';
    for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
    return f?x:-x;
}
mt19937 rnd(time(0));
const int mo=998244353;
inline int qpow(int x,int t){
    int ret=1;
    for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
    return ret;
}
inline void red(int &x){x>=mo?x-=mo:0;}
inline void chmin(int &x,int y){x=min(x,y);}
inline void chmax(int &x,int y){x=max(x,y);}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
const int N=2e5+5;
set<pair<int,pii>> pos,tmp;
int a[N],b[N],gcda[N],gcdb[N],sufA[N],sufB[N],n;
void opf(pii &a,pii b){
    if(a.st==b.st)a.nd+=b.nd;
    else a=max(a,b);
}
void solve(){
    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        gcda[i]=gcd(gcda[i-1],a[i]);
    }
    for(int i=1;i<=n;++i){
        b[i]=read();
        gcdb[i]=gcd(gcdb[i-1],b[i]);
    }
    sufA[n+1]=sufB[n+1]=0;
    for(int i=n;i;--i){
        sufA[i]=gcd(sufA[i+1],a[i]);
        sufB[i]=gcd(sufB[i+1],b[i]);
    }
    pii ans={0,0};
    pos.clear();
    for(int i=1;i<=n;++i){
        tmp.clear();
        for(auto [u,v]:pos){
            int x=v.st,y=v.nd;
            tmp.insert({u,{gcd(x,a[i]),gcd(y,b[i])}});
        }
        tmp.insert({i,{gcd(a[i],gcdb[i-1]),gcd(b[i],gcda[i-1])}});
        pos.clear();
        for(set<pair<int,pii>>::iterator it1=tmp.begin(),it2;it1!=tmp.end();it1=it2){
            it2=it1;
            it2++;
            while(it2!=tmp.end()&&(*it1).nd==(*it2).nd)it2++;
            it2--;
            pos.insert(*it1);
            it2++;
        }
        for(set<pair<int,pii>>::iterator it=pos.begin();it!=pos.end();){
            int x=(*it).nd.st,y=(*it).nd.nd,A,B;
            A=gcd(x,sufB[i+1])+gcd(y,sufA[i+1]);
            B=-(*it).st;
            ++it;
            if(it==pos.end())B+=i+1;
            else B+=(*it).st;
            opf(ans,{A,B});
        }
    }
    printf("%lld %lld\n",ans.st,ans.nd);
    return;
}
signed main(){
    for(int cas=read();cas--;)
        solve();
    return 0;
}

I

Relative order determines divisibility. In Cartesian trees, parent divides children.

Enumerate potential $ x $ values based on factor counts. Check conditions on Cartesian tree.

J

Greedy algorithm combined with bit manipulation solves the problem.