A

矩陣死了！

這個題是個科技題，但其實也有貪心的哈希做法，只是過于復雜了

聯想一下什么東西像括號一樣，沒有交換律的？是矩陣！

考慮欽定四種左括號分別對應四種不同的可逆矩陣，然后兩個串可合并的必要條件是乘積為單位陣

注意到這是必要條件而非充要條件，但是眾所周知哈希也是必要條件

如果擔心撞的話，可以考慮多兩組

所以只需維護矩陣的前綴積和矩陣前綴積的逆即可，注意矩陣運算無交換律

然后再對矩陣維護哈希表就行了

#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){
    // printf("This is the %lldth TURNS\n\n",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);
                // printf("[%lld,%lld]=",i,x);debug(cnm);
                // for(int j=i;j<=x;++j)putchar(str[j]);puts("");
                ++tms[cnm];
            }
            if(turns==2){
                pii tmp=Tree.query(1,1,n,x);
                // printf("[%lld,%lld]=",i,x);debug(tmp);
                // for(int j=i;j<=x;++j)putchar(str[j]);puts("");
                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){
        // if(G==17){
        //     int n=read(),m=read();
        //     scanf("%s",str+1);
        //     for(int i=1;i<=m;++i){
        //         l[i]=read(),r[i]=read();
        //     }
        //     printf("### %lld %lld\n",n,m);
        //     printf("### %s\n",str+1);
        //     for(int i=1;i<=m;++i){
        //         printf("### %lld %lld\n",l[i],r[i]);
        //     }
        //     return 0;;
        // }
        solve();
    }
}

B

實際上就是要求把一個區間里的數從小到大排序后滿足：

也就是說，如果我們同時維護序列 \(\{b_n\}:b_i=-a_i\)

那么對于同一個區間將 \(\{a\},\{b\}\) 均排序后應有：

關鍵在于怎么動態的維護一個序列，同時支持詢問某個區間排序后的結果呢

考慮對于 \(\{a\},\{b\}\) 分別維護生成函數：

那么對于區間 \([l,r]\) 只要滿足：

那么這個區間就是好的

事實上，直接維護多項式是不現實的，但是多項式恒等的一個必要條件是兩個多項式上的若干的特征值相等，所以我們隨意令 \(x\) 為一個值，然后維護多項式的和即可，原理類似于哈希（擔心撞哈希的可以考慮維護多哈希）

順便普及一下生日悖論

C

首先考慮錯排的結構：

如果 \(n\) 是偶數，那么最近的錯排是 \(2i-1\) 和 \(2i\) 進行交換，這是唯一的

如果 \(n\) 是奇數，那么最近的錯排是具有如下性質的排列：

存在一個整數 \(r\) 使得 \(2r+1,2r+2,2r+3\) 三個數的位置是輪換的，剩下的元素是與相鄰元素交換的

所以這樣的排列有 \(n-1\) 個

并且，每一個這樣的排列（錯排）都可以被如下的二元組表示：

然后為求出字典序的第 \(k\) 個，考慮從前往后貪心的操作，

事實上，不難分析出每個位置 \(i\) 上至多有 \(5\) 種可能的值，分別對應

使用線段樹維護即可

D - 勢能分析入門

考慮維護 \(n+1\) 棵動態開點線段樹，編號從 \(0\) 到 \(n\)，\(0\) 代表沒有人用的位置，其余的分別代表每個人所占有的線段

然后不難發現題目的三種操作至多會增加 \(O(n)\) 個連續段，

第一種操作就是線段樹分裂，每次至多產生 \(\log n\) 個節點，因此整個程序的總的節點數是 \(O(n\log n)\)

第二種操作是線段樹合并，每次操作對時間復雜度的貢獻是該次操作刪除的節點的個數，顯然總和不會超過總結點個數，所以這個部分的時間復雜度也是 \(O(n\log n)\)

現在還沒有解決詢問的問題

考慮對于所有連續段維護一個 set 或者什么別的，記錄這個連續段的節點的編號，然后每次就二分找到那個彈幕所在的節點，顯然這個節點是某個線段樹的葉子，然后就一直往上跳跳到根節點即可判斷這個根節點是在誰手上

上述的功能也可以用 fhqtreap 來完成，但是我不會 fhqtreap

E

裸的線段樹合并模板

#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

神奇分塊

首先需要發現一個性質：

性質1

對于序列 \(\{b_n\}:b_i=\gcd(i,b_i)\) 的修改次數是不多的

具體的，是對每個數的質因子個數求和，為 \(O(n \log\log n)\)

考慮對于序列分塊，每個節點維護它跳出當前塊的第一個位置是多少以及收獲的權值

每次修改 \(b_i\) 時就對 \(i\) 信息暴力重構即可，時間復雜度為 \(O(B)\)

取塊長 \(B=400\) 可以達到最佳效果

G

考慮當一個球變成藍色時會影響哪些偵測器：

所以維護藍色球的連續段即可，使用線段樹合并可以完成

H

不難注意到后綴 \(\gcd\) 至多 \(\log\) 個取值，所以直接用個 set 維護一下就行了

#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();
    // pos.insert({0,{0,0}});
    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(){
    // freopen("D.out","w",stdout);
    for(int cas=read();cas--;)
        solve();
    return 0;
}

I

注意到整體加上一個數不影響相對大小，所以考慮通過相對大小的方式來討論：

實際上一個序列是可整除的充要條件是笛卡爾樹上的每個父親都是兒子的因子

第二個要關注的是這樣的 \(x\) 是不多的，因為：

事實上，在 \(1\sim 1e9\) 之間最大的因子個數為 \(1000\)

所以暴力枚舉后在笛卡爾樹上檢驗，可以通過本題

J

貪心+位運算即可