Liveddd's Blog

愛にできることはまだあるかい

LOJ#3983. 「NOI2023」字符串

发表于 分类于
本文字数： 5.8k 阅读时长 ≈ 13 分钟

感觉有些套路。。。

转化限制，转为好统计的后缀或者是前缀。设 $S_i=s[i,n],P_i=R(s[1,i])$，那么对于 $i,l$，需要满足原限制的必要条件是 $S_i<P_{i+2l-1}$。考虑去掉多余的情况，即满足 $s[i,i+l-1]=R(s[i+l,i+2l-1])$ 即 $s[i,i+2l-1]$ 是回文串，并且满足 $S_{i-1}<P_{i+2l}$。于是把问题分为两部分分别计数。将询问离线考虑。

对于第一部分，我们对 $s+c_1+R(s)+c_2$ 建后缀数组，$c_1,c_2$ 为分隔符，均小于字符集种最小字符且满足 $c_1>c_2$。问题变为二维数点，扫描线即可解决。

对于第二部i分，使用 Manacher 求出所有回文串。设其回文中心为 $i$，回文半径为 $r$。对于 $S_{i-r-1}<P_{i+r}$ 只需要判断 $s[i-r-1]<s[i+r]$。问题依然是二位数点，加入的点形如一条斜率为 $-1$ 的斜线 $(i-l,i+l+1)$ 其中 $0<l\le r$，查询 $(i,i+2r-1)$ 下方的点个数。对坐标进行简单变换，$(x,y)\to (\frac{y+x+1}{2},\frac{y-x+1}{2})$，二者分别变为 $(i+1,l+1)$，其中 $0<l\le r$，与 $(i+r,r)$。问题变为二维数点，扫描线即可解决

总的时间复杂度为 $\mathcal O((n+q)\log n)$。

Code
 
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define lowbit(x) (x&(-x))
using namespace std;
const int N=2e5+10,C=128;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int type,T,n,m,k;
char s[N],t[N];
int ans[N];
struct BIT
{
    int n,c[N];
    void clear(){memset(c,0,sizeof(c));}
    void add(int x,int k){for(;x<=n;x+=lowbit(x))c[x]+=k;}
    int ask(int x){int res=0;for(;x;x-=lowbit(x))res+=c[x];return res;}
    int query(int l,int r){return ask(r)-ask(l-1);}
};
namespace SA
{
    int n,m;
    int pos,sa[N],rk[N],oldrk[N<<1],id[N],key1[N],cnt[N];
    bool cmp(int x,int y,int w){return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];}
    void build(int len,char *s)
    {
        n=len;
        m=C;
        memset(cnt,0,sizeof(cnt));
        memset(rk,0,sizeof(rk));
        for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i;i--)sa[cnt[rk[i]]--]=i;
        for(int w=1;;w<<=1,m=pos)
        {
            pos=0;
            for(int i=n;i>n-w;i--)id[++pos]=i;
            for(int i=1;i<=n;i++)if(sa[i]>w)id[++pos]=sa[i]-w;
            memset(cnt,0,sizeof(cnt));
            for(int i=1;i<=n;i++)cnt[key1[i]=rk[id[i]]]++;
            for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
            for(int i=n;i;i--)sa[cnt[key1[i]]--]=id[i];
            memcpy(oldrk+1,rk+1,n*sizeof(int));
            pos=0;
            for(int i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?pos:++pos;
            if(pos==n)break;
        }
    }
};
namespace Manacher
{
    int len,p[N];
    char s[N];
    void build(char *c)
    {
        int n=strlen(c+1);
        s[0]='~',s[len=1]='#';
        for(int i=1;i<=n;i++)s[++len]=c[i],s[++len]='#';
        s[++len]='!';
        for(int mid=0,mr=0,i=1;i<=len;i++)
        {
            int j=mid*2-i;
            p[i]=i>mr?1:min(p[j],mr-i+1);
            // if(i<=mr)p[i]=min(p[j],mr-i+1);
            while(s[i-p[i]]==s[i+p[i]])p[i]++;
            if(i+p[i]>mr)mr=i+p[i]-1,mid=i;
        }
    }
};

namespace Part1
{
    struct Query
    {
        int id,l,r;
    };
    vector<Query>q[N];
    void add(int id,int i,int r){q[SA::rk[i]].push_back({id,i+1,i+(r<<1)-1});}
    BIT t[2];
    void solve()
    {
        t[0].clear(),t[1].clear();
        t[0].n=t[1].n=m;
        for(int i=m;i;i--)
        {
            int pos=SA::sa[i];
            if(pos<=n)
                for(auto now:q[i])
                    ans[now.id]+=t[now.l&1].query(now.l,now.r);
            else if(pos>n+1&&pos<m)
            {
                pos=m-pos;
                t[pos&1].add(pos,1);
            }
            q[i].clear();
        }
    }
};
namespace Part2
{
    struct Modify
    {
        int x,y;
    };
    vector<Modify>a[N],q[N];
    BIT t;
    void add(int id,int i,int r){q[i].push_back({id,i+r});}
    void solve()
    {
        t.clear();
        t.n=n<<1;
        Manacher::build(s);
        for(int i=2;i<=n;i++)
        {
            int r=Manacher::p[i*2-1]>>1;
            if(!r||s[i+r]>=s[i-r-1])continue;
            a[i-r].push_back({i,1});
            a[i].push_back({i,-1});
        }
        for(int i=1;i<=n;i++)
        {
            for(auto now:a[i])t.add(now.x,now.y);
            for(auto now:q[i])ans[now.x]-=t.ask(now.y);
            a[i].clear(),q[i].clear();
        }
    }
};

inline void solve()
{
	read(n,k);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)t[i]=s[i];
    t[n+1]='2',t[2*n+2]='1';
    t[2*n+3]='\0';
    s[n+1]='\0';
    for(int i=1;i<=n;i++)t[n+i+1]=s[n-i+1];
    m=2*n+2;
    SA::build(m,t);
    for(int i=1;i<=k;i++)
    {
        int x,r;
        read(x,r);
        Part1::add(i,x,r);
        Part2::add(i,x,r);
    }
    Part1::solve();
    Part2::solve();
    for(int i=1;i<=k;i++)printf("%d\n",ans[i]),ans[i]=0;
}
int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	read(type,T);
	while(T--)solve();
	return 0;
}