Loading

廣二集訓 day2

T1：推性質+CDQ分治 T3：莫隊+字符串相關，實際上是雜糅改編題就對了

T1 CDQ分治

Problem A: 白(bai)

給你一個長度為 $n$ 的序列 $a$ 和 $m$ 次詢問，每次詢問給定三個整數
$l,r,k$，你需要求出下面問題的答案。

有一個初始為空的棧，把序列中下標在 $l$ 到 $r$
之間的元素依次加入棧中，每加入一個元素之前把棧頂前 $k$個元素中與即將加入的元素相同的元素刪除，最后棧中有多少個元素？

【輸入格式】

從文件 bai.in 中讀入數據。

第一行兩個整數 $n,m$，表示序列長度和詢問的個數。

第二行 $n$ 個整數表示序列 $a$。

接下來 $m$ 行，每行三個整數 $l,r,k$，表示一次詢問。

【輸出格式】

輸出到文件 bai.out 中。

輸出共 $m$ 行，每行一個整數表示詢問的答案。

【樣例1輸入】

6 3
1 2 3 1 2 1
1 5 3
3 6 1
1 6 2

【樣例1輸出】

3
4
5

見選手目錄下的 $\mathit{bai/bai1.in}$ 與 $\mathit{bai/bai1.ans}$。

【樣例1解釋】

在第三次詢問中往棧中加入元素的過程如下：

初始棧為空棧。
加入元素 $1$。在這之后棧中元素從底到頂為 $[1]$。
加入元素 $2$。在這之后棧中元素從底到頂為 $[1,2]$。
加入元素 $3$。在這之后棧中元素從底到頂為 $[1,2,3]$。
加入元素 $1$。在這之前棧頂前 $2$ 個元素中沒有
$1$，不需要刪除。在這之后棧中元素從底到頂為 $[1,2,3,1]$。
加入元素 $2$。在這之前棧頂前 $2$ 個元素中沒有
$2$，不需要刪除。在這之后棧中元素從底到頂為 $[1,2,3,1,2]$。
加入元素 $1$。在這之前棧頂前 $2$ 個元素中有
$1$，刪除后棧中元素從底到頂為 $[1,2,3,2]$。加入元素 $1$
后棧中元素從底到頂為 $[1,2,3,2,1]$。

最終棧中元素有 $5$ 個。

【樣例2輸入】

20 8
9 18 10 9 12 10 7 10 3 10 12 7 3 7 7 3 12 12 3 9
14 17 1
4 19 4
1 2 5
6 7 4
10 17 6
3 3 4
13 17 1
8 17 5

【樣例2輸出】

CDQ分治好題，考場上想出來了除CDQ以外的全部內容

首先我們觀察到：

一個元素最多只能刪除一個相同元素
兩個鄰接元素（不妨稱為貢獻區間），前一個元素能否被另一個元素刪除有不變臨界值$w_i$
若貢獻區間 $i$ 包含其他共享區間 $j(共有siz個)$ ，則有 $w_i\ge w_j$，形式化的
：$ w_i=max(w_j,len_i-siz-1)$ ,也可以抽象為區間顏色數，維護一下即可

int t1[N];
void add(int x,int k) {
    for(;x<=n;x+=(x&-x)) t1[x]+=k; 
}
int query(int x) {
    int sum=0;if(x==0) return 0;
    for(;x;x-=(x&-x)) sum+=t1[x];
    return sum; 
}
int t2[N<<2];
void Add(int x,int k) {
    for(;x<=n;x+=(x&-x)) t2[x]=max(t2[x],k); 
}
int Query(int x) {
    int sum=0;
    for(;x;x-=(x&-x)) sum=max(sum,t2[x]);
    return sum; 
}

for(register int i=1;i<=n;i++) {
        a[i]=read();
        if(p[a[i]]) la[i]=p[a[i]];
        p[a[i]]=i;
        if(!la[i]) continue;
        add(1,1);add(la[i],-1);
        w[i]=max(Query(n-la[i]+1),i-la[i]-query(la[i]));
        Add(n-la[i]+1,w[i]);
        q[++cnt]={la[i],i,w[i],1,0};
}

