Wuyanru's blog
0%

[NOI2023] 字符串

发表于 分类于 ，

现场选手，拿了 分。

感觉差点就切了啊，那应该还是我菜了

切了就金了，气死了。

题目链接

题意

现在有一个长度为 的字符串 ，和 次询问。

定义 为 的第 到 位构成的子串， 为翻转字符串 得到的字符串。

对于每一组询问，给出 ，求出有多少个 ，满足 且

多组数据， 且单组数据 。

题解

先来讲一下我考场上的思路。

首先题目涉及了两个字符串字典序的比较，而且只涉及了原串的子串（及其翻转），我在考场上的直觉，就是正解的第一步，大概率是先把原串和它的反串拼在一起，跑一个后缀数组。

所以我们先令 ，并对 建立后缀数组。

题目要求的是有多少个 满足条件，我们发现这个 给的是参与比较的两个串的分界线。

那我们考虑换一个元，我们不求有多少个 满足条件，我们求有多少个 满足条件，其中 ，即我们对第二个串的末尾计数。

那么经过推导，我们可以知道，合法的 需要满足以下条件：

  1. 且 与 不同奇偶，并且 ；
  2. 。

条件可能写的很迷，来详细解释一下。

题目中要求 ，即 。

那么首先存在一个必要条件，就是 这个后缀一定要小于 这个后缀。

这就是 的原因。

但是我们发现，这个条件是必要的，但是不是充要的，为什么呢？

因为即使满足了上述的条件，也有可能出现两个串相等的情况，所以我们还要排除掉两个串相等的情况。

我们知道串的长度是 ，所以还需要满足条件 。

这两个条件都不是我一眼能看出来的，好难啊（

所以考虑一个条件一个条件的看。

part1

题目中有一个特殊性质 B，是所有相邻的字符都不相等，可以推出第二个条件永远成立，所以在这个部分分中只需要考虑第一个条件。

还是一样，为了方便，换个元，令 ，那么就是要求 ， 且 与 同奇偶的 数量。

首先将所有询问离线，并按照 的奇偶进行分类，这样我们只需要考虑与 奇偶性相同的 。

对于一组询问，我们将其中的询问按照 从大到小的顺序进行排序。

这样，我们按照这个顺序进行处理，对于每一组询问，就可以将所有当前 的 插入一个线段树中。

然后查询区间 中有多少个 ，这样三个条件我们就同时满足了。

直接这样做，和暴力拼一起可以拿到 分，时间复杂度为 。

然后特殊性质 A 意思就是两个串相等的话，长度一定不会超过 ，经典结论了属于是。

然后想到这里就可以拿到 分乐。

part2

现在来看第二个条件。

我们首先发现 其实是 SA 上的 RMQ 问题，但是这样子显然太麻烦了，基本没有办法优化到 以下。

这个时候特殊性质 B 可以给我们启发。

特殊性质 B 意思是没有两个串相等，但是并没有直接说出来，而是采用了一种不那么显然的方式——相邻两个字符不相等。

仔细想想，我们会发现，第二个条件如果不满足，那么 一定是一个回文串。

所以我们考虑先算出满足条件 的 的数量，在用它减去，满足条件 却不满足条件 的数量。

什么情况下，会出现满足条件 但不满足条件 呢？

  1. 为回文串；
  2. 。

首先回文串数量很多，我们不可能每一个回文串都单独拿出来，所以我们先用 Manacher 找出所有满足条件的，极长回文串（只需要找出长度为偶数的就好）。

假设一个合法回文串范围为 ，那么我们定义它的中点 （即靠左的中心点），长度 ，我们考虑使用中点与长度表示一个合法的回文串。

那么我们对于每一个询问，实际上要求的就是满足以下条件的回文串数量：

  1. （回文串包含 这个位置，且 在中点以左）；
  2. （满足题目中 的限制）。

我们发现，假如将一个回文串看作一个二维平面上的点 ，那么条件就是：

  1. ；
  2. 。

这是一个标准的二维数点问题，差分后做二维偏序即可。

最后总时间复杂度还是 。

记得清空，不然会挂很多。

代码

