BZOJ 5496: [2019省队联测]字符串问题 (后缀数组+主席树优化建图+拓扑排序)

题意

略

分析

考场上写了暴力建图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\n", 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;

	}

}

常数巨大

BZOJ 5496: [2019省队联测]字符串问题 (后缀数组+主席树优化建图+拓扑排序)

题意

分析

CODE