有了這些我們可以來處理詢問區間($l , r, k$)中有幾個生效的貢獻區間（$L_i R_i w_i$）：

$l \le L_i$
$r \ge R_i$
$k \ge w_i $

發現是一個三維偏序，CDQ分治即可

void CDQ(int l,int r) {
	if(l==r) return ;
	int mid=l+r>>1;
	CDQ(l,mid),CDQ(mid+1,r);
	sort(q+l,q+mid+1,cmp2),sort(q+mid+1,q+r+1,cmp2);
	int j=l;
	for(int i=mid+1;i<=r;i++) {
		while(q[j].r<=q[i].r&&j<=mid) {
			if(q[j].op==1) add(q[j].l,1);
			j++;
		}
		if(q[i].op==2) A[q[i].id]+=query(n)-query(q[i].l-1);
	}
	for(int i=l;i<j;i++) 
		if(q[i].op==1) add(q[i].l,-1);
}

T3 90pts 莫隊+字符串相關

【題目描述】

給你一個大小為 $n$ 的字符串序列 $a$。定義 $f(s,t)$ 為字符串 $s$ 在 $t$
中的出現次數。$g(l,r)=\sum\limits_{i=l}^{r}\sum\limits_{j=i+1}^r\max(f(a_i,a_j),f(a_j,a_i))$。

再給你 $m$ 個詢問，每次詢問給定兩個整數 $l,r$，你需要求出 $g(l,r)$
的值。

【輸入格式】

從文件 zhong.in 中讀入數據。

第一行兩個整數 $n,m$，表示序列長度和詢問的個數。

接下來 $n$ 行，每行一個字符串，其中第 $i$ 行的字符串 $a_i$
表示序列中的第 $i$ 個字符串。

接下來 $m$ 行，每行三個整數 $l,r$，表示一次詢問。

【輸出格式】

輸出到文件 zhong.out 中。

輸出共 $m$ 行，每行一個整數表示詢問的答案。

首先發現這個式子長很丑，而且有很多無用的信息，除非兩個字符串相等，不然 $f(a_i,a_j) 和 f(a_j,a_i)$ 只會有一個非0

那么我們考慮化一下式子，容易得到 $g(l,r)=\sum\limits_{i=l}^r\sum\limits_{j=l}^rg(a_i,a_j)-\sum\limits_{i=l}^r\sum\limits_{j=i}^r[a_i=a_j]$

發現后半部分是好維護的（莫隊維護AC自動機的結束位置即可），考慮前面的部分

對于非數論函數，這種形態的式子我們一般可以考慮~~接著化~~（doge），其實是還可以考慮容斥和增量法，這個顯然不好容斥，考慮用莫隊逐步增量，下面講解加法

考慮加入一個字符串 $s$ ，稱字符串區間 $[l,r]$ 組成的AC自動機集合為 $AC$，以下子樹均為 $Fail$ 樹

AC在s中出現次數

板子題類似，考慮s在AC自動機走過路徑中的點往上跳Fail邊，這個題目不能直接照板子那樣做，考慮每個串加進去時進行子樹加操作，然后s走路徑時對每個點進行單點查

void Add(int x) {
    for(int nw=id[x];nw;nw=fa[nw]) {
        ans+=B1.query(dfn[nw]);
    }
    B1.add(dfn[id[x]],1),B1.add(dfn[id[x]]+siz[id[x]],-1);
}

s在AC中出現次數

與上文類似，單點加子樹求和即可

void Add(int x) {
    for(int nw=id[x];nw;nw=fa[nw]) {
        B2.add(dfn[nw],1);
    }
    ans+=B2.query(dfn[id[x]]+siz[id[x]]-1)-B2.query(dfn[id[x]]-1);
}

