【BZOJ 3881】[COCI2015] Divljak

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3881
神犇题解:http://trinkle.is-programmer.com/2015/6/30/bzoj-3881.100056.html

解题报告

考虑把Alice的串建成AC自动机
那么每一次用Bob的串去匹配就是Fail树上一些树链的并
这个用BIT+虚树无脑维护一下就可以了

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 2000009;
const int LOG = 26;
const int SGZ = 26;

int in[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

class Ac_Automaton{
int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N];
int head[N], to[N], nxt[N], ot[N], fa[N][LOG];
class FenwickTree{
int mx, sum[N];
public:
	inline void init(int nn) {
		mx = nn;
	}
	inline void modify(int p, int d) {
		for (int i = p; i <= mx; i += lowbit(i)) {
			sum[i] += d;
		}
	}
	inline int query(int l, int r) {
		int ret = 0;
		for (int i = l - 1; i > 0; i -= lowbit(i)) {
			ret -= sum[i];
		}
		for (int i = r; i; i -= lowbit(i)) {
			ret += sum[i];
		}
		return ret;
	}
private:
}bit;
public:
	inline void insert(char *s, int nn, int id) {
		int w = root;
		for (int i = 1; i <= nn; i++) {
			int cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
			}
			w = ch[w][cc];
		} 
		pos[id] = w;
	}
	inline void build() {
		static queue<int> que;
		for (int i = 0; i < SGZ; i++) {
			if (ch[root][i]) {
				que.push(ch[root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			AddEdge(fail[w], w);
			for (int i = 0; i < SGZ; i++) {
				if (!ch[w][i]) {
					ch[w][i] = ch[fail[w]][i];
				} else {
					que.push(ch[w][i]);
					fail[ch[w][i]] = ch[fail[w]][i];
				}
			}
		}
		DFS(0, 0);
		for (int j = 1; j < LOG; j++) {
			for (int i = 0; i <= cnt; i++) {
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
			}
		}
		bit.init(cnt + 1);
	} 
	inline void match(char *s, int nn) {
		static vector<int> vt[N];
		static int que[N], stk[N], vis[N]; 
		int qtot = 0, stot = 0, vtot = 0;
		que[++qtot] = root;
		for (int i = 1, w = root; i <= nn; i++) {
			w = ch[w][s[i] - 'a'];
			que[++qtot] = w;
		}
		sort(que + 1, que + 1 + qtot);
		qtot = unique(que + 1, que + 1 + qtot) - que - 1;
		sort(que + 1, que + 1 + qtot, cmp);
		for (int i = 1; i <= qtot; i++) {
			if (stot) {
				int lca = LCA(que[i], stk[stot]);
				for (; stot && dep[stk[stot]] > dep[lca]; --stot) {
					if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) {
						vt[stk[stot - 1]].push_back(stk[stot]);
					} else {
						vt[lca].push_back(stk[stot]);
					}
				}
				if (stot && stk[stot] != lca) {
					stk[++stot] = lca;
					vis[++vtot] = lca;
				}
			} 
			stk[++stot] = que[i];
			vis[++vtot] = que[i];
		}
		for (; stot > 1; --stot) {
			vt[stk[stot - 1]].push_back(stk[stot]);
		}
		update(root, vt);
		for (int i = 1; i <= vtot; i++) {
			vt[vis[i]].clear();
		}
	}
	inline int query(int id) {
		return bit.query(in[pos[id]], ot[pos[id]]);
	}
private:
	inline void update(int w, vector<int> *vt) {
		for (int i = 0; i < (int)vt[w].size(); i++) {
			bit.modify(in[w], -1);
			bit.modify(in[vt[w][i]], 1);
			update(vt[w][i], vt);
		}
	}
	inline int LCA(int a, int b) {
		if (dep[a] < dep[b]) {
			swap(a, b);
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (dep[fa[a][j]] >= dep[b]) {
				a = fa[a][j];
			}
		}
		if (a == b) {
			return a;
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (fa[a][j] != fa[b][j]) {
				a = fa[a][j];
				b = fa[b][j];
			}
		}
		return fa[a][0];
	} 
	static bool cmp(int a, int b) {
		return in[a] < in[b];
	}
	inline void DFS(int w, int f) {
		static int tt = 0;
		in[w] = ++tt;
		dep[w] = dep[fa[w][0] = f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			DFS(to[i], w);
		}
		ot[w] = tt;
	}
	inline void AddEdge(int u, int v) {
		static int E = 1;
		to[++E] = v; nxt[E] = head[u]; head[u] = E;
	}
}ac;

int main() {
	static char ss[N];
	int n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%s", ss + 1);
		int len = strlen(ss + 1);
		ac.insert(ss, len, i);
	}
	ac.build();
	int m = read();
	for (int i = 1; i <= m; i++) {
		if (read() == 1) {
			scanf("%s", ss + 1);
			int len = strlen(ss + 1);
			ac.match(ss, len);
		} else {
			printf("%d\n", ac.query(read()));
		}
	}
	return 0;
}

