2022牛客多校加赛场

acm
2022牛客多校
发布日期:   2022-09-08
文章字数:   1.3k

2022牛客多校加赛场

contest传送门

战况

standing

这次的发挥实在是离谱，甚至差点进前50。

然后至于为什么这么久才开始补这场的博客，是因为我今天下午刚补了一道这场的字符串题目，前面有提到过这道题。

补题

Cmostp

题意

给出一个长度为 $n(1 \leq n \leq 10^5)$ 的字符串 $s$ ，然后会有 $q(1 \leq q \leq 10^5)$ 个提问。

每次提问给出一个区间 $[l,r]$ ，询问字符串 $s$ 中，所有结尾在 $[l,r]$ 的子串中，本质不同子串的个数。

思路

这道题的思路和之前的一道洛谷上面的题目特别类似，那道题是求区间本质不同子串数量，具体见我写的这篇，这道题的大致思路和那道题的思路十分类似，也是利用 $SAM$ + $LCT$ + 扫描线思想 + 离线处理 + 线段树 来进行求解的。不同的地方就是 $LCT$ 里面的 $access$ 操作有点不太一样。

这道题里面的线段树中维护的是以该位置为结尾的子串的数量，所以在 $LCT$ 中的 $access$ 操作中要进行操作和维护的是字串的右端点，进行一些改动即可。

代码

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
#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=500005;

int n,q;
char s[MAXX];
int pos[MAXX];

struct SamNode{
	int ch[26];
	int len,fa;
	SamNode(){memset(ch,0,sizeof(ch));len=0;}
}sam[MAXX<<1];
int las=1,sam_cnt=1;

//LL num[MAXX<<1];
void add(int c){
	int p=las;int np=las=++sam_cnt;
//	num[np]=1LL;//此行为计数用，标记出现过几次 
	sam[np].len=sam[p].len+1;
	for(;p&&!sam[p].ch[c];p=sam[p].fa) sam[p].ch[c]=np;
	if(!p) sam[np].fa=1;
	else{
		int q=sam[p].ch[c];
		if(sam[q].len==sam[p].len+1) sam[np].fa=q;
		else{
			int nq=++sam_cnt;sam[nq]=sam[q];
			sam[nq].len=sam[p].len+1;
			sam[q].fa=sam[np].fa=nq;
			for(;p&&sam[p].ch[c]==q;p=sam[p].fa) sam[p].ch[c]=nq;
		}
	}
}

struct Seg{
    LL tr[MAXX<<2],lazy[MAXX<<2];
    //sum
    inline void pushup(int now){
        tr[now]=tr[now<<1]+tr[now<<1|1];
    }
    inline void pushdown(int now,int l,int r){
        if(lazy[now]){
            int mid=(l+r)>>1;
            lazy[now<<1]+=lazy[now];
            lazy[now<<1|1]+=lazy[now];
            tr[now<<1]+=lazy[now]*(mid-l+1);
            tr[now<<1|1]+=lazy[now]*(r-mid);
            lazy[now]=0;
        }
    }
    //add
    void updata(int now,int l,int r,int ll,int rr,LL val){
        if(l>=ll&&r<=rr){
            lazy[now]+=val;
            tr[now]+=val*(r-l+1);
            return;
        }
        pushdown(now,l,r);
        int mid=(l+r)>>1;
        if(mid>=ll)
            updata(now<<1,l,mid,ll,rr,val);
        if(mid<rr)
            updata(now<<1|1,mid+1,r,ll,rr,val);
        pushup(now);
    }
    //sum
    LL getsum(int now,int l,int r,int ll,int rr){
        if(l>=ll&&r<=rr)
            return tr[now];
        pushdown(now,l,r);
        LL ret=0;
        int mid=(l+r)>>1;
        if(mid>=ll)
            ret+=getsum(now<<1,l,mid,ll,rr);
        if(mid<rr)
            ret+=getsum(now<<1|1,mid+1,r,ll,rr);
        return ret;
    }
}seg;

struct LCT{
    struct node{
        int fa,left,right,val,cover;
    }s[MAXX<<1];
    inline void pushdown(int i){
        if(s[i].cover){
            if(s[i].left) s[s[i].left].val=s[s[i].left].cover=s[i].cover;
            if(s[i].right) s[s[i].right].val=s[s[i].right].cover=s[i].cover;
            s[i].cover=0;
        }
    }
    inline int identify(int i){
        if(s[s[i].fa].left==i) return 0;
        if(s[s[i].fa].right==i) return 1;
        return -1;
    }
    inline void connect(int i,int f,int op){
        s[i].fa=f;
        if(op==1) s[f].right=i;
        if(op==0) s[f].left=i;
    }
    inline void rotate(int x){
        int y=s[x].fa;
        int z=s[y].fa;
        int opy=identify(y);
        int opx=identify(x);
        int u=0;
        if(opx==1) u=s[x].left;
        if(opx==0) u=s[x].right;
        connect(u,y,opx);
        connect(y,x,opx^1);
        connect(x,z,opy);
    }
    void pushall(int x){
        if(identify(x)!=-1) pushall(s[x].fa);
        pushdown(x);
    }
    inline void splay(int i){
        pushall(i);
        while(identify(i)!=-1){
            int up=s[i].fa;
            if(identify(up)==-1) rotate(i);
            else if(identify(i)==identify(up)) rotate(up),rotate(i);
            else rotate(i),rotate(i);
        }
    }
    //以上为splay的一些基本操作
    //下面是LCT的操作
    //构建一条从根到k的一条重链
    inline int access(int k,int id){
        int temp=0;
        while(k){
            splay(k);
			if(s[k].val){
				seg.updata(1,1,n,s[k].val,s[k].val,-(sam[k].len-sam[s[k].fa].len));
			}
            s[k].right=temp;
            temp=k;
            k=s[k].fa;
        }
		seg.updata(1,1,n,id,id,id);
		s[temp].val=s[temp].cover=id;
        return temp;
    }
}lct;

struct query{
	int l,r,id;
}qq[MAXX];
LL ans[MAXX];
bool cmp(query jj,query kk){return jj.r<kk.r;}

inline void solve(){
	scanf("%d%d",&n,&q);
	getchar();scanf("%s",s+1);
	for(int i=1;i<=n;++i){
		add(s[i]-'a');
		pos[i]=las;
	}
	for(int i=2;i<=sam_cnt;++i)
		lct.s[i].fa=sam[i].fa;

	for(int i=1;i<=q;++i)
		scanf("%d%d",&qq[i].l,&qq[i].r),qq[i].id=i;
	sort(qq+1,qq+q+1,cmp);

	int p=1;
	for(int i=1;i<=n;++i){
		lct.access(pos[i],i);
		while(qq[p].r==i){
			ans[qq[p].id]=seg.getsum(1,1,n,qq[p].l,qq[p].r);
			++p;
		}
	}
	
	for(int i=1;i<=q;++i)
		printf("%lld\n",ans[i]);
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}

总结

这道题也算是字符串里面的一道神仙题目了。需要多练习练习。

文章作者: Shaun
文章链接: http://shaun-2314.github.io/2022/09/08/2022nowcoder-extra/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Shaun !
acm
评论
  目录