题意
略
分析
考场上写了暴力建图40分溜了…(结果只得了30分)
然后只要优化建边就行了
首先给出的支配关系无法优化,就直接A向它支配的B连边.
考虑B向以B作为前缀的所有A连边,做一遍后缀数组,两个区间的左端点位置的LCP一定大于等于B的长度.在排好序的后缀数组上就是一段区间.然后用线段树优化建边.
那么用ST表倍增算一下能拓展的区间就行了.
然后由于只能向长度大于自己的连边,就按长度排序然后线段树改成主席树.
写+调一个下午…发现是sb错误…
CODE
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; while(!isdigit(ch=getc()));
for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
const int MAXS = 200005;
const int MAXA = 200005;
const int MAXB = 200005;
const int maxn = 5000005;
char s[MAXS];
int m, na, nb, la[MAXA], lb[MAXB], ra[MAXA], rb[MAXB], w[maxn]; //开始这里 w数组长度开成 MAXA+MAXB了...
struct sub {
int x, len, typ, id;
sub(){}
sub(int x, int len, int typ, int id):x(x), len(len), typ(typ), id(id){}
inline bool operator <(const sub &o)const {
return len != o.len ? len > o.len : typ < o.typ;
}
}Sub[MAXA+MAXB];
namespace _SA { //后缀数组
int f[MAXS][18], Lg[MAXS], height[MAXS], sa[MAXS], rk[MAXS], c[MAXS], x[MAXS], y[MAXS];
inline void Pre(int n) { Lg[0] = -1; for(int i = 1; i <= n; ++i) Lg[i] = Lg[i>>1] + 1; }
inline void Get_Height(int n) {
for(int i = 1, j, k = 0; i <= n; ++i) if(rk[i] > 1) {
j = sa[rk[i]-1], k = k ? k-1 : 0;
while(i+k <= n && j+k <= n && s[i+k] == s[j+k]) ++k;
height[rk[i]] = k;
}
}
inline void Init_ST(int n) {
for(int i = 1; i <= n; ++i) f[i][0] = height[i];
for(int j = 1; j <= Lg[n]; ++j)
for(int i = 1; i <= n-(1<<j)+1; ++i)
f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}
inline void Get_SA(int n, int m) {
for(int i = 1; i <= m; ++i) c[i] = 0;
for(int i = 1; i <= n; ++i) ++c[x[i]=s[i]-'a'+1];
for(int i = 2; i <= m; ++i) c[i] += c[i-1];
for(int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
for(int k = 1; k <= n; k<<=1) {
int p = 0;
for(int i = n-k+1; i <= n; ++i) y[++p] = i;
for(int i = 1; i <= n; ++i) if(sa[i] > k) y[++p] = sa[i]-k;
for(int i = 1; i <= m; ++i) c[i] = 0;
for(int i = 1; i <= n; ++i) ++c[x[i]];
for(int i = 2; i <= m; ++i) c[i] += c[i-1];
for(int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i];
swap(x, y);
x[sa[1]] = p = 1;
for(int i = 2; i <= n; ++i)
x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) ? p : ++p;
if((m=p) == n) break;
}
for(int i = 1; i <= n; ++i) rk[sa[i]] = i;
Get_Height(n); Init_ST(n);
}
}
using namespace _SA;
namespace Gragh { //建图
int deg[maxn];
vector<int> G[maxn];
inline void add(int x, int y) { ++deg[y]; G[x].push_back(y); }
LL dp[maxn]; int q[maxn];
inline LL Get_Ans(int N) {
int l = 0, r = 0;
for(int i = 1; i <= N; dp[i] = w[i], ++i)
if(!deg[i]) q[r++] = i;
LL re = 0;
while(l < r) { //topo排序
int u = q[l++];
re = max(re, dp[u]);
for(int i = 0, siz = G[u].size(), v; i < siz; ++i) {
v = G[u][i];
dp[v] = max(dp[v], dp[u] + w[v]);
if(!--deg[v]) q[r++] = v;
}
}
if(r < N) re = -1;
return re;
}
}
using namespace Gragh;
namespace Segment_Tree { //主席树
int ls[maxn], rs[maxn], tot;
void insert(int &now, int l, int r, int x, int id) {
++tot, ls[tot] = ls[now], rs[tot] = rs[now];
if(now) add(tot, now);
w[now = tot] = 0;
if(l == r) { add(now, id); return; }
int mid = (l + r) >> 1;
if(x <= mid) insert(ls[now], l, mid, x, id), add(now, ls[now]);
else insert(rs[now], mid+1, r, x, id), add(now, rs[now]);
}
void addedge(int now, int l, int r, int x, int y, int id) {
if(!now || y < l || x > r) return;
if(x <= l && r <= y) { add(id, now); return; }
int mid = (l + r) >> 1;
addedge(ls[now], l, mid, x, y, id);
addedge(rs[now], mid+1, r, x, y, id);
}
}
using namespace Segment_Tree;
int main () {
int T; read(T);
Pre(200000);
while(T--) {
int N = 0;
while(isalpha(s[++N]=getc()));
Get_SA(--N, 26);
read(na);
for(int i = 1; i <= na; ++i)
read(la[i]), read(ra[i]), Sub[i] = sub(rk[la[i]], w[i]=ra[i]-la[i]+1, 0, i);
read(nb);
for(int i = 1; i <= nb; ++i)
read(lb[i]), read(rb[i]), Sub[na + i] = sub(rk[lb[i]], rb[i]-lb[i]+1, 1, i), w[na+i] = 0;
sort(Sub + 1, Sub + na + nb + 1);
tot = na + nb; int rt = 0;
for(int i = 1; i <= na + nb; ++i) {
if(!Sub[i].typ) insert(rt, 1, N, Sub[i].x, Sub[i].id);
else {
int l = Sub[i].x, r = Sub[i].x;
for(int j = Lg[l-1]; ~j; --j)
if(l > (1<<j) && f[l-(1<<j)+1][j] >= Sub[i].len) l -= 1<<j;
for(int j = Lg[N-r]; ~j; --j)
if(r < N && f[r+1][j] >= Sub[i].len) r += 1<<j;
addedge(rt, 1, N, l, r, na + Sub[i].id);
}
}
read(m);
for(int i = 1, x, y; i <= m; ++i)
read(x), read(y), add(x, na + y);
printf("%lld
", Get_Ans(tot));
for(int i = 1; i <= tot; ++i)
deg[i] = ls[i] = rs[i] = 0, G[i].clear();
ls[0] = rs[0] = 0;
}
}
常数巨大