【AtCoder】[Grand Contest 015 E] Mr.Aoki Incubator

相关链接

题目传送门:http://agc015.contest.atcoder.jp/tasks/agc015_e

解题报告

我们发现:对于任意一个时刻,一个病原体引发的感染者一定是一个区间
那么问题转化为选一些线段来覆盖整个序列,这个用可以线性维护
总的时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;
 
const int N = 200009;
const int MOD = 1000000007;
 
int n, np[N], arr[N];
struct Data{
	int x, v; 
	inline bool operator < (const Data &D) const {
		return x < D.x || (x == D.x && v < D.v);
	}
}d[N], seg[N];
 
inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}
 
inline bool cmpv(int aa, int bb) {
	return d[aa].v < d[bb].v;
}
 
class Fenwick_Tree{
	int sum[N], uve, cur = 1;
public:
	inline void modify(int p, int x) {
		uve = (uve + x) % MOD;
		sum[p] = (sum[p] + x) % MOD;
	}	
	inline int query(int p) {
		while (cur < p) {
			++cur;
			sum[cur] = (sum[cur] + sum[cur - 1]) % MOD;
		}
		return ((uve - sum[p - 1]) + MOD) % MOD;
	}
}BIT;
 
int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		d[i].x = read();
		d[i].v = read();
		arr[i] = i;
	}
	sort(d + 1, d + 1 + n);
	sort(arr + 1, arr + 1 + n, cmpv);
	for (int i = 1; i <= n; i++) {
		np[arr[i]] = i;
	}
	for (int i = 1, cur = 0; i <= n; ++i) {
		seg[i].x = cur = max(cur, np[i]);
	}
	for (int i = n, cur = n + 1; i; --i) {
		seg[i].v = cur = min(cur, np[i]);
	}
	sort(seg + 1, seg + 1 + n);
	BIT.modify(1, 1);
	for (int i = 1; i <= n; i++) {
		int tmp = BIT.query(seg[i].v);
		BIT.modify(seg[i].x + 1, tmp);
	}
	printf("%d\n", BIT.query(n + 1));
	return 0;
}

【Codeforces 749E】Inversions After Shuffle

相关链接

题目传送门:http://codeforces.com/contest/749/problem/E
官方题解:http://codeforces.com/blog/entry/49186

解题报告

考虑从期望的定义下手
就是要求所有区间的逆序对的和
于是我们枚举右端点,然后算贡献
用$BIT$来维护,时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 100009;

int n, p[N]; 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Fenwick_Tree{
	double sum[N];
	public:
		inline void init() {
			memset(sum, 0, sizeof(sum));
		}
		inline void modify(int p, int d = 1) {
			for (int i = p; i <= n; i += lowbit(i)) {
				sum[i] += d;
			}
		}
		inline double query(int p) {
			double ret = 0;
			for (int i = p; i; i -= lowbit(i)) {
				ret += sum[i];
			}
			return ret;
		}
}BIT;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		p[i] = read();
	}
	double ans = 0, psm = 0;
	for (int i = n; i; i--) {
		ans += BIT.query(p[i]);
		BIT.modify(p[i]);	
	}	
	ans *= n * (n + 1ll);
	BIT.init();
	for (int i = 1; i <= n; i++) {
		LL t1 = BIT.query(p[i]);
		LL t2 = i * (i - 1ll) / 2 - t1;
		ans += (psm += t1 - t2);
		BIT.modify(p[i], i);
	}
	printf("%.15lf\n", ans / n / (n + 1));
	return 0;
}

