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

420 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!

  25. I am extremely inspired together with your writing skills as neatly as with
    the layout in your blog. Is that this a paid subject matter or did you customize it
    yourself? Anyway stay up the excellent high quality writing, it’s uncommon to see a great weblog like
    this one nowadays..

  26. Please let me know if you’re looking for a author for your
    blog. You have some really great posts and I feel I would
    be a good asset. If you ever want to take some of the load
    off, I’d love to write some articles for your blog in exchange for
    a link back to mine. Please blast me an email if interested.

    Thank you!

  27. Greate article. Keep writing such kind of
    information on your site. Im really impressed by it.
    Hello there, You have performed an excellent job. I’ll certainly digg it and
    individually suggest to my friends. I am confident they will be
    benefited from this web site.

  28. Admiring the persistence you put into your blog and in depth information you provide.
    It’s nice to come across a blog every once in a while that isn’t the same outdated rehashed information.
    Excellent read! I’ve saved your site and I’m adding your RSS feeds to my Google account.

  29. It’s truly a nice and useful piece of information. I am satisfied that you shared this helpful information with
    us. Please keep us up to date like this. Thank you for sharing.

  30. I like the helpful information you provide on your articles.

    I’ll bookmark your blog and check again here frequently. I am slightly sure I will be informed lots of new stuff right right here!
    Best of luck for the following!

  31. I really like your blog.. very nice colors & theme.
    Did you design this website yourself or did you hire someone to do it for you?
    Plz respond as I’m looking to design my own blog and would like to know where u got this from.
    appreciate it

  32. You actually make it seem really easy with your presentation however I in finding
    this matter to be really something that I think I
    would never understand. It sort of feels
    too complicated and extremely broad for me. I am having a
    look forward in your next post, I’ll try to get the hold of it!

  33. I absolutely love your site.. Great colors & theme. Did you develop this website yourself?
    Please reply back as I’m looking to create my own blog and would love to find out
    where you got this from or what the theme is called. Thanks!

  34. This is the perfect website for anybody who hopes to understand this topic.
    You understand a whole lot its almost hard to argue with you (not that I actually would want to…HaHa).

    You certainly put a fresh spin on a subject that
    has been written about for ages. Wonderful stuff, just wonderful!

  35. Tremendous things here. I am very happy to see your article.

    Thank you so much and I’m having a look ahead to
    touch you. Will you kindly drop me a e-mail?

  36. I think this is among the so much significant info for me.
    And i’m satisfied studying your article. But wanna observation on some general issues,
    The web site style is ideal, the articles is really great : D.
    Excellent activity, cheers

  37. you are in reality a just right webmaster. The web site loading velocity is
    amazing. It sort of feels that you are doing any unique trick.
    Furthermore, The contents are masterwork.
    you have done a excellent process on this topic!

  38. Thanks for a marvelous posting! I definitely enjoyed reading it, you happen to
    be a great author.I will make certain to bookmark your
    blog and will come back very soon. I want to encourage you to definitely continue your great writing,
    have a nice weekend!

  39. hello!,I really like your writing so so much!
    percentage we be in contact extra approximately your article
    on AOL? I need a specialist on this space to resolve my
    problem. Maybe that’s you! Having a look ahead to peer you.

  40. We’re a gaggle of volunteers and starting a brand new scheme in our community.

    Your web site offered us with valuable info to work on. You have performed an impressive job and our
    whole neighborhood might be grateful to you.

  41. Please let me know if you’re looking for a article author for your
    blog. You have some really great articles and I think I
    would be a good asset. If you ever want to take some of the load off, I’d
    absolutely love to write some material for your blog in exchange for a link back to mine.
    Please blast me an email if interested. Thank you!

  42. Aw, this was a really nice post. Taking the
    time and actual effort to generate a really good article… but what can I say… I procrastinate a whole lot and don’t seem to get anything done.

  43. I have been surfing on-line more than three hours nowadays,
    yet I by no means discovered any attention-grabbing article like yours.
    It is pretty price sufficient for me. In my view,
    if all webmasters and bloggers made good content as you did, the net
    will be a lot more useful than ever before.

  44. Great post. I used to be checking continuously this weblog and I am impressed!

    Very helpful information specifically the last part 🙂 I handle such info a lot.
    I was seeking this particular info for a long time.
    Thank you and good luck.

  45. whoah this weblog is magnificent i like studying your posts.
    Keep up the good work! You know, a lot of individuals are looking around for this information, you could help them greatly.

  46. Hey very nice website!! Guy .. Beautiful .. Amazing ..
    I’ll bookmark your website and take the feeds also?
    I’m satisfied to search out a lot of useful info here within the publish, we want develop extra strategies on this regard, thanks for sharing.
    . . . . .

  47. You can definitely see your skills in the article you write.
    The world hopes for more passionate writers like you who aren’t afraid to say
    how they believe. Always go after your heart.

发表评论

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