相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4196
解题报告
考虑树链剖分
线段树部分只需要支持区间赋值，查询区间中1的个数
总的时间复杂度：$O(n \log ^ 2 n)$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100009;
const int M = 200009;
int n, m, head[N], nxt[N], to[N], beg[N], ot[N];
int fa[N], top[N], hvy[N], sz[N], dep[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 void AddEdge(int u, int v) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
}
inline void DFS1(int w, int f) {
fa[w] = f;
dep[w] = dep[f] + 1;
sz[w] = 1;
for (int i = head[w]; i; i = nxt[i]) {
DFS1(to[i], w);
sz[w] += sz[to[i]];
if (sz[to[i]] > sz[hvy[w]]) {
hvy[w] = to[i];
}
}
}
inline void DFS2(int w, int t) {
static int dfc = 0;
beg[w] = ++dfc;
top[w] = t;
if (hvy[w]) {
DFS2(hvy[w], t);
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != hvy[w]) {
DFS2(to[i], to[i]);
}
}
}
ot[w] = dfc;
}
class Segment_Tree{
int cnt, root, ch[M][2], sum[M], tag[M];
public:
inline void init() {
init(root, 1, n);
}
inline int install(int w) {
int ret = 0, tmp;
while (true) {
int l = beg[top[w]], r = beg[w], len = r - l + 1;
tmp = len - modify(root, 1, n, beg[top[w]], beg[w], 1);
ret += tmp;
if (fa[top[w]] != w && tmp) {
w = fa[top[w]];
} else {
break;
}
}
return ret;
}
inline int uninstall(int w) {
return modify(root, 1, n, beg[w], ot[w], -1);
}
private:
inline void init(int &w, int l, int r) {
w = ++cnt;
if (l < r) {
int mid = l + r + 1 >> 1;
init(ch[w][0], l, mid - 1);
init(ch[w][1], mid, r);
}
}
inline void PushDown(int w, int l, int mid, int r) {
if (tag[w]) {
int ls = ch[w][0], rs = ch[w][1];
if (tag[w] == 1) {
sum[ls] = mid - l;
sum[rs] = r - mid + 1;
} else {
sum[ls] = sum[rs] = 0;
}
tag[ls] = tag[rs] = tag[w];
tag[w] = 0;
}
}
inline int modify(int w, int l, int r, int L, int R, int t) {
if (L <= l && r <= R) {
int ret = sum[w];
sum[w] = t == -1? 0: r - l + 1;
tag[w] = t;
return ret;
} else {
int mid = l + r + 1 >> 1, ret = 0;
PushDown(w, l, mid, r);
if (L < mid) {
ret += modify(ch[w][0], l, mid - 1, L, R, t);
}
if (mid <= R) {
ret += modify(ch[w][1], mid, r, L, R, t);
}
sum[w] = sum[ch[w][1]] + sum[ch[w][0]];
return ret;
}
}
}SGT;
int main() {
freopen("manager.in", "r", stdin);
freopen("manager.out", "w", stdout);
n = read();
for (int i = 2; i <= n; i++) {
AddEdge(read() + 1, i);
}
DFS1(1, 1);
DFS2(1, 1);
SGT.init();
m = read();
char cmd[20];
for (int i = 1; i <= m; i++) {
scanf("%s", cmd + 1);
if (cmd[1] == 'i') {
printf("%d\n", SGT.install(read() + 1));
} else {
printf("%d\n", SGT.uninstall(read() + 1));
}
}
return 0;
}
Hey very nice blog!
What’s up, this weekend is pleasant designed for me, as this occasion i am reading this impressive educational post here at my home.
There is certainly a great deal to learn about this issue.
I like all the points you made.
Hello to every body, it’s my first visit of this webpage; this website contains awesome and genuinely fine stuff in favor
of readers.
Why people still make use of to read news papers when in this technological world everything
is presented on web?
An outstanding share! I’ve just forwarded this onto a coworker who had been doing a little homework on this.
And he actually ordered me breakfast simply because I found it for him…
lol. So allow me to reword this…. Thanks for the meal!!
But yeah, thanks for spending some time to talk about this subject here on your website.
I simply couldn’t leave your website before suggesting that I extremely
loved the standard info an individual provide in your guests?
Is gonna be back regularly to check up on new posts
I could not resist commenting. Well written!
Hello, i think that i saw you visited my web site thus i came to “return the favor”.I am attempting to find things
to improve my site!I suppose its ok to use some of your ideas!!
I’m curious to find out what blog platform you are utilizing?
I’m having some minor security issues with my latest
website and I’d like to find something more secure. Do you
have any solutions?
Hmm it appears like your site ate my first comment (it was extremely
long) so I guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog blogger but I’m still new to everything.
Do you have any helpful hints for rookie blog writers?
I’d certainly appreciate it. plenty of fish natalielise
Do you have a spam issue on this website; I also am a blogger, and I was wanting to know
your situation; many of us have created some nice methods
and we are looking to trade strategies with others, please
shoot me an e-mail if interested.
We absolutely love your blog and find almost all of your post’s
to be exactly what I’m looking for. can you offer guest writers to write content
for you? I wouldn’t mind publishing a post or elaborating
on a lot of the subjects you write in relation to here.
Again, awesome blog!
Thanks for another informative site. Where else may I am getting that kind of info written in such
an ideal approach? I have a undertaking that I’m just now operating on, and I have been at
the glance out for such information. plenty of fish natalielise
Asking questions are truly fastidious thing if you are not understanding something fully, but
this article provides nice understanding yet. natalielise plenty of fish
Hi, I do believe this is a great website. I stumbledupon it
😉 I will come back yet again since i have book-marked it.
Money and freedom is the greatest way to change, may you be rich and
continue to guide other people.
WOW just what I was looking for. Came here by searching
for plenty of fish dating site
What’s up, this weekend is pleasant for me, as this moment i am reading this great
educational post here at my house.
Hello, i read your blog from time to time and i own a similar one and i was just
curious if you get a lot of spam comments? If so how do you protect against it,
any plugin or anything you can suggest? I get so much lately it’s driving me crazy so any assistance is
very much appreciated.
Normally I don’t learn article on blogs, but I would like to say that this write-up very forced me to try and do so!
Your writing style has been amazed me. Thanks, very great article.
Attractive element of content. I simply stumbled upon your site and in accession capital to claim that I acquire actually enjoyed
account your blog posts. Any way I will be subscribing
for your feeds or even I achievement you access consistently rapidly.
Hello there I am so glad I found your blog page, I really found you by error,
while I was searching on Google for something else, Regardless I am here
now and would just like to say many thanks for a tremendous post and a all round
exciting blog (I also love the theme/design),
I don’t have time to read it all at the moment but I have saved it and also added your RSS feeds, so when I have time I will be back to
read a great deal more, Please do keep up the excellent job.
I like it when individuals come together and share thoughts.
Great blog, stick with it!
Thanks for sharing your thoughts on minecraft games. Regards
Very soon this web page will be famous amid all blogging and site-building viewers, due to it’s pleasant articles or reviews
This is my first time pay a quick visit at here
and i am in fact impressed to read all at single place.
I like the valuable information you provide in your articles.
I will bookmark your blog and check again here regularly.
I’m quite certain I’ll learn a lot of new stuff right here!
Good luck for the next!
Fantastic items from you, man. I’ve remember
your stuff prior to and you are just extremely excellent.
I actually like what you have acquired here, certainly like what you are saying and the best
way through which you say it. You’re making it enjoyable and you continue to care for to stay it smart.
I can not wait to read far more from you. That is really a
great website.
I like the valuable info you provide in your articles.
I will bookmark your blog and check again here frequently.
I’m quite sure I’ll learn lots of new stuff right here!
Best of luck for the next!
It’s an awesome paragraph designed for all the internet people; they will get advantage from it I am sure.
I blog frequently and I really appreciate your information. This article has
really peaked my interest. I will book mark your website and keep
checking for new information about once per week. I opted
in for your RSS feed too.
Hi to all, for the reason that I am really eager of reading
this website’s post to be updated regularly. It contains nice material.
I like it whenever people get together and share ideas.
Great site, keep it up!
Why viewers still use to read news papers when in this technological globe the whole thing is available on net?
Your method of explaining everything in this paragraph is truly pleasant, every
one can simply be aware of it, Thanks a lot.
You could definitely see your skills within the article you
write. The sector hopes for even more passionate writers like
you who are not afraid to mention how they believe. Always follow your heart.
It’s going to be end of mine day, but before ending I
am reading this fantastic piece of writing to increase my knowledge.
Whats up very nice site!! Guy .. Beautiful
.. Wonderful .. I will bookmark your site and take the feeds additionally?
I’m satisfied to find numerous useful info here in the put up, we’d like work out more strategies in this regard, thank you for sharing.
. . . . .
Every weekend i used to pay a visit this website,
as i wish for enjoyment, for the reason that this this web page conations
genuinely nice funny material too.
Attractive component to content. I simply stumbled upon your weblog and in accession capital to assert that
I acquire actually enjoyed account your weblog posts.
Any way I’ll be subscribing on your feeds or
even I achievement you get admission to constantly fast.
I believe this is among the most significant info for me.
And i am satisfied studying your article. But want to remark on some basic issues, The web site style is ideal, the articles is actually nice
: D. Excellent process, cheers
It is appropriate time to make some plans for the future and
it is time to be happy. I’ve read this post and if I could I wish to
suggest you few interesting things or suggestions.
Maybe you can write next articles referring to this article.
I desire to read more things about it!
For hottest news you have to pay a visit internet and on the
web I found this web page as a most excellent
web site for most up-to-date updates.
My spouse and I stumbled over here from a different website and
thought I might as well check things out. I like what I see
so now i’m following you. Look forward to checking out your web page for a
second time.
If you are going for best contents like I do, simply go to see this web page daily because it presents feature contents, thanks
Please let me know if you’re looking for a author for your site.
You have some really good 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 articles for your blog in exchange for
a link back to mine. Please shoot me an email if interested.
Cheers!
excellent points altogether, you simply gained a logo
new reader. What would you recommend in regards to your publish that you made a few days in the past?
Any positive?
Hi there, I desire to subscribe for this weblog to get most recent updates, therefore where can i do it please assist.
Everything is very open with a really clear explanation of the issues.
It was really informative. Your site is very useful. Thank you for sharing!
What’s up friends, how is all, and what you want to say about this paragraph,
in my view its actually amazing for me.
I don’t even understand how I stopped up here,
but I assumed this put up used to be good. I
don’t know who you are however definitely you are going to a famous blogger
in the event you are not already. Cheers!
Greate pieces. Keep writing such kind of information on your page.
Im really impressed by your site.
Hello there, You have performed an incredible
job. I will certainly digg it and individually recommend to my friends.
I am sure they will be benefited from this web site.
I every time used to study piece of writing in news papers but now as I am a user of
web so from now I am using net for articles or reviews, thanks
to web.
Nice answers in return of this query with firm arguments
and explaining everything regarding that.
My brother suggested I might like this web site. He was entirely right.
This post actually made my day. You can not imagine just how much time I had spent for this information! Thanks!
This info is worth everyone’s attention. How can I find
out more?
You really make it seem really easy along with your presentation but I find this matter to be really one thing which I feel I’d by no means understand. It seems too complex and extremely huge for me. I’m looking forward for your subsequent put up, I¦ll try to get the hold of it!
Good post! We will be linking to this particularly great post on our website.
Keep up the good writing.
Please let me know if you’re looking for a article author for your weblog.
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.
Thanks!
Hey! This is my first comment here so I just wanted to give a
quick shout out and tell you I truly enjoy reading through your blog posts.
Can you recommend any other blogs/websites/forums that cover the same topics?
Thanks a ton!
Hi, There’s no doubt that your blog may be having internet browser compatibility problems.
When I look at your website in Safari, it looks fine however when opening
in IE, it has some overlapping issues. I simply wanted to give you a quick heads
up! Besides that, wonderful blog!
Hi there! Would you mind if I share your blog with my myspace group?
There’s a lot of people that I think would really enjoy your
content. Please let me know. Many thanks
Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.
You clearly know what youre talking about,
why throw away your intelligence on just posting videos to your site when you could be giving us something informative to read?
I am really impressed with your writing skills and also with the layout on your blog.
Is this a paid theme or did you modify it
yourself? Either way keep up the excellent quality writing, it is rare to see a nice blog like this one nowadays.
There’s certainly a lot to learn about this issue. I like all
of the points you have made.
I have been checking out a few of your posts and i can claim clever stuff. I will definitely bookmark your site.