【BZOJ 4900】[CTSC2017] 密钥

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4900
原版题面:https://oi.qizy.tech/wp-content/uploads/2017/05/ctsc2017_day1.pdf

解题报告

我们做一个前缀和,发现问题变为询问一个区间内大于某个数的数有多少个
区间我们可以用滑动窗口来维护
询问大于某个数有多少可以用$BIT$来维护

总的时间复杂度:$O(n \log n)$
因为本题数据很水,所以过$10^7$的数据很轻松

当然标算是$O(n)$的算法
但我忘掉怎么证正确性了 qwq

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 40000009;

int k,n,seed,s,sum[N];
int ans1, ans2, ans3, MX, INF;
bool p[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int R() {
	seed = ((seed * 12321) ^ 9999) & 32767;
	return seed;
}

class Fenwick_Tree{
	int arr[N],tot;
	public:
		inline void modify(int pos, int delta) {
			tot += delta;
			for (int i = pos + MX; i <= INF; i += lowbit(i)) {
				arr[i] += delta;
			}
		}
		inline int query(int pos) {
			int ret = tot;
			for (int i = pos + MX; i > 0; i -= lowbit(i)) {
				ret -= arr[i];
			}
			return ret;
		}
}B1,B2;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	k = read(); 
	seed = read();
	s = read();
	n = k * 2 + 1;
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		p[i] = (R() >> 7) & 1;
		cnt += p[i];
	}
	int cur = 1;
	while (cnt > k) {
		while (!p[cur]) {
			++cur;
		}
		p[cur] = 0;
		--cnt;
	}
	while (cnt < k) {
		while (p[cur]) {
			++cur;
		}
		p[cur] = 1;
		++cnt;
	}
	for (int i=1;i<=n;i++) {
		p[i + n] = p[i];
	}
	
	for (int i = 1; i <= n * 2; ++i) {
		sum[i] = sum[i - 1] + (p[i]? 1: -1);
		MX = max(MX, abs(sum[i]));
	}
	INF = MX << 1;
	for (int i = 1; i <= n; i++) {
		if (p[i]) {
			B1.modify(sum[i], 1);
		} else {
			B2.modify(-sum[i], 1);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!p[i]) {
			int tmp = B1.query(sum[i]);
			if (tmp == 0) {
				ans1 = i;
			} else if (tmp == s) {
				ans2 = i;
			}
			B2.modify(-sum[i], -1);
			if (B2.query(-sum[i]) == s) {
				ans3 = i;
			}
			if (ans1 && ans2 && ans3) {
				break;
			}
		} else {
			B1.modify(sum[i], -1);
		}
		if (p[i + n]) {
			B1.modify(sum[i + n], 1);
		} else {
			B2.modify(-sum[i + n], 1);
		}
	}
	
	printf("%d\n%d\n%d", ans1, ans2, ans3);
	return 0;
}

【HDU 4630】No Pain No Game

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4630
神犇题解:http://www.cnblogs.com/zhsl/p/3234099.html

吐槽

最开始写了一个复杂度玄学的莫队,然后被卡$T$了
然后又写了一个$O(n \log n \sqrt{n \log n})$的$KD-Tree$,然后又被卡$T$了

然后看了题解就给跪了,这™不是傻逼题吗?

解题报告

我们将询问按照左端点排序,然后降序处理
这样每一次询问就相当于问一个后缀的前缀

然后考虑新加入最左边一个数$a_i$对于答案的影响
显然我们可以枚举因数$v$,然后记$v$上一次出现的位置为$last_v$
那么右端点在$i \sim last_v$之间的询问都会计算到这个$\gcd$
于是我们用$BIT$维护一个前缀最值就可以了
时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 50009;

