【NOIP十连测】[D3T3] 序列

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/test3_problem.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2016/10/solution.pdf

嗯,函数式线段树,挺好写的
但这™是NOIP模拟赛啊!

原始提问很简单,裸的函数式线段树
后来的更改,实际上就是求“询问区间包含p且询问值在数列的新旧值之间”的询问次数有多少
这样的话,可以打一打差分,然后也可以用函数式线段树搞
复杂度O(nlogn)

考试时候码的代码好丑啊……

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

const int N = 100000+9; 
const int M = 10000000;

int n,m,q,arr[N]; 
LL last_ans;
vector<int> Q_tmp[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;
}

namespace Segment_Tree{
	#define CT Segment_Tree
	int ch[M][2],sum[M],root[N],cnt,ans_tmp;
	
	void insert(int p, int &w, int l, int r, int pur) {
		w = ++cnt; 
		sum[w] = sum[p] + 1;
		memcpy(ch[w],ch[p],sizeof(ch[w]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pur < mid) {
				insert(ch[p][0], ch[w][0],l,mid-1,pur);
			} else {
				insert(ch[p][1], ch[w][1],mid,r,pur);
			}
		}
	} 
	
	inline void build_tree(){
		for (int i=1;i<=n;i++) {
			insert(root[i-1],root[i],1,n,arr[i]);
		}
	}
	
	void query(int w, int l, int r, int x, int f) {
		if (!w) {
			return;
		} else if (l < r){
			int mid = l + r + 1 >> 1;
			if (mid <= x) {
				query(ch[w][1],mid,r,x,f);
			} else {
				ans_tmp += sum[ch[w][1]]*f;
				query(ch[w][0],l,mid-1,x,f);
			} 
		} else if (l == r && l == x) {
			ans_tmp += sum[w]*f;
		} 
	}
	
	inline int query(int l, int r, int x) {
		ans_tmp = 0; 
		query(root[l-1],1,n,x,-1);
		query(root[r],1,n,x,1);
		return ans_tmp;
	}
	
	void modify(int p, int &w, int l, int r, int x, int f) {
		w = ++cnt;
		sum[w] = sum[p] + f; 
		memcpy(ch[w],ch[p],sizeof(ch[w]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (x < mid) {
				modify(ch[p][0],ch[w][0],l,mid-1,x,f);
			} else {
				modify(ch[p][1],ch[w][1],mid,r,x,f);
			}
		}
	}
	
	inline void rebuild(){
		memset(ch,0,sizeof(ch));
		memset(sum,0,sizeof(sum));
		memset(root,0,sizeof(root));
		cnt = 0;
		for (int i=1;i<=n;i++) {
			root[i] = root[i-1];
			for (int j=0,lim=Q_tmp[i].size();j<lim;j++) {
				int tmp = Q_tmp[i][j];
				if (tmp < 0) {
					modify(root[i],root[i],1,n,-tmp,-1);
				} else {
					modify(root[i],root[i],1,n,tmp,1);
				}
			}
		}
	}
	
	void ask(int w, int l, int r, int x) {
		if (!w) {
			return;
		} else if (l == r && r == x) {
			ans_tmp += sum[w];
		} else if (l < r) {
			int mid = l + r + 1 >> 1;
			if (x >= mid) {
				ask(ch[w][1],mid,r,x);
				ans_tmp += sum[ch[w][0]];
			} else {
				ask(ch[w][0],l,mid-1,x);
			}
		}
	}
	
	inline int requery(int p, int x) {
		ans_tmp = 0;
		ask(root[p],1,n,x);
		return ans_tmp;
	}
};

int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	n = read(); m = read(); q = read();
	for (int i=1;i<=n;i++) {
		arr[i] = read();
	}
	CT::build_tree();
	for (int i=1,l,r,x;i<=m;i++) {
		l = read(); r = read(); x = read();
		last_ans += CT::query(l,r,x);
		Q_tmp[l].push_back(x);
		Q_tmp[r+1].push_back(-x);
	}
	CT::rebuild();
	printf("%lld\n",last_ans);
	for (int T=1,a,b;T<=q;T++) {
		a = read() ^ last_ans;
		b = read() ^ last_ans;
		last_ans += CT::requery(a,b);
		last_ans -= CT::requery(a,arr[a]);
		arr[a] = b;
		printf("%lld\n",last_ans);
	}
	return 0;
}

