【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;
}

【日常小测】链上求和

相关链接

题目传送门: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;
}

【UVa 10635】Prince and Princess

题目传送门:https://uva.onlinejudge.org/index.php&problem=1576
中文题面:《算法竞赛·入门经典·训练指南》P66

这题真的是好妙啊!
wv6v0iqq6vgq9xxczbs2c

首先O(n^4)的DP大家都会吧?
来说一说O(n*log(n))的做法:
将A串重新编号为1、2、3、4、5····
然后将编码的对应关系应用到B上面去
这样的话,就变成了求B的LIS了
于是搞一个BIT什么的就可以辣!

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

const int N = 250+9;
const int M = N * N;

int n,m,q,p,A[M],B[M],trans[M],vout[M];

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;
}

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int MX[M];
	
	inline void modify(int pos, int val) {
		for (int i=pos;i<=m;i+=lowbit(i)) 
			MX[i] = max(MX[i], val);
	}
	
	inline int query(int pos) {
		int ret = 0;
		for (int i=pos;i;i-=lowbit(i)) 
			ret = max(ret, MX[i]);
		return ret;
	}
};

int main(){
	for (int k=1,T=read();k<=T;k++) {
		n = read(); m = n * n + 1;
		p = read() + 1; q = read() + 1;
		for (int i=1;i<=p;i++) A[i] = read();
		for (int i=1;i<=q;i++) B[i] = read();
		
		memset(trans,0,sizeof(trans));
		memset(vout,0,sizeof(vout));
		memset(BIT::MX,0,sizeof(BIT::MX));
		for (int i=1;i<=p;i++) trans[A[i]] = i;
		for (int i=1;i<=q;i++) B[i] = trans[B[i]];
		for (int i=1;i<=q;i++) if (B[i]) {
			vout[i] = BIT::query(B[i]) + 1;
			BIT::modify(B[i],vout[i]);
		}
		
		int ret = 0;
		for (int i=1;i<=q;i++) 
			ret = max(ret, vout[i]);
		printf("Case %d: %d\n",k,ret);
	} 
	return 0;
}

【Codeforces 707E】Garlands

题目传送门:http://codeforces.com/contest/707/problem/E
中文题面:http://blog.csdn.net/kg20006/article/details/52275809

对于每一个链单独考虑,算对于答案的贡献
时间复杂度:\(O(k \cdot {\log _2}{(n)^2} \cdot (len + q))\)

然后在算贡献那里,可以用二维树状数组
但我的代码跑了1100ms,有一份代码只跑了700ms
于是去看了看,突然想起来,这种不带修改的二维树状数组
可以把询问记下来,按照横坐标排序,然后转化为一维树状数组
好像要稍微快一点,不过我还是写的二维的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;

const int N = 2000+9;
const int M = 4000000+9;
const int INF = 1000000000;

int q,head[N],Y[M],n,m,k,X[M],W[M],nxt[M],tot,x1[N],x2[N],y1[N],y2[N],tme[N];
LL mat[N][N],vout[N];
queue<int> que[N]; 
char pat[N];

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

inline void Add(int len, int num){
	static int T = 0;
	for (int i=1;i<=len;i++) {
		nxt[++T] = head[num]; X[T] = read(); 
		Y[T] = read(); W[T] = read(); head[num] = T;
	}
}

inline void modify(int x, int y, int w){
	for (int j=y;j<=m;j+=lowbit(j))
		for (int i=x;i<=n;i+=lowbit(i))
			mat[i][j] += w; 
}

inline LL query(int x, int y){
	LL ret = 0;
	for (int j=y;j;j-=lowbit(j)) 
		for (int i=x;i;i-=lowbit(i))
			ret += mat[i][j];
	return ret;
}

int main(){
	n = read(); m = read(); k = read();
	for (int i=1;i<=k;i++) Add(read(),i);
	q = read(); for (int i=1;i<=q;i++) {
		scanf("%s",pat+1);
		if (pat[1] == 'S') que[read()].push(i);	
		else {
			tme[++tot] = i;
			x1[tot] = read(); y1[tot] = read();
			x2[tot] = read(); y2[tot] = read();
		}
	} 
	for (int i=1;i<=k;i++) que[i].push(INF);
	for (int i=1;i<=k;i++) {
		for (int j=head[i];j;j=nxt[j]) modify(X[j],Y[j],W[j]);
		int sta = 1,T=1; while (!que[i].empty()) {
			int w = que[i].front(); que[i].pop(); sta ^= 1;
			while (T <= tot && tme[T] < w) {
				int p = T++; if (sta^1) 		
				vout[p] += query(x1[p]-1,y1[p]-1) + query(x2[p],y2[p]) - query(x1[p]-1,y2[p]) - query(x2[p],y1[p]-1);
			}
		}
		for (int j=head[i];j;j=nxt[j]) modify(X[j],Y[j],-W[j]);
	} 
	for (int i=1;i<=tot;i++) printf("%I64d\n",vout[i]);
	return 0;
}