2021“MINIEYE杯”中国大学生算法设计超级联赛（10）Pty loves string（kmp+可持续化线段树）_2021“minieye杯”中国大学生算法设计超级联赛(10)

思路：
首先得出l+x=r-y+1的结果，kmp出所有合法的x,y;构建两个树，跑dfs序列进行离散化，然后用主席树，求出合法x和y；
dfs序列：https://blog.csdn.net/gao506440410/article/details/81909292
可持续化线段树：https://blog.csdn.net/diaoxiangxi0422/article/details/101255260
借鉴：https://www.cnblogs.com/darker-wxl/p/15165963.html

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define MAX 100005
#define ll long long
#define llu unsigned long long
#define inf 0x3f3f3f
#define pi acos(-1)
const ll maxn=200100;
const ll maxm=5e3+10;
int h1[maxn],e1[maxn],ne1[maxn];
int h2[maxn],e2[maxn],ne2[maxn];
int idx,m1,m2;
int ls[maxn<<8],rs[maxn<<8],sum[maxn<<8];
int f1[maxn],f2[maxn];
int kkk;
int rt[maxn],pos[maxn],in[maxn][2],out[maxn][2],tot[2];
char str[maxn];
void ad1(int a,int b){
    e1[m1]=b;
    ne1[m1]=h1[a];
    h1[a]=m1;
    m1++;
}
void ad2(int a,int b){
    e2[m2]=b;
    ne2[m2]=h2[a];
    h2[a]=m2;
    m2++;
}
void dfs1(int u){
    in[u][0]=++tot[0];
    pos[tot[0]]=u;
    for(int i=h1[u];~i;i=ne1[i]){
        int j=e1[i];
        dfs1(j);
    }
    out[u][0]=tot[0];
}//从in[u][0]进入，从out[u][0]出，就是u的子树，给所有的节点进行编号
void dfs2(int u){
    in[u][1]=++tot[1];
    for(int i=h2[u];~i;i=ne2[i]){
        int j=e2[i];
        dfs2(j);
    }
    out[u][1]=tot[1];
}
void insert1(int &t,int pre,int l,int r,int x){//进行引用传递
    t=++idx;
    ls[t]=ls[pre],rs[t]=rs[pre];
    sum[t]=sum[pre]+1;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(x<=mid){
        insert1(ls[t],ls[pre],l,mid,x);
    }else{
        insert1(rs[t],rs[pre],mid+1,r,x);
    }
    return ;
}
int query(int p,int q,int l,int r,int x,int y){
    if(r<x||y<l)return 0;
    if(x<=l&&y>=r){
        return sum[p]-sum[q];
    }
    int mid=(l+r)>>1;
    return query(ls[p],ls[q],l,mid,x,y)+query(rs[p],rs[q],mid+1,r,x,y);
}

void solve(){
    int n,q;
    cin>>n>>q;
    cin>>(str+1);
    int j=0;
    memset(h1,-1,sizeof(h1));
    memset(h2,-1,sizeof(h2));
    for(int i=2;i<=n;i++){
        while(j&&str[j+1]!=str[i])j=f1[j];
        if(str[j+1]==str[i])j++;
        f1[i]=j;
    }//进行kmp预处理，f1[i]和i就是合理的x
    j=n+1;
    f2[n]=n+1;//初始化
    for(int i=n-1;i>=1;i--){
        while(j<=n&&str[j-1]!=str[i])j=f2[j];
        if(str[j-1]==str[i])j--;
        f2[i]=j;
    } //进行kmp预处理，f2[i]和i就是合理的y
    for(int i=1;i<=n;i++){
        ad1(f1[i],i);
        ad2(f2[i],i);
    }
    dfs1(0);
    dfs2(n+1);
    for(int i=1;i<=n+1;i++){//进行可持化线段树,结果存在就加一
        insert1(rt[i],rt[i-1],1,n+1,in[pos[i]+1][1]);
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        y=n-y+1;
        cout<<query(rt[out[x][0]],rt[in[x][0]-1],1,n+1,in[y][1],out[y][1])<<endl;
    }
    for(int i = 0;i <= n + 1;i++) f1[i] = f2[i] = 0, rt[i] = 0;
    idx = tot[1] = tot[0] = 0;
    m1 = m2 = 0;
}
/*void solve(){
    int n,q;
    cin >> n >> q;
    cin >> (str + 1);
    // 字符串kmp预处理
    int j = 0;
    memset(h1,-1,sizeof h1);
    memset(h2,-1,sizeof h2);
    for(int i = 2;i <= n;i ++) {
        while(j && str[j + 1] != str[i]) j = f1[j];
        if(str[j + 1] == str[i]) j ++;
        f1[i] = j;
    }
    j = n + 1;
    f2[n] = n + 1;
    for(int i = n - 1;i >= 1;i --) {
        while(j <= n && str[j - 1] != str[i]) j = f2[j];
        if(str[j - 1] == str[i]) j --;
        f2[i] = j;
    }
    // 建树
    for(int i = 1;i <= n;i ++) {
        ad1(f1[i],i);
        ad2(f2[i],i);
    }
    dfs1(0);
    dfs2(n + 1);
    // 处理
    for(int i = 1;i <= n + 1;i ++) { // 注意我们的dfs序是从0或n + 1开始的，所以需要加1
        insert1(rt[i], rt[i - 1],1,n + 1,in[pos[i] + 1][1]);
    }
    while(q --) {
        int x,y;
        cin >> x >> y;
        y = n - y + 1;
        cout << query(rt[out[x][0]],rt[in[x][0] - 1],1,n + 1,in[y][1],out[y][1]) << endl;
    }
    for(int i = 0;i <= n + 1;i ++) f1[i] = f2[i] = 0, rt[i] = 0;
    idx = tot[1] = tot[0] = 0;
    m1 = m2 = 0;
}
*/
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170