我写了一坨，很长。

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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
#include<algorithm>
#include<cassert>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
using ll=long long;
template<typename A>
using vc=vector<A>;
using pli=pair<ll,int>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
struct node
{
    int x,r;
    int v;
    int id;
}a[100001];
int qans[100001];
char in[100001];
int n,m;
namespace S
{
    int num1[800001];
    int num2[800001];
    inline void init()
    {
        memset(num1,0,sizeof(num1));
        memset(num2,0,sizeof(num2));
    }
    void add(int p,int pl,int pr,int x)
    {
        if(x&1) num1[p]++;
        else num2[p]++;
        if(pl==pr) return ;
        int mid=(pl+pr)>>1;
        if(x<=mid) add(p*2,pl,mid,x);
        else add(p*2|1,mid+1,pr,x);
    }
    int get1(int p,int pl,int pr,int l,int r)
    {
        if(l<=pl&&pr<=r) return num1[p];
        int mid=(pl+pr)>>1,ans=0;
        if(l<=mid) ans+=get1(p*2,pl,mid,l,r);
        if(mid<r) ans+=get1(p*2|1,mid+1,pr,l,r);
        return ans;
    }
    int get2(int p,int pl,int pr,int l,int r)
    {
        if(l<=pl&&pr<=r) return num2[p];
        int mid=(pl+pr)>>1,ans=0;
        if(l<=mid) ans+=get2(p*2,pl,mid,l,r);
        if(mid<r) ans+=get2(p*2|1,mid+1,pr,l,r);
        return ans;
    }
}
namespace part1
{
    int tmp[200005];
    int cnt[200005];
    int num1[200001];
    int num2[200001];
    int sa[200001];
    int rk[400001];
    char s[200005];
    inline void SA_sort(int n,int ma)
    {
        memset(cnt,0,sizeof(int)*(ma+2));
        for(int i=1;i<=n;i++) cnt[num2[i]+1]++;
        for(int i=1;i<=ma+1;i++) cnt[i]+=cnt[i-1];
        for(int i=1;i<=n;i++) tmp[++cnt[num2[i]]]=i;
        memset(cnt,0,sizeof(int)*(ma+2));
        for(int i=1;i<=n;i++) cnt[num1[i]+1]++;
        for(int i=1;i<=ma+1;i++) cnt[i]+=cnt[i-1];
        for(int i=1;i<=n;i++) sa[++cnt[num1[tmp[i]]]]=tmp[i];
    }
    inline void SA(int n)
    {
        s[n+1]=0;
        memset(rk,0,sizeof(rk));
        for(int i=1;i<=n;i++) rk[i]=s[i]-'a'+1,sa[i]=1;
        for(int i=1;i<n;i<<=1)
        {
            for(int j=1;j<=n;j++)
            {
                num1[j]=rk[j];
                num2[j]=rk[i+j];
            }
            SA_sort(n,max(26,n));
            for(int j=1;j<=n;j++)
            {
                int now=sa[j],lst=sa[j-1];
                if(num1[now]==num1[lst]&&num2[now]==num2[lst]) rk[now]=rk[lst];
                else rk[now]=j;
            }
        }
        // printf("%s\n",s+1);
        // for(int i=1;i<=n;i++) printf("%d%c",sa[i]," \n"[i==n]);
        // for(int i=1;i<=n;i++) printf("%d%c",rk[i]," \n"[i==n]);
    }
    inline void mian()
    {
        for(int i=1;i<=n;i++) s[i]=s[2*n-i+1]=in[i];
        SA(2*n);int now=2*n+1;
        sort(a+1,a+m+1,[](node a,node b){ return rk[a.x]>rk[b.x];});
        S::init();
        for(int i=1;i<=m;i++)
        {
            while(now>rk[a[i].x])
            {
                now--;
                S::add(1,1,2*n,sa[now]);
            }
            int l=a[i].x,r=l+2*a[i].r-1;
            l=2*n-l+1,r=2*n-r+1;
            if(r&1) qans[a[i].id]=S::get1(1,1,2*n,r,l);
            else qans[a[i].id]=S::get2(1,1,2*n,r,l);
        }
    }
}
namespace C
{
    struct pal
    {
        int l,mid;
    }b[100001];
    int tag[400001];
    int tot;
    inline void Add(int l,int r)
    {
        tot++;
        b[tot].l=l;
        b[tot].mid=(l+r)>>1;
    }
    void add(int p,int pl,int pr,int l,int r)
    {
        if(l<=pl&&pr<=r)
        {
            tag[p]++;
            return ;
        }
        int mid=(pl+pr)>>1;
        if(l<=mid) add(p*2,pl,mid,l,r);
        if(mid<r) add(p*2|1,mid+1,pr,l,r);
    }
    int get(int p,int pl,int pr,int x)
    {
        if(pl==pr) return tag[p];
        int mid=(pl+pr)>>1;
        if(x<=mid) return tag[p]+get(p*2,pl,mid,x);
        return tag[p]+get(p*2|1,mid+1,pr,x);
    }
    inline void run()
    {
        sort(a+1,a+m+1,[](node a,node b){ return a.v<b.v;});
        sort(b+1,b+tot+1,[](pal a,pal b){ return a.mid<b.mid;});
        int now=0;memset(tag,0,sizeof(tag));
        for(int i=1;i<=m;i++)
        {
            while(now<tot&&a[i].v>=b[now+1].mid)
            {
                now++;
                add(1,1,n,b[now].l,b[now].mid);
            }
            qans[a[i].id]-=get(1,1,n,a[i].x);
        }
    }
}
namespace part2
{
    int num[200005];
    char s[200005];
    int len;
    inline char gol(int x,int y)
    {
        if(x<=y) return '?';
        return s[x-y];
    }
    inline char gor(int x,int y)
    {
        if(x+y>len) return '!';
        return s[x+y];
    }
    inline void manacher()
    {
        s[len+1]=0;
        int l=1,r=0;
        for(int i=1;i<=len;i++)
        {
            if(i>r) num[i]=0;
            else num[i]=min(num[l+r-i],r-i);
            while(gol(i,num[i]+1)==gor(i,num[i]+1)) num[i]++;
            if(i+num[i]>r) l=i-num[i],r=i+num[i];
        }
        C::tot=0;
        for(int i=1;i<=len;i+=2) if(num[i])
        {
            int l=(i-num[i]+1)/2;
            int r=(i+num[i]-1)/2;
            int wl=part1::rk[l],wr=part1::rk[2*n-r+1];
            // printf("%d %d : %d %d\n",l,r,wl,wr);
            if(wl>wr) continue;
            C::Add(l,r);
        }
    }
    inline void mian()
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            s[++cnt]='#';
            s[++cnt]=in[i];
        }
        s[++cnt]='#',len=cnt;
        manacher();
        C::run();
    }
}
inline void solve()
{
    n=read(),m=read();
    scanf("%s",in+1);
    for(int i=1;i<=m;i++)
    {
        a[i].x=read(),a[i].r=read();
        a[i].v=a[i].x+a[i].r-1;
        a[i].id=i;
    }
    part1::mian(),part2::mian();
    for(int i=1;i<=m;i++) printf("%d\n",qans[i]);
}
int main()
{
    read();int T=read();
    while(T--) solve();
    return 0;
}

感谢观看！