int n,m,pos[N],arr[N],last[N],ans[N];
struct Query{
	int l,r,id;
	inline bool operator < (const Query &Q) const {
		return l < Q.l;
	}
}q[N];
vector<int> que[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Fenwick_Tree{
	#define lowbit(x) ((x)&-(x))
	int mx[N];
	public:
		inline void init() {
			memset(mx, 0, sizeof(mx));
		}
		inline void modify(int p, int v) {
			for (int i=p;i<=n;i+=lowbit(i)) {
				mx[i] = max(mx[i], v);
			}
		}
		inline int query(int p) {
			int ret = 1;
			for (int i=p;i;i-=lowbit(i)) {
				ret = max(ret, mx[i]);
			}
			return ret;
		}
}BIT;

int main() {
	for (int T=read();T;T--) {
		n = read();
		for (int i=1;i<=n;i++) {
			que[i].clear();
			arr[i] = read();
			pos[arr[i]] = i; 
		}
		for (int i=2;i<n;i++) {
			for (int j=i;j<=n;j+=i) {
				que[pos[j]].push_back(i);
			}
		} 
		m = read();
		for (int i=1,l,r;i<=m;i++) {
			q[i].l = read();
			q[i].r = read();
			q[i].id = i;
		}
		sort(q+1, q+1+m);
		BIT.init();
		memset(last,60,sizeof(last));
		for (int i=m,cur=n+1;i;i--) {
			while (cur > q[i].l) {
				--cur;
				for (int j=0;j<que[cur].size();j++) {
					int v = que[cur][j];
					if (last[v] <= n) {
						BIT.modify(last[v], v);
					}
					last[v] = cur;
				}
			}
			if (q[i].l == q[i].r) ans[q[i].id] = 0;
			else ans[q[i].id] = BIT.query(q[i].r);
		}
		for (int i=1;i<=m;i++) {
			printf("%d\n",ans[i]);
		}
	}
	return 0;
}

【BZOJ 4231】回忆树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4231
数据生成器:http://paste.ubuntu.com/24366714/
神犇题解:http://www.cnblogs.com/clrs97/p/5467637.html

解题报告

首先我们如果最终一个串出现的位置会越过$LCA$
那么我们可以把这一部分的情况单独拿出来,暴力跑$KMP$

剩下就是单纯地从根节点向下,或者向上的路径中出现了多少次
这不难让我们想到广义后缀自动机,但似乎这题并不能用

考虑另一个方法,把所有模式串建成AC自动机
然后在原树上$DFS$,进入一个点时将其在AC自动机对应的结点权值$+1$
退出来的时候将其$-1$,那么我们在需要询问的时候统计一下子树的权值和就可以了

总时间复杂度:$O(n \log n + \sum |S|)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 600009;

int n,m,head[N],nxt[M],to[M],cost[M],U[N];
int pp[N][2],ans[N],dep[N],fa[N][20],C[N];
vector<pair<int,int> > qry[N]; 

class AC_Automaton{
	int dfs_cnt,ch[M][26],fail[M],in[M],out[M];
	queue<int> que; vector<int> sn[M]; 
	struct Fenwick_Tree{
		int sum[M],sz;
		inline int lowbit(int x) {return x & -x;}
		inline void modify(int w, int delta) {
			for (int i=w;i<=sz;i+=lowbit(i)) sum[i] += delta;
		}
		inline int query(int l, int r) {
			int ret = 0; l--;
			for (int i=l;i;i-=lowbit(i)) ret -= sum[i];
			for (int i=r;i;i-=lowbit(i)) ret += sum[i];
			return ret;
		}
	}BIT;
	public:
		inline void build() {
			for (int i=0;i<26;i++) ch[0][i]=1;
			que.push(1); fail[1] = 0;
			while (!que.empty()) {
				int w = que.front(); que.pop();
				sn[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i]) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else ch[w][i] = ch[fail[w]][i];
				}
			}
			DFS(1);
			BIT.sz = dfs_cnt;
		}
		inline int insert(char *s) {
			static int cnt = 1;
			int w = 1, len = strlen(s+1);
			for (int i=1,c;i<=len;i++) {
				if (!ch[w]-'a']) ch[w] = ++cnt;
				w = ch[w]; 
			} 
			return w;
		}
		inline int query(int p) {
			return BIT.query(in[p], out[p]);
		}
		inline void modify(int p, int delta) {
			BIT.modify(in[p], delta);
		}
		inline int move(int w, int c) {
			return ch[w];
		}
	private:
		void DFS(int w) {
			in[w] = ++dfs_cnt;
			for (int i=sn[w].size()-1;~i;i--)
				if (!in[sn[w][i]]) DFS(sn[w][i]);
			out[w] = dfs_cnt;
		}
}ac;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	for (int j=19;~j;j--) if (dep[fa[a][j]] >= dep[b]) a = fa[a][j];
	if (a == b) return a;
	for (int j=19;~j;j--) if (fa[a][j] != fa[b][j]) a = fa[a][j], b = fa[b][j];
	return fa[a][0];
}