時間復雜度為 $O(S\sqrt m\log S)$

若使用二次離線莫隊即為 $O(S\sqrt m)$，等我學了二離再來補

int n,q1,cnt,id[N],tot;
char s[N];
int fail[N],t[N][26],fa[N];
 
void insert(int x) {
    int nw=0,l=strlen(s+1);
    for(int i=1;i<=l;i++) {
        if(t[nw][s[i]-'a']) nw=t[nw][s[i]-'a'];
        else t[nw][s[i]-'a']=++cnt,fa[cnt]=nw,nw=cnt;
    }
    id[x]=nw;
}
 
vector<int > c[N];
queue<int > q;
void Build() {
    for(int i=0;i<26;i++)
        if(t[0][i]) q.push(t[0][i]);
    while(!q.empty()) {
        int k=q.front();q.pop();
        c[fail[k]].push_back(k);
        for(int i=0;i<26;i++) {
            if(t[k][i]) {
                fail[t[k][i]]=t[fail[k]][i];
                q.push(t[k][i]);
            }
            else t[k][i]=t[fail[k]][i];
        }
    }
}
 
int dfn[N],siz[N],A[N],fk[N],len;
void dfs(int p) {
    dfn[p]=++tot;siz[p]++;
    for(int i:c[p]) {
        dfs(i);siz[p]+=siz[i];
    }
}
 
int ans,tmp,num[N];
struct node {
    int l,r,id;
}g[N];
int pos(int x) { return fk[x]/len; }
bool cmp(node a,node b) {
    if(pos(a.l)^pos(b.l)) return a.l<b.l;
    else if(pos(a.l)&1) return a.r<b.r;
    else return a.r>b.r;
}
 
struct Tree{
    int t[N];
    void add(int x,int k) { for(;x<=tot;x+=x&-x) t[x]+=k; }
    int query(int x) { int sum=0;if(!x) return 0;for(;x;x-=(x&-x)) sum+=t[x];return sum; }
}B1,B2;//區間在單體  單體在區間
 
void Add(int x) {
    for(int nw=id[x];nw;nw=fa[nw]) {
        ans+=B1.query(dfn[nw]);
        B2.add(dfn[nw],1);
    }
    ans+=B2.query(dfn[id[x]]+siz[id[x]]-1)-B2.query(dfn[id[x]]-1);
    B1.add(dfn[id[x]],1),B1.add(dfn[id[x]]+siz[id[x]],-1);
    num[id[x]]++;
    tmp+=num[id[x]];
}
 
void Del(int x) {
    ans-=B2.query(dfn[id[x]]+siz[id[x]]-1)-B2.query(dfn[id[x]]-1);
    B1.add(dfn[id[x]],-1),B1.add(dfn[id[x]]+siz[id[x]],1);
    for(int nw=id[x];nw;nw=fa[nw]) {
        ans-=B1.query(dfn[nw]);
        B2.add(dfn[nw],-1);
    }
    tmp-=num[id[x]];
    num[id[x]]--;
}
 
signed main() {
    cin>>n>>q1;
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);fk[i]=fk[i-1]+strlen(s+1);
        insert(i);
    }
    Build();dfs(0);
    for(int i=1;i<=q1;i++) {
        int l=read(),r=read();
        g[i]={l,r,i};
    }
    len=pow(n,0.8);
    sort(g+1,g+1+q1,cmp);
    int l=1,r=0;
    for(int i=1;i<=q1;i++) {
        while(r<g[i].r) r++,Add(r);
        while(l>g[i].l) l--,Add(l);
        while(r>g[i].r) Del(r),r--;
        while(l<g[i].l) Del(l),l++;
        A[g[i].id]=ans-tmp;
    }
    for(int i=1;i<=q1;i++) printf("%lld\n",A[i]);
    return 0;
}

posted @ 2025-06-13 19:49 Mortis_Life 閱讀(20) 評論(0) 收藏舉報

刷新頁面返回頂部