271 thoughts to “【NOIP十连测】[D3T3] 序列”

  1. I don’t even understand how I ended up here, however I assumed this submit
    was once great. I do not understand who you’re but certainly you’re going to
    a well-known blogger should you are not already. Cheers!

  2. I’ve been exploring for a little for any high-quality articles or blog posts in this kind of
    area . Exploring in Yahoo I finally stumbled upon this web site.

    Reading this information So i am satisfied to show
    that I have a very excellent uncanny feeling I
    found out exactly what I needed. I most indisputably will make sure
    to do not omit this website and provides it a look on a relentless basis.

  3. Hello superb website! Does running a blog like
    this require a large amount of work? I’ve absolutely no expertise in programming but I was hoping to start
    my own blog in the near future. Anyways, should you have any suggestions or tips for
    new blog owners please share. I understand this is off topic but I just wanted to ask.
    Many thanks!

  4. Greetings! Quick question that’s totally off topic. Do you know how to make your site
    mobile friendly? My website looks weird when viewing from my apple iphone.
    I’m trying to find a template or plugin that
    might be able to correct this problem. If you have any recommendations, please share.
    Cheers!

  5. I loved as much as you’ll receive carried out right here.
    The sketch is tasteful, your authored subject matter stylish.
    nonetheless, you command get bought an shakiness over that you wish be delivering the following.
    unwell unquestionably come further formerly again as exactly the same nearly a lot often inside case you shield this
    increase.

  6. I’m amazed, I must say. Seldom do I encounter a blog that’s both
    educative and amusing, and without a doubt, you’ve hit the nail on the head.
    The problem is an issue that not enough folks are speaking intelligently
    about. Now i’m very happy that I came across
    this during my hunt for something relating to this.

  7. I think everything published was very reasonable.
    But, think on this, what if you wrote a catchier
    post title? I mean, I don’t wish to tell you how to run your blog, but suppose you added something that grabbed folk’s attention? I
    mean 【NOIP十连测】[D3T3] 序列 –
    Qizy's Database is a little vanilla. You could peek at
    Yahoo’s front page and watch how they write post titles to get people to open the links.
    You might try adding a video or a related picture or two to get people interested about what you’ve
    got to say. In my opinion, it might bring your posts a little livelier.

  8. My coder is trying to persuade me to move to .net from PHP.
    I have always disliked the idea because of the costs. But he’s tryiong none the less.
    I’ve been using Movable-type on several websites for about a year and am anxious about switching to another platform.

    I have heard fantastic things about blogengine.net. Is there a way I can transfer all my wordpress content into it?
    Any kind of help would be really appreciated!

  9. Does your blog have a contact page? I’m having a tough time locating it but, I’d like to shoot you an e-mail.

    I’ve got some ideas for your blog you might be
    interested in hearing. Either way, great website and I
    look forward to seeing it expand over time.

  10. After I originally left a comment I appear to have clicked
    the -Notify me when new comments are added- checkbox and from now on whenever a comment is added I receive 4 emails with the exact same comment.
    Perhaps there is a way you can remove me from that service?

    Kudos!

  11. The other day, while I was at work, my sister stole my apple ipad and tested to see if it
    can survive a forty foot drop, just so she can be a youtube sensation. My apple ipad is now
    destroyed and she has 83 views. I know this is completely off topic but
    I had to share it with someone!

  12. I just like the helpful info you provide to your articles.
    I’ll bookmark your weblog and take a look at again right here regularly.
    I’m somewhat sure I will be told lots of
    new stuff right right here! Good luck for the next!

  13. whoah this blog is fantastic i love reading your articles.
    Keep up the good work! You already know, a lot of people are searching around for this info,
    you could aid them greatly. natalielise plenty of fish

  14. Hello to every one, the contents existing at this web site are actually awesome for people knowledge, well, keep up the good work fellows.

  15. I am really loving the theme/design of your website.

    Do you ever run into any browser compatibility issues?

    A handful of my blog readers have complained about my blog
    not operating correctly in Explorer but looks great in Safari.
    Do you have any solutions to help fix this problem?

  16. When I initially left a comment I appear to
    have clicked the -Notify me when new comments are added- checkbox and from now on whenever
    a comment is added I get four emails with the same comment.
    Perhaps there is an easy method you can remove me from that service?
    Appreciate it!

  17. Hey There. I found your blog using msn. This is an extremely well written article. I will make sure to bookmark it and come back to read more of your useful info. Thanks for the post. I’ll definitely return.

  18. What’s Going down i’m new to this, I stumbled upon this I’ve found It absolutely helpful and it has aided me out loads.
    I am hoping to contribute & help different customers like its
    aided me. Great job.

  19. Hello There. I found your blog using msn. This is an extremely
    well written article. I will make sure to bookmark it and come back to read more of your useful info.
    Thanks for the post. I’ll certainly comeback.

  20. I don’t even know the way I stopped up right here, however I thought
    this submit was once great. I don’t understand who you might be however certainly you’re going
    to a well-known blogger if you happen to aren’t already.
    Cheers!

  21. Wow that was odd. I just wrote an incredibly long comment but after I clicked submit my comment didn’t appear. Grrrr… well I’m not writing all that over again. Anyways, just wanted to say great blog!|

  22. I think this is one of the most significant info for me. And i am glad reading your article. But should remark on few general things, The website style is ideal, the articles is really excellent : D. Good job, cheers|

  23. Hello there, I discovered your blog via Google even as
    looking for a comparable topic, your web site got here up,
    it appears great. I have bookmarked it in my google bookmarks.

    Hello there, simply become alert to your blog via Google, and located that it’s truly informative.
    I’m gonna be careful for brussels. I will appreciate in the event you proceed this in future.
    A lot of folks might be benefited out of your writing.

    Cheers!

  24. Nice post. I was checking continuously this blog and I’m inspired!
    Extremely useful info specifically the ultimate part 🙂 I maintain such info a lot.
    I was looking for this particular information for a long time.
    Thank you and best of luck.

  25. Hi there! I understand this is kind of off-topic however I had to ask.
    Does running a well-established blog like yours require a lot of work?
    I am completely new to blogging but I do write in my journal every day.
    I’d like to start a blog so I can easily share my personal experience and views online.
    Please let me know if you have any kind of suggestions or tips for brand
    new aspiring blog owners. Thankyou!

  26. Good day I am so happy I found your weblog, I really found you by mistake, while I was researching on Google for something else, Nonetheless I am here now and would just like to say thanks for a marvelous post and a all round enjoyable blog (I also love the theme/design), I don’t have time to browse it all at the moment but I have bookmarked it and also included your RSS feeds, so when I have time I will be back to read more, Please do keep up the fantastic work.|

  27. Attractive component to content. I just stumbled upon your weblog and in accession capital to say that I get actually enjoyed account your blog posts. Anyway I will be subscribing on your augment and even I achievement you get right of entry to persistently fast.|

  28. You’re so awesome! I do not think I’ve read through something like this before. So good to find another person with unique thoughts on this subject. Really.. thanks for starting this up. This web site is something that is required on the web, someone with a bit of originality!|

  29. I’m really enjoying the design and layout of your site.
    It’s a very easy on the eyes which makes it much more pleasant
    for me to come here and visit more often. Did you hire out a
    developer to create your theme? Exceptional work!

  30. Attractive part of content. I simply stumbled upon your website
    and in accession capital to assert that I acquire in fact enjoyed account your
    weblog posts. Anyway I’ll be subscribing for your augment and even I
    fulfillment you get entry to consistently fast.

  31. I’m amazed, I have to admit. Seldom do I come across a blog that’s both equally educative and entertaining, and without a doubt, you have hit the nail on the head.
    The problem is something that not enough
    people are speaking intelligently about. I’m very
    happy that I came across this in my hunt for something concerning this.

  32. Greetings! Quick question that’s entirely off
    topic. Do you know how to make your site mobile friendly?
    My weblog looks weird when viewing from my apple iphone. I’m trying
    to find a template or plugin that might be able to fix this issue.
    If you have any recommendations, please share.

    Cheers!

  33. Good day! I know this is kind of off topic but I was wondering if you knew where I could locate
    a captcha plugin for my comment form? I’m using the same
    blog platform as yours and I’m having problems finding one?

    Thanks a lot!

  34. Just wish to say your article is as astonishing.
    The clearness in your post is simply great and i can assume you are an expert on this subject.
    Fine with your permission let me to grab your feed to keep up to date with forthcoming
    post. Thanks a million and please continue the rewarding work.

  35. naturally like your web-site however you need to check
    the spelling on several of your posts. Several of them are rife with spelling problems and I
    to find it very bothersome to tell the truth nevertheless I will certainly come back again.

  36. Hello There. I discovered your blog using msn. That is a
    really smartly written article. I will be sure to
    bookmark it and return to learn more of your useful info.
    Thanks for the post. I will definitely comeback.

  37. Wow, wonderful weblog structure! How long have you been running a blog for?
    you make running a blog glance easy. The full look of your website is wonderful, as neatly as the content material!

  38. I just like the valuable info you provide to your articles.
    I’ll bookmark your weblog and check once more right here regularly.

    I am reasonably sure I will be informed a lot of new stuff right right here!
    Good luck for the next!

  39. Very great post. I simply stumbled upon your weblog and wished to say that I’ve truly enjoyed surfing around your blog
    posts. In any case I’ll be subscribing in your rss feed and I’m hoping you write again soon!

  40. Pretty nice post. I just stumbled upon your weblog and wanted
    to say that I have truly enjoyed browsing your blog posts.

    In any case I’ll be subscribing to your feed and
    I hope you write again very soon!

  41. Do you have a spam problem on this site; I also am a blogger, and I
    was wanting to know your situation; many of us have developed some nice procedures and
    we are looking to exchange methods with others, why not shoot me an e-mail
    if interested.

  42. I feel this is among the such a lot important information for me. And i’m satisfied studying your article. However wanna commentary on few general things, The website taste is perfect, the articles is in point of fact excellent : D. Just right process, cheers

  43. Hello there, just became aware of your blog through Google, and found
    that it is truly informative. I’m going to watch out for brussels.

    I will appreciate if you continue this in future. Many people will
    be benefited from your writing. Cheers!

  44. Just want to say your article is as surprising. The clarity in your post is simply excellent and i
    could assume you are an expert on this subject. Well with your permission let me to grab
    your RSS feed to keep updated with forthcoming post.
    Thanks a million and please keep up the rewarding work.

  45. Hey! This is my first visit to your blog! We are a group of volunteers and starting a new initiative in a
    community in the same niche. Your blog provided us useful
    information to work on. You have done a extraordinary
    job!

  46. My partner and I stumbled over here by a different web page and thought I may as well check things out. I like what I see so now i am following you. Look forward to looking into your web page for a second time.

  47. Just wish to say your article is as amazing. The clarity in your post is just cool and i can assume
    you’re an expert on this subject. Fine with your permission let me to
    grab your feed to keep updated with forthcoming post.
    Thanks a million and please continue the enjoyable work.

  48. What i do not understood is if truth be told how you’re no longer actually much more smartly-preferred
    than you might be now. You are so intelligent. You
    already know thus significantly relating to this subject, made me for my
    part consider it from so many varied angles. Its like women and men are
    not involved unless it’s something to do with Lady gaga!
    Your individual stuffs excellent. All the time care for it up!

Leave a Reply

Your email address will not be published. Required fields are marked *