2016 ACM/ICPC Asia Regional Qingdao Online 题解
代码更新 10/13 题解更新13/13
A. 多组询问求大于等于$n$的第一个数，其因数只含2，3， 5， 7.
$n \leq 10^9$
【题解】
预处理+二分
利用STL可以有效提高代码速度
复杂度$O(10^4 + Q)$
# include <stdio.h>
# include <set>
# include <algorithm>
using namespace std;
typedef long long ll;
set<ll> q;
int T, s;
int p[10010], pn=0;
int main() {
q.insert(2), q.insert(3), q.insert(5), q.insert(7);
while(!q.empty()) {
ll _top = *q.begin(); q.erase(_top);
if(_top > 1e9) break;
p[++pn] = _top;
q.insert(_top*2);
q.insert(_top*3);
q.insert(_top*5);
q.insert(_top*7);
}
scanf("%d", &T);
while(T--) {
scanf("%d", &s);
printf("%d\n", p[lower_bound(p+1, p+pn+1, s) - p]);
}
return 0;
}
B
多组询问，求$a_{n} = \sum_{i=1}^{n} \frac{1}{i^{2}}$。
输入数据不超过1M
复杂度$O(10^7 + Q)$
【题解】
观察到数列收敛，猜测有极限，暴力求出极限后打表。
# include <stdio.h>
# include <string.h>
using namespace std;
typedef long double ld;
typedef double db;
ld p[1000010];
char str[100010];
int main() {
for (int i=1; i<=1000000; ++i)
p[i] = p[i-1] + 1.0f/((ld)i * i);
while(~scanf("%s", str)) {
int sz = strlen(str), n;
if(sz >= 7) puts("1.64493");
else {
n = 0;
for (int i=0; i<sz; ++i)
n = (n<<3) + (n<<1) + str[i] - '0';
printf("%.5lf\n", (db)p[n]);
}
}
return 0;
}
C
给出屏蔽文本，要你从文章中屏蔽这些词。
【题解】AC自动机，卡空间。
D
有一壶水，体积在$[L, R]$之间，要把水近乎平均的倒到两个杯子里（差值小等1），而且要保证这壶水剩下的不能超过1，你不能实时知道还剩下水的体积，求要满足最少倒几次。
$0 < L, R \leq 10^{15}$
【题解】
很明显模拟之后我们发现要分类讨论。
①$1 < R \leq 2$：倒1体积水到一个杯子即可，故答案为1
②$0 < R \leq 1$：明显不用倒水即可，故答案为0
③$0 < L \leq 1$：第一杯1体积，之后每次2体积往上交替加即可。答案为$\frac{R-1}{2}+1$
④$R-L \leq 2$，第一次倒$\frac{L+1}{2}$，第二次倒$\frac{L+3}{2}$即可，答案为2.
⑤其他情况，在保证L的情况下，每次2体积往上交替即可。第一次倒$\frac{L+1}{2}$，第二次倒$\frac{L+3}{2}$即可，故答案为$\frac{R-L}{2}+1$
复杂度$O(T)$
# include <stdio.h>
using namespace std;
typedef long long ll;
ll L, R;
int main() {
while(~scanf("%I64d%I64d", &L, &R)) {
if(R<=1) {
puts("0");
continue;
}
if(R<=2) {
puts("1");
continue;
}
if(R-L <= 2) {
puts("2");
continue;
}
if(L <= 1) {
printf("%I64d\n", (R-1)/2+1);
continue;
}
printf("%I64d\n", (R-L)/2+1);
}
return 0;
}
E
扩展锤子剪刀布问题
【题解】
判奇数偶数即可。
复杂度$O(T)$
# include <stdio.h>
using namespace std;
int T, n;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
if(n&1) puts("Balanced");
else puts("Bad");
}
return 0;
}
F
给一条路，找一条欧拉路，使得经过的点的依次顺序，它们的异或值最大。
$n \leq 100000$
若不符合欧拉路的条件就是Impossible，不联通也是Impossible。
如果点度数两个奇数，那么欧拉路唯一，直接输出固定值即可。
否则，枚举起点（因为起点=终点会被多异或一次）求最大值即可。
复杂度$O(Tn)$
# include <stdio.h>
using namespace std;
int T, n, m, fa[100010], cnts[100010], deg[100010], v[100010];
inline int getf(int x) {
return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
fa[i] = i;
deg[i] = 0;
scanf("%d", &v[i]);
}
for (int i=1, u, vs; i<=m; ++i) {
scanf("%d%d", &u, &vs);
deg[u] ++, deg[vs] ++;
int fu = getf(u), fv = getf(vs);
if(fu != fv) fa[fu] = fv;
}
int cnt=0;
bool all = 1;
for (int i=1; i<=n; ++i) if(deg[i] & 1) cnt++, all = 0;
if(cnt > 2) {
puts("Impossible");
continue;
}
cnt = 0;
for (int i=1; i<=n; ++i) cnts[getf(i)] ++;
for (int i=1; i<=n; ++i) if(cnts[i] > 0) ++cnt;
if(cnt > 1) {
puts("Impossible");
continue;
}
if(! all) {
int ans = 0;
for (int i=1; i<=n; ++i) {
if (deg[i]&1) deg[i] = deg[i]/2 + 1;
else deg[i] /= 2;
if (deg[i]&1) ans ^= v[i];
}
printf("%d\n", ans);
} else {
int ans = 0, anss, maxx=0;
for (int i=1; i<=n; ++i) {
deg[i] /= 2;
if (deg[i]&1) ans ^= v[i];
}
for (int i=1; i<=n; ++i) {
anss = ans ^ v[i];
if(anss > maxx)
maxx = anss;
}
printf("%d\n", maxx);
}
}
return 0;
}
G
有n个数，每次可以合并k个数，花费的代价为数的和，新数为所有原数的和，如果代价不能超过T，求k的最小值。
$n \leq 100000$
【题解】
二分+优先队列+卡时+fread能过，复杂度$O(Tnlog^2n)$
但是由于插入的单调性，所以我们可以用两个队列维护。一个维护旧的一个维护合并后的。
唯一要注意的是如果$(n-1) mod (k-1) \not= 0$（因为合并一次消去了$k-1$个数，总共要消去$n-1$个数，那么我们把小的提前合并即可。复杂度$O(Tnlogn)$
# include <stdio.h>
# include <queue>
# include <algorithm>
# define R register
using namespace std;
typedef long long ll;
int T, n;
ll t;
ll a[100010];
int l, r, mid, ans;
queue<ll> q1, q2;
inline int read() {
R int x=0;
R char ch=getchar();
while(ch > '9' || ch < '0') ch = getchar();
while(ch >= '0' && ch <= '9') {
x = (x<<3) + (x<<1) + ch - '0';
ch = getchar();
}
return x;
}
inline ll readll() {
R ll x=0;
R char ch=getchar();
while(ch > '9' || ch < '0') ch = getchar();
while(ch >= '0' && ch <= '9') {
x = (x<<3) + (x<<1) + ch - '0';
ch = getchar();
}
return x;
}
inline bool check(int k) {
R ll res, sum, ret = 0;
R int gs;
while(!q1.empty()) q1.pop();
while(!q2.empty()) q2.pop();
for (int i=1; i<=n; ++i) q1.push((ll)a[i]);
if((n-1)%(k-1) != 0) {
res = (n-1)%(k-1)+1, sum = 0;
for (int i=1; i<=res; ++i) {
sum += q1.front();
q1.pop();
}
q2.push(sum);
ret += sum;
}
while(!q1.empty()) {
sum = 0;
for (int i=1; i<=k; ++i) {
if(!q1.empty() && !q2.empty()) {
if(q1.front() <= q2.front()) sum+=q1.front(), q1.pop();
else sum += q2.front(), q2.pop();
} else if(!q1.empty()) sum += q1.front(), q1.pop();
else if(!q2.empty()) sum += q2.front(), q2.pop();
}
ret += sum;
q2.push(sum);
}
if(ret > t) return false;
sum = gs = 0;
while(!q2.empty()) {
sum += q2.front(); ++gs; q2.pop();
if(gs == k) {
q2.push(sum);
ret += sum;
sum=gs=0;
if(q2.size() == 1) break;
}
}
return ret <= t;
}
int main() {
T = read();
while(T--) {
n = read(), t = readll();
for (int i=1; i<=n; ++i) a[i] = readll();
sort(a+1, a+n+1);
l=2, r=n, ans=1000001;
while(l<=r) {
int mid = l+r>>1;
if(check(mid)) {
r=mid-1;
ans = min(ans, mid);
}
else l=mid+1;
}
printf("%d\n", ans);
}
return 0;
}
H
给出一个$n\times m$的格子，格子$(i,j)$的值为$p(i,j)$，两个格子间距离定义为格子中心的欧几里得距离，你可以选择一个格子，距离小于等于$r$的那些格子都会贡献$\frac{p(i,j)}{d+1}$，选择一个格子，使得贡献和最大。
【题解】造多项式，FFT即可。
I
求树删去一条边后分成的两个块的直径最大值的期望，为了输出方便，答案乘以$n-1$。
$ n \leq 100000$
【题解】其实就是问树删去一条边后分成的两个块的直径最大值的和了
首先预处理出树的一条直径$(a,b)$，标记直径上的边，如果枚举的不是直径上的边，答案就是直径长度。
如果枚举的是直径上的边，那么我们考虑，对于$a$和$b$为根分别预处理，得到$f1_x, f2_x$分别表示以$a$为根和以$b$为根，$x$的子树的直径大小是多少。这个可以通过树形dp预处理。
所以接下来就是查询啦，很简单啦
总复杂度$O(Tn)$
比较难拍所以附带暴力以及数据生成器（视需要自行修改）
# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
int T, n;
int head[500100], nxt[800100], to[800100], w[800100], tot=0, pos[800100];
bool inc[500100];
int fr[500100];
int u[500100], v[500100];
typedef long long ll;
ll ans=0;
int fir[500100], sec[500100], f1[500100], f2[500100], son[500100];
inline void add(int uu, int vv, int tw, int ii) {
++tot;
nxt[tot]=head[uu];
head[uu]=tot;
to[tot]=vv;
w[tot]=tw;
pos[tot]=ii;
}
int mx, res;
inline void dfs(int cur, int fa, int curw) {
if(curw > mx) {
mx = curw;
res = cur;
}
for (int i=head[cur]; i; i=nxt[i]) {
if(to[i] == fa) continue;
dfs(to[i], cur, curw+w[i]);
}
}
bool success = 0;
inline void dfsnode(int cur, int fa, int too) {
if(success) return;
if(cur == too) {
success = 1;
return ;
}
for (int i=head[cur]; i; i=nxt[i]) {
if(to[i] == fa) continue;
inc[pos[i]] = 1;
fr[pos[i]] = cur;
dfsnode(to[i], cur, too);
if(success) break;
inc[pos[i]] = 0;
fr[pos[i]] = 0;
}
}
inline void dp1(int x, int fa) {
son[x]=f1[x]=fir[x]=sec[x]=0;
for(int i=head[x]; i; i=nxt[i]) {
if(to[i] == fa) continue;
++son[x];
dp1(to[i], x);
fir[to[i]] += w[i], sec[to[i]] += w[i];
if(son[x] == 1) fir[x]=fir[to[i]];
else {
if(fir[to[i]] > fir[x]) {
sec[x] = fir[x];
fir[x] = fir[to[i]];
}
else if(fir[to[i]] > sec[x]) sec[x] = fir[to[i]];
}
f1[x] = max(f1[x], f1[to[i]]);
}
if(son[x] == 1) f1[x] = max(f1[x], fir[x]);
else if(son[x] > 1) f1[x] = max(f1[x], fir[x] + sec[x]);
}
inline void dp2(int x, int fa) {
son[x]=f2[x]=fir[x]=sec[x]=0;
for(int i=head[x]; i; i=nxt[i]) {
if(to[i] == fa) continue;
++son[x];
dp2(to[i], x);
fir[to[i]] += w[i], sec[to[i]] += w[i];
if(son[x] == 1) fir[x]=fir[to[i]];
else {
if(fir[to[i]] > fir[x]) {
sec[x] = fir[x];
fir[x] = fir[to[i]];
}
else if(fir[to[i]] > sec[x]) sec[x] = fir[to[i]];
}
f2[x] = max(f2[x], f2[to[i]]);
}
if(son[x] == 1) f2[x] = max(f2[x], fir[x]);
else if(son[x] > 1) f2[x] = max(f2[x], fir[x] + sec[x]);
}
int main() {
//freopen("hdu5886.in", "r", stdin);
//freopen("hdu5886.out", "w", stdout);
scanf("%d", &T);
while(T--) {
ans=0;
tot=0; memset(head, 0, sizeof(head));
memset(inc, 0, sizeof(inc)); success = 0;
scanf("%d", &n);
for (int i=1, tw; i<n; ++i) {
scanf("%d%d%d", &u[i], &v[i], &tw);
add(u[i], v[i], tw, i);
add(v[i], u[i], tw, i);
}
mx=-1; dfs(1, 0, 0); int posa = res;
mx=-1; dfs(posa, 0, 0); int posb = res;
//printf("%d %d\n", posa, posb);
dfsnode(posa, 0, posb);
//for (int i=1; i<n; ++i) printf("%d\n", inc[i]);
dp1(posa, 0);
//for (int i=1; i<=n; ++i) printf("i=%d, %d\n", i, f1[i]);
dp2(posb, 0);
//printf("%d\n", mx);
for (int i=1; i<n; ++i) {
if(!inc[i]) ans += (ll)mx;
else {
int from = fr[i], to = u[i]+v[i]-from;
int zj = max(f2[from], f1[to]);
ans += (ll)zj;
}
}
printf("%I64d\n", ans);
}
return 0;
}
/*
1
10
4 3 56
3 6 85
8 7 45
7 5 164
5 1 166
1 6 2
6 10 174
9 2 61
2 10 14
ans:4664
*/
# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
int T, n;
int head[500100], nxt[800100], to[800100], w[800100], tot=0, pos[800100];
bool vis[800100];
bool inc[500100];
int fr[500100];
int u[500100], v[500100], ppos[500100];
typedef long long ll;
ll ans=0;
int fir[500100], sec[500100], f1[500100], f2[500100], son[500100];
inline void add(int uu, int vv, int tw, int ii) {
++tot;
nxt[tot]=head[uu];
head[uu]=tot;
to[tot]=vv;
w[tot]=tw;
pos[tot]=ii;
vis[tot]=0;
}
int mx, res;
inline void dfs(int cur, int fa, int curw) {
if(curw > mx) {
mx = curw;
res = cur;
}
for (int i=head[cur]; i; i=nxt[i]) {
if(to[i] == fa || vis[i]) continue;
dfs(to[i], cur, curw+w[i]);
}
}
int main() {
//freopen("hdu5886.in", "r", stdin);
//freopen("hdu5886.ans", "w", stdout);
scanf("%d", &T);
while(T--) {
ans=0;
tot=0; memset(head, 0, sizeof(head));
scanf("%d", &n);
for (int i=1, tw; i<n; ++i) {
scanf("%d%d%d", &u[i], &v[i], &tw);
add(u[i], v[i], tw, i);
ppos[i] = tot;
add(v[i], u[i], tw, i);
}
for (int i=1; i<n; ++i) {
vis[ppos[i]] = vis[ppos[i]+1]=1;
mx=-1;dfs(u[i],0,0); int poss=res;
mx=-1;dfs(poss,0,0); int gg = mx;
mx=-1;dfs(v[i],0,0); poss=res;
mx=-1;dfs(poss,0,0);
vis[ppos[i]] = vis[ppos[i]+1]=0;
ans+=max(mx, gg);
}
printf("%I64d\n", ans);
}
return 0;
}
#include<cstdio>
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[30000+20];
struct nod
{
int id,d;
}d[30000+20];
bool cmpid(nod x,nod y)
{
return x.id<y.id;
}
bool cmp(nod x,nod y)
{
if(x.d!=y.d)return x.d<y.d;
else return x.id<y.id;
}
int main()
{
freopen("hdu5886.in","w",stdout);
srand(time(NULL));
puts("10");
for (int jj=1;jj<=10;++jj) {
int n=10;
cout<<n<<endl;
for(int i=1;i<=n;i++)
{
d[i].d=1;
d[i].id=i;
}
for(int i=1;i<=n-2;i++)a[i]=rand()%n+1;
for(int i=1;i<=n-2;i++)d[a[i]].d++;
for(int i=1;i<=n-2;i++)
{
sort(d+1,d+n+1,cmp);
int j;
for(j=1;j<=n;j++) if(d[j].d)break;
printf("%d %d %d\n",d[j].id,a[i], rand()%200+1);
d[j].d--;
sort(d+1,d+n+1,cmpid);
d[a[i]].d--;
}
sort(d+1,d+n+1,cmp);
printf("%d %d %d\n",d[n-1].id,d[n].id, rand()%200+1);
}
return 0;
}
J
求0/1背包，$T \leq 10, n \leq 100, wi, vi \leq 10^9$。
【题解】
dfs+剪枝
每次到一层做一次可分解背包判断可行性。
时间复杂度：理论$O(T2^n)$；实际：$O(能过)$
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long double ld;
typedef long long ll;
int n, m;
struct pi {
int a, b;
ld rate;
}p[110];
ll maxx = 0;
inline bool cmp(pi a, pi b) {
return a.rate > b.rate;
}
inline void dfs(int cur, ll v, ll w) {
if(w>maxx) maxx = w;
if(cur == n+1) return;
ld vv=(ld)v, ww=(ld)w;
for (int i=cur; i<=n; ++i) {
if(vv + p[i].a <= m) {
vv += p[i].a;
ww += p[i].b;
} else {
ww += (m - vv) * p[i].rate;
break;
}
}
if(ww < maxx) return;
if(v+p[cur].a<=m) dfs(cur+1, v+p[cur].a, w+p[cur].b);
dfs(cur+1, v, w);
}
int main() {
while(~scanf("%d%d", &n, &m)) {
maxx = 0;
for (int i=1; i<=n; ++i) {
scanf("%d%d", &p[i].a, &p[i].b);
p[i].rate = (ld)p[i].b/p[i].a;
}
sort(p+1, p+n+1, cmp);
dfs(1, 0, 0);
printf("%I64d\n", maxx);
}
return 0;
}
K
求一张图1~n的最短路中的图的最小割
$n \leq 1000$
【题解】
裸题 代码by zhouyis
复杂度 $O(Tn^2)$
#include<map>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<complex>
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;
#define inf 1001001001
#define infll 1001001001001001001LL
#define ll long long
#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl
#define gmax(a,b) (a)=max((a),(b))
#define gmin(a,b) (a)=min((a),(b))
#define Ri register int
#define gc getchar()
#define il inline
il int read(){
bool f=true;Ri x=0;char ch;while(!isdigit(ch=gc))if(ch=='-')f=false;while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=gc;}return f?x:-x;
}
#define gi read()
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
int n,m;
namespace maxf{
const int N=1005,M=233333;
struct edge{
int to,next;ll cap;
}e[M];
int last[N],cnt=1;int h[N];
void insert(int u,int v,ll cap,ll revc){
e[++cnt]=(edge){v,last[u],cap};last[u]=cnt;
e[++cnt]=(edge){u,last[v],revc};last[v]=cnt;
}
bool bfs(int s,int t){
memset(h,-1,sizeof(h));
h[s]=0;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=last[u];i;i=e[i].next){
if(e[i].cap&&h[e[i].to]==-1){
h[e[i].to]=h[u]+1;
q.push(e[i].to);
}
}
}
return h[t]!=-1;
}
ll dfs(int v,int t,ll f){
if(v==t) return f;
ll used=0,w=0;
for(int u=last[v];u;u=e[u].next){
if(h[e[u].to]==h[v]+1){
w=dfs(e[u].to,t,min(f-used,e[u].cap));
e[u].cap-=w;
e[u^1].cap+=w;
used+=w;
if(used==f) return f;
}
}
if(!used) h[v]=-1;
return used;
}
ll maxflow(int s,int t){
ll ans=0;
while(bfs(s,t)){
ans+=dfs(s,t,(1ll<<60));
if(ans>=(1ll<<60))return ans;}
return ans;
}
int main(){
cout<<maxflow(1,n)<<endl;
}
}
namespace graph_theory{
#define M 220000
struct edge{
int to,next,v,cost;
}e[M];
#define N 10000
int cnt,last[N],inq[N],dis[N];
//dis:length of shorest path
//inq: is point "i" be pushed into the queue
void insert(int a,int b,int c,int d){
e[++cnt]=(edge){b,last[a],c,d};last[a]=cnt;
}
int spfa(int s,int t){
queue<int>q;
for(int i=1;i<=N-1;i++)dis[i]=(1e9);
q.push(s);dis[s]=0;inq[s]=true;
while(!q.empty()){
int c=q.front();q.pop();inq[c]=false;
for(int i=last[c];i;i=e[i].next){
if(dis[e[i].to]>dis[c]+e[i].v){
//update dis[e[i].to]
dis[e[i].to]=dis[c]+e[i].v;
if(!inq[e[i].to]){
q.push(e[i].to);
inq[e[i].to]=true;
}
}
}
}
return dis[t];
}
int main(){
memset(last,0,sizeof(last));cnt=1;
n=gi;m=gi;
for(int i=1;i<=m;i++){
int a,b,c;
a=gi;b=gi;c=gi;
insert(a,b,1,c);
insert(b,a,1,c);
}
spfa(1,n);
memset(maxf::last,0,sizeof(maxf::last));maxf::cnt=1;
for(int i=1;i<=n;i++){
for(int j=last[i];j;j=e[j].next){
if(dis[i]+e[j].v==dis[e[j].to]){
maxf::insert(i,e[j].to,e[j].cost,0);
}
}
}
return 0;
}
#undef N
#undef M
}
int main(){
int T=gi;
while(T--){
graph_theory::main();
maxf::main();
}
}
L
给出$n$个数，$m$次询问问去掉三个数（可以相同）后，剩下的数能否用不超过10个组成87.
$n \leq 100$
【题解】
bitset dp，时间有点紧，所以用读入优化就能过啦，982ms。
理论时间复杂度$O(Tn^3 \times 10 \times 87)$，实际复杂度$O(能过)$。
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <bitset>
using namespace std;
typedef long long ll;
bitset<90> f[11];
int ans[60][60][60];
int a[100], n, m;
int q[4];
inline int read() {
int x=0;char ch=getchar();
while(ch>'9' || ch<'0') ch=getchar();
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x;
}
inline int chk(int x, int y, int z) {
for (int i=0; i<=n; ++i) f[i].reset();
f[0][0]=1;
for (int i=1; i<=n; ++i) {
if(i==x || i==y || i==z) continue;
for (int t=10; t>=1; --t)
f[t] |= f[t-1]<<a[i];
}
if(f[10][87] == 1) return 1;
return 0;
}
int main() {
int T; T=read();
while(T--) {
n=read();
memset(ans, 0, sizeof(ans));
for (int i=1; i<=n; ++i) a[i]=read();
for (int i=1; i<=n; ++i)
for (int j=i; j<=n; ++j)
for (int k=j; k<=n; ++k)
if(chk(i, j, k))
ans[i][j][k] = 1;
m=read();
while(m--) {
for (int i=1; i<=3; ++i) q[i]=read();
sort(q+1,q+3+1);
printf("%s\n", ans[q[1]][q[2]][q[3]] ? "Yes" : "No");
}
}
return 0;
}
M
给出一个字符串，要求支持往后加一个字符，询问字符串T（是原串子串，以$[L,R]$形式给出），问T中的一个子串最长的至少出现两次的子串的长度，强制在线。
【题解】后缀树（自动机）+可持久化线段树+LCT。具体不会。
2023年4月19日 16:16
The MBOSE will provide the SSLC model papers with the previous exam solved question bank along subject experts suggested study material along bit questions for Guessing the Important to Short Answer Questions, Very Short Answer Questions and objective type Questions to all Medium Collages Unit tests, modelpapers2019.com Quarterly, Half Yearly, annual final public examination test of March 2023 under Meghalaya Board of School Education.