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

179 thoughts to “【BZOJ 3881】[COCI2015] Divljak”

  1. Howdy would you mind letting me know which web host you’re using?
    I’ve loaded your blog in 3 completely different browsers and I must
    say this blog loads a lot quicker then most. Can you suggest a good web hosting provider at a fair price?
    Thanks, I appreciate it!

  2. What’s Happening i am new to this, I stumbled upon this I’ve discovered It absolutely useful and
    it has helped me out loads. I hope to give a contribution & help other customers
    like its helped me. Great job.

  3. Hmm it appears like your website ate my first comment (it was super long)
    so I guess I’ll just sum it up what I submitted and say, I’m thoroughly enjoying your blog.
    I too am an aspiring blog blogger but I’m still new to the whole thing.
    Do you have any recommendations for beginner blog writers?
    I’d really appreciate it.

  4. Fantastic goods from you, man. I’ve understand your stuff previous
    to and you’re just extremely wonderful. I actually like what
    you’ve acquired here, certainly like what you’re saying and the way in which you say it.
    You make it enjoyable and you still care for to keep it wise.

    I cant wait to read much more from you. This is really a terrific site.

  5. It is the best time to make some plans for the future and it is time to be happy.

    I have read this post and if I could I wish to suggest you some interesting things or tips.
    Maybe you could write next articles referring to this
    article. I want to read more things about it!

  6. Hi there! I realize this is somewhat off-topic however I
    needed to ask. Does operating a well-established blog
    such as yours take a lot of work? I’m completely new to
    blogging but I do write in my diary every day.
    I’d like to start a blog so I can easily share my personal experience and
    feelings online. Please let me know if you have any recommendations or tips for
    brand new aspiring blog owners. Appreciate it!

  7. Hi there! I know this is kinda off topic nevertheless I’d figured
    I’d ask. Would you be interested in exchanging links or maybe guest writing a blog article or
    vice-versa? My site goes over a lot of the same subjects as yours and I feel we could greatly benefit from each other.
    If you’re interested feel free to shoot me an email.
    I look forward to hearing from you! Great blog by the way!
    natalielise pof

  8. Today, I went to the beach front with my kids. I found a sea shell and gave it to my
    4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to her ear and screamed.
    There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is completely off topic but I had to tell
    someone! plenty of fish natalielise

  9. I’m really enjoying the theme/design of your website. Do you ever run into any web browser compatibility issues?
    A few of my blog audience have complained about my website not
    working correctly in Explorer but looks great in Safari.
    Do you have any recommendations to help fix this issue?

  10. wonderful points altogether, you just received a brand new reader.
    What would you recommend in regards to your put up that you
    just made some days in the past? Any certain?

  11. This is the right blog for everyone who really wants to understand this topic.
    You understand a whole lot its almost hard to argue with you
    (not that I actually will need to…HaHa).
    You definitely put a new spin on a subject that has been written about for years.
    Wonderful stuff, just excellent!

  12. certainly like your web site but you have to take a
    look at the spelling on quite a few of your posts.
    A number of them are rife with spelling issues and I find it
    very bothersome to tell the truth then again I’ll certainly come back again.

  13. This design is wicked! You obviously know how to keep a reader entertained.

    Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Excellent job.
    I really loved what you had to say, and more than that, how you presented it.

    Too cool!

  14. whoah this blog is wonderful i really like studying your
    articles. Keep up the great work! You understand, a lot of people are hunting round for
    this info, you can help them greatly.

  15. I know this if off topic but I’m looking into starting
    my own blog and was wondering what all is needed to get set up?
    I’m assuming having a blog like yours would cost a pretty penny?

    I’m not very internet savvy so I’m not 100% certain. Any
    suggestions or advice would be greatly appreciated. Appreciate it

  16. Hi! I’ve been reading your blog for some time now and finally got the bravery to go ahead and give you a
    shout out from Houston Texas! Just wanted to say keep up the great work!

  17. Greetings from California! I’m bored to tears at work so I
    decided to check out your site on my iphone during
    lunch break. I really like the knowledge you provide here and can’t wait to take a look when I get home.
    I’m shocked at how fast your blog loaded on my cell phone ..
    I’m not even using WIFI, just 3G .. Anyways, awesome blog!

  18. Hey there would you mind sharing which blog platform you’re working with? I’m going to start my own blog in the near future but I’m having a tough time making a decision between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design and style seems different then most blogs and I’m looking for something completely unique. P.S Apologies for getting off-topic but I had to ask!

  19. “I have discovered some important things through your website post. One other subject I would like to say is that there are numerous games out there designed particularly for toddler age kids. They include pattern identification, colors, animals, and patterns. These typically focus on familiarization instead of memorization. This will keep children and kids occupied without having a sensation like they are studying. Thanks”

  20. Les effets indésirables du Viagra – imaginés et réels. Quelles conséquences vaut-il la peine de craindre et comment faut-il les éviter – lisez l’article “Effets indésirables du Viagra – mythe et réalité”.

  21. I was wondering if you ever thought of changing the structure
    of your site? Its very well written; I love what
    youve got to say. But maybe you could a little more in the way of content so
    people could connect with it better. Youve got an awful lot of text for only having one or
    two images. Maybe you could space it out better?

  22. Heya i am for the first time here. I came acrossthis board and I find It really useful & it helped me out a lot.I hope to give something back and help others like you aidedme.

  23. I’m really enjoying the design and layout of yourwebsite. It’s a very easy on the eyes which makes it much more pleasant for me to come here andvisit more often. Did you hire out a developer to createyour theme? Outstanding work!

  24. Hello! I know this is kind of off-topic however I had to ask.
    Does operating a well-established website such as yours take a lot of work?
    I am brand new to running a blog but I do write in my diary every day.
    I’d like to start a blog so I can easily share my personal experience
    and thoughts online. Please let me know if you have any suggestions or tips for new aspiring bloggers.
    Thankyou!

发表评论

电子邮件地址不会被公开。 必填项已用*标注