void pre(int w, int f) { 
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) 
		C[to[i]] = cost[i], pre(to[i], w);
}

void solve(int w, int p) { 
	for (int i=qry[w].size()-1,f;~i;i--) {
		if (qry[w][i].first>0) f = 1; else f = -1, qry[w][i].first *= -1;
		ans[qry[w][i].first] += ac.query(pp[qry[w][i].first][qry[w][i].second]) * f;
	}
	for (int i=head[w],tmp;i;i=nxt[i]) {
		if (dep[to[i]] > dep[w]) {
			tmp = ac.move(p, cost[i]); 
			ac.modify(tmp, 1); 
			solve(to[i], tmp);
			ac.modify(tmp, -1); 
		}
	}
}

inline int dif(int &u, int &v, int lca, char *s, int len) {
	static char ss[M]; static int NXT[M]; int tot = 0, TOT;
	int w = u, l = dep[u] - dep[lca] - len + 1, ret = 0;
	if (l > 0) {for (int j=0;l;l>>=1,++j) if (l&1) w = fa[w][j]; u = w;} 
	while (w != lca) ss[++tot] = C[w] + 'a', w = fa[w][0];
	w = v; l = dep[v] - dep[lca] - len + 1;
	if (l > 0) {for (int j=0;l;l>>=1,++j) if (l&1) w = fa[w][j]; v = w;}
	TOT = (tot += dep[w] - dep[lca]);
	while (w != lca) ss[tot--] = C[w] + 'a', w = fa[w][0];
	
	for (int i=1,w;i<=len;i++) {
		for (w=NXT[i];w&&s[w+1]!=s[i+1];w=NXT[w]);
		NXT[i+1] = w + (s[w+1] == s[i+1]);
	}
	for (int i=1,w=0;i<=TOT;i++) {
		for (;w&&s[w+1]!=ss[i];w=NXT[w]);
		w += s[w+1] == ss[i];
		ret += w == len;
	} 
	return ret;
}

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		char c[2]; scanf("%s",c);
		AddEdge(u, v, c[0] - 'a');
	} 
	pre(1, 1); 
	for (int j=1;j<=19;j++) 
		for (int i=1;i<=n;i++) 
			fa[i][j] = fa[fa[i][j-1]][j-1];
	char pat[300009];
	for (int i=1,u,v,lca,ll,p1,p2;i<=m;i++) {
		U[i] = u = read(); v = read(); lca = LCA(u, v);
		scanf("%s",pat+1); pp[i][0] = ac.insert(pat); ll = strlen(pat+1);
		qry[u].push_back(make_pair(i,1)); qry[v].push_back(make_pair(i,0)); 
		ans[i] += dif(u, v, lca, pat, ll); 
		qry[u].push_back(make_pair(-i,1)); qry[v].push_back(make_pair(-i,0));
		for (int l=1,r=ll;l<r;l++,r--) swap(pat[l], pat[r]); pp[i][1] = ac.insert(pat);
	} 
	ac.build();
	solve(1, 1);
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

【CodeChef TREEP】Period on tree

相关链接

题目传送门:https://www.codechef.com/NOV15/problems/TREEP
中文题面:http://www.codechef.com/download/translated/NOV15/mandarin/TREEP.pdf
官方题解:https://discuss.codechef.com/questions/76897/treep-editorial

题目大意

给定一个$n(n \le 200000)$个结点的树,每条边上有一个小写字母
定义$Str_{u,v}$为从$u$走到$v$将路径上的小写字母按顺序拼起来组成的字符串
给定$m(m \le 200000)$个操作,操作分两类:

  1. 输入$u,v$,询问$Str_{u,v}$的循环节最短为多长
  2. 输入$u,v,c$,表示将$u \to v$这条边上的字符改成$c$

解题报告

这么奇怪的题目,一看就只能是$Hash$来做
我们不难发现,若循环节为$l$,串长$len$,那么$\forall x \in (l,len]$若$x \equiv 0(\bmod l)$则$x$也是循环节
于是如果我们可以$O(\log n)$判定$l$是不是原串的循环节,我们就可以在$O(n \log^2 n)$的时间复杂度内解决这个问题了

我们发现,若是循环节,那么开头那一段的$Hash$值不仅可以整除整个串的$Hash$值,而且等于一个等比数列
于是我们就可以用BIT维护一个到根的前缀和,然后将判定优化到$O(\log n)$

Code

这是考试的代码,似乎没写多组数据,CC上交不了QwQ

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
const int M = N << 1;
const int SED = 37;
const int MOD = 1000000009;
 
int n,m,head[N],to[M],nxt[M],cost[M],dep[N],beg[N],END[N]; 
int POW[M],tot,pri[N],vis[N],sur[N],fa[N][20],val[N];
char pat[5];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline void AddEdge(int u, int v, int c) {
    static int E = 1; cost[E+1] = cost[E+2] = c;
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
 
class FenwickTree{
    #define lowbit(x) ((x)&(-(x)))
    int sum[N];
    public:
        inline void modify(int l, int r, int v) {
            for (int i=l-1;i;i-=lowbit(i)) sum[i] = (sum[i] - v) % MOD;
            for (int i=r;i;i-=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
        }   
        inline int query(int p) {
            int ret = 0; p = beg[p];
            for (int i=p;i<=n;i+=lowbit(i)) 
                ret = (ret + sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
}up,dw;
 
inline void prework() {
    POW[0] = sur[1] = 1; 
    for (int i=1;i<M;i++) POW[i] = (LL)POW[i-1] * SED % MOD;
    for (int i=2;i<N;i++) {
        if (!vis[i]) pri[++tot] = i, sur[i] = i;
        for (int j=1;j<=tot&&i*pri[j]<N;j++) {
            vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}
 
inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u=fa[u][j];
    if (u == v) return u;
    for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
    return fa[u][0];
}
 
void DFS(int w, int f) {
    static int dfs_cnt = 0; 
    beg[w] = ++dfs_cnt;
    fa[w][0] = f; dep[w] = dep[f] + 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            val[to[i]] = cost[i];
            DFS(to[i], w);
        }
    }
    END[w] = dfs_cnt;
    up.modify(beg[w], END[w], (LL)val[w] * POW[n-dep[w]+1] % MOD);
    dw.modify(beg[w], END[w], (LL)val[w] * POW[dep[w]] % MOD); 
}
 
inline int FA(int u, int k) {
    for (int t=0;k;k>>=1,t++) 
        if (k&1) u = fa[u][t];
    return u;
}
 
inline int query(int u, int v, int lca, int k) {
    if (dep[u] - dep[lca] >= k) {
        int ret = (up.query(u) - up.query(FA(u, k))) % MOD;
        return (((LL)ret * POW[dep[u]-1] % MOD) + MOD) % MOD;
    } else {
        int ret = (up.query(u) - up.query(lca)) % MOD;
        ret = (LL)ret * POW[dep[u] - 1] % MOD;
        int res = dep[u] + dep[v] - (dep[lca] << 1) - k;
        res = (dw.query(FA(v, res)) - dw.query(lca)) % MOD;
        res = (LL)res * POW[n + dep[u] - (dep[lca] << 1) - 1] % MOD;
        return ((res + ret) % MOD + MOD) % MOD;
    }
}
 
inline int Pow(int w, int t) {
    int ret = 1;
    for (;t;t>>=1,w=(LL)w*w%MOD)
        if (t&1) ret=(LL)ret*w%MOD;
    return ret;
}   
 
inline int query(int u, int v) {
    int lca = LCA(u, v); tot = 0;
    int len = dep[u] + dep[v] - (dep[lca] << 1);
    int STA = query(u, v, lca, len), ori = len;
    for (int c,w=len;c=sur[w],w>1;) {
        pri[++tot] = c; vis[tot] = 0;
        for (;w%c==0;w/=c) vis[tot]++; 
    }
    for (int i=1,sta,cur,PRI;i<=tot;i++) {
        PRI = pri[i];
        for (int j=1;j<=vis[i];j++) {
            sta = (LL)(Pow(POW[len/PRI], ori/len*PRI) - 1) * Pow(POW[len/PRI]-1, MOD-2) % MOD;
            cur = (LL)STA * Pow(query(u, v, lca, len / PRI), MOD-2) % MOD;
            if (sta==cur) len /= PRI;
            else break;
        }
    }
    return len;
}
 
int main() {
    prework();
    n = read(); 
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        scanf("%s",pat+1);
        AddEdge(u, v, pat[1]-'a'+1);
    }
    DFS(1, 1);
    for (int j=1;j<20;j++) {
        for (int i=1;i<=n;i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    } 
    m = read(); 
    for (int i=1,u,v,c;i<=m;i++) {
        if (read() == 1) {
            u = read(); v = read();
            printf("%d\n",query(u, v));
        } else {
            u = read(); v = read();
            if (dep[u] > dep[v]) swap(u, v);
            scanf("%s",pat+1); c = pat[1]-'a'+1;
            if (c == val[v]) continue;
            up.modify(beg[v], END[v], (LL)(c - val[v]) * POW[n-dep[v]+1] % MOD);
            dw.modify(beg[v], END[v], (LL)(c - val[v]) * POW[dep[v]] % MOD);
            val[v] = c;
        }
    } 
    return 0;
}

【日常小测】链上求和

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/03/3764237472378947264.png
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/03/4876274224.jpg

解题报告

这题就是暴力写出来之后,发现可以直接维护一个东西
于是维护一个子树和,然后支持一下换根的操作就可以辣!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 100009;
const int M = N << 1;
const int MOD = 1000000007;
  
int n,vout,head[N],to[M],nxt[M],val[N];
int tot,fa[N],yzq_in[N],yzq_out[N],sz[N];
struct Query{int v,id;}q[N];
  
class Fenwick_Tree{
    #define lowbit(x) ((x)&-(x))
    public:
        int sum[N],SUM;
        inline void modify(int p, int v) {
            for (int i=p;i<=n;i+=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
            SUM = (SUM + v) % MOD;
        } 
        inline void modify(int l, int r, int v) {
            for (int i=r;i;i-=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
            for (int i=l-1;i;i-=lowbit(i)) sum[i] = (sum[i] - v) % MOD;
        }
        inline int query(int l, int r) {
            int ret = 0;
            for (int i=r;i;i-=lowbit(i)) ret = (ret + sum[i]) % MOD;
            for (int i=l-1;i;i-=lowbit(i)) ret = (ret - sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
        inline int query(int p) {
            int ret = 0;
            for (int i=p;i<=n;i+=lowbit(i)) ret = (ret + sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
}BIT,BIT2,BIT3;
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
  
inline void Add_Edge(int u, int v) {
    static int E = 1;
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
  
inline bool cmp(const Query &A, const Query &B) {
    return A.v < B.v || (A.v == B.v && A.id < B.id);
}
  
void DFS(int w, int f) {
    fa[w] = f; yzq_in[w] = ++tot; sz[w] = 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            DFS(to[i], w);
            sz[w] += sz[to[i]];
        }
    }
    yzq_out[w] = tot;
}   
  
inline void solve(int w) {
    int ret = 0; LL cur=1,s1;
    for (int i=head[w],s,c;i;i=nxt[i]) {
        if (to[i] == fa[w]) {
            s = (BIT.SUM - BIT.query(yzq_in[w], yzq_out[w])) % MOD; 
            s1 = BIT3.query(yzq_in[w]);
            c = BIT2.query(yzq_in[w]);
            s = (s - s1 + (LL)c * n) % MOD;
            ret = (ret + (LL)sz[w] * s) % MOD; 
            ret = (ret + (LL)(n - sz[w]) * cur) % MOD;
            cur += n - sz[w];
        } else {
            ret = (ret + (LL)(n-sz[to[i]]) * BIT.query(yzq_in[to[i]], yzq_out[to[i]])) % MOD;
            ret = (ret + (LL)sz[to[i]] * cur) % MOD;
            cur += sz[to[i]];
        }
    }
    vout = (vout + (LL)ret * val[w]) % MOD;
}
 
int main() {
    n = read();
    for (int i=1;i<n;i++) Add_Edge(read(), read());
    for (int i=1;i<=n;i++) val[i] = q[i].v = read(), q[i].id = i;
    DFS(1, 1); sort(q+1, q+1+n, cmp);
    for (int i=1,p,v;i<=n;i++) {
        p = q[i].id;
        solve(p);
        BIT.modify(yzq_in[p], sz[p]);
        BIT2.modify(yzq_in[p], yzq_out[p], 1);
        BIT3.modify(yzq_in[p], yzq_out[p], sz[p]);
        for (int j=head[p],t;j;j=nxt[j]) {
            if ((t=to[j]) != fa[p]) 
                BIT3.modify(yzq_in[t], yzq_out[t], sz[t]);
        }
    }
    printf("%d\n",(vout+MOD)%MOD);
    return 0;
}

【BZOJ 4282】慎二的随机数列

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4282
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/48998981

解题报告

首先我们需要得到一个结论:一定存在一组最优解,使得所有的模糊的位置均在LIS中
现在我们来证明一下这个结论:

考虑如果有一组最优解中存在一个模糊的位置不在最优解中
那么讲这个模糊的位置换成后面的第一个确定位置的数即可,这样不会使答案变劣

于是我们就假设一个确定的位置的前缀中有a个不确定位置
那么我们把该确定位置的值减去a(相当于把那a个不确定位置在值域上留出位置)
然后对确定的串做一次LIS,然后加上不确定位置的个数即可

Code

我写LIS一直用的BIT,但PoPoQQQ大爷的LIS似乎更加优雅
他是直接维护一个最优的LIS,然后每一次lower_bound就可以了!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;

int n,m,tot,vout,_hash[N],f[N],arr[N];
char pat[10];

class Fenwick_Tree{
	int mx[N];
	public:
		inline void modify(int p, int v) {
			for (int i=p;i<=tot;i+=lowbit(i))
				mx[i] = max(mx[i], v);
		}
		inline int query(int p) {
			int ret = 0; 
			for (int i=p-1;i;i-=lowbit(i))
				ret = max(ret, mx[i]);
			return ret;
		}
	private:
		inline int lowbit(int x) {
			return x & (-x);
		}
}BIT;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read();
	for (int i=1;i<=n;++i) {
		scanf("%s",pat+1);
		if (pat[1] == 'K') {
			arr[++tot] = read() - m;
			_hash[tot] = arr[tot];		
		} else ++m;
	}
	n = tot; sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		f[i] = BIT.query(arr[i]) + 1;
		vout = max(f[i], vout);
		BIT.modify(arr[i], f[i]);
	} 
	printf("%d\n",vout + m);
	return 0;
}

【AtCoder】[Regular Contest 068 E] Snuke Line

相关链接

题目传送门:http://arc068.contest.atcoder.jp/tasks/arc068_c
数据生成器:http://paste.ubuntu.com/23948002/
官方题解:https://arc068.contest.atcoder.jp/editorial

解题报告

设一个间隔$d$,一种物品的覆盖区间长度为$L$
若 $L \ge d$ 则一定能取,否则只会被遍历到一次
于是我们就从小到达枚举$d$,同时维护$L$,把$L < d$的扔到$BIT$里就可以啦!
复杂度: $O(n{log^2}n)$,不过因为$BIT$的常数关系,所以跑得飞快

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000+9;

int n,m;
struct Event{
	int l,r,len;
	inline Event() {}
	inline Event(int _l, int _r) {l = _l; r = _r; len = r - l + 1;}
	inline bool operator < (const Event &B) const {return len < B.len;}
}e[N];

class Fenwick_Tree{
	int cnt[N];
	public:
		inline void modify(int l, int r) {
			for (int i=l-1;i;i-=lowbit(i)) cnt[i]--;
			for (int i=r;i;i-=lowbit(i)) cnt[i]++; 
		}
		inline int query(int p) {
			int ret = 0;
			for (int i=p;i<=m;i+=lowbit(i)) ret += cnt[i];
			return ret;
		}
	private:
		inline int lowbit(int x) {
			return x & -x;
		}
}BIT; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); m = read();
	for (int i=1,l,r;i<=n;i++) {
		l = read(); r = read();
		e[i] = Event(l, r);
	}
	sort(e+1, e+1+n);
	for (int d=1,p=1,sta=n;d<=m;d++) {
		for (;p<=n&&e[p].len==d-1;p++) {
			--sta;
			BIT.modify(e[p].l, e[p].r);
		}
		int vout = 0;
		for (int i=d;i<=m;i+=d) 
			vout += BIT.query(i);
		printf("%d\n",vout+sta);
	}
	return 0;
}