[www.luogu.org] P1972 HH's necklace *Solution*
A problem suitable for BIT, the Binary Indexed Tree (Estimated Difficulty: above Senior, NOIP)
"Sky Gate":http://www.luogu.org/problem/show?pid=1972#
Given N, N integers and M queries on the number of different numbers between interval [l_i,r_i], answer each query. Input: N A_1 A_2 ... A_N M l_1 r_1 l_2 r_2 ... l_M r_M Output: M lines in total , answering M queries in order with an integer every line Sample Input: 6 1 2 3 4 3 5 3 1 2 3 5 2 6 Sample Output: 2 2 4 Explanations: There are two distinct numbers (1 and 2) in interval [1,2]; two distinct numbers (3 and 4) in interval [3,5]; and four distinct numbers (2, 3, 4 and 5)in interval [2,6] For all 5 testcases: 1<=N<=50000, 0<=A_i<=1000000 (1<=i<=N), 1<=M<=200000, 1<=l_i<=r_i<=N (1<=i<=M), all numbers mentioned are non-negative integers
First of all, it is very important to sort all N numbers, and order them with 1 to N positive integers representing their value. (We call it "discretization")
Disconnect all the queries first and sort by their intervals.
Use a BIT, and a linking chart pointing to the next position with the same number.
Only through GDB could you realize how interesting the code could be...
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<cctype> #include<string> #include<vector> #define hk 60100 #define lb(x) ((x)&(-(x))) using namespace std; inline void getint(int&x){ char c;for(c=getchar();c>57||c<48;c=getchar()); for(x=0;c<58&&c>47;c=getchar())x=x*10+c-48; }typedef struct pt{int dig,ord;}; typedef struct qu{int l,r,o,ans;}; typedef struct BIT{ int n,c[hk];void add(int x,int d){while(x<=n){c[x]+=d;x+=lb(x);}} int que(int x){int r=0;while(x){r+=c[x];x-=lb(x);}return r;} };int n,i,b[hk],m,j,nxt[hk],p[hk];pt a[hk];qu q[hk<<2];BIT bit; bool jsy(pt x,pt y){return x.dig<y.dig||x.dig==y.dig&&x.ord<y.ord;} bool hgs(pt x,pt y){return x.ord<y.ord||x.ord==y.ord&&x.dig<y.dig;} bool ckh(qu x,qu y){return x.l<y.l||x.l==y.l&&x.r<y.r||x.l==y.l&&x.r==y.r&&x.o<y.o;} bool ccb(qu x,qu y){return x.o<y.o;} int main(){ getint(n);for(i=1;i<=n;i++){getint(a[i].dig);a[i].ord=i;} sort(a+1,a+n+1,jsy);b[1]=1;for(i=2;i<=n;i++)b[i]=b[i-1]+(a[i].dig>a[i-1].dig?1:0); for(i=1;i<=n;i++)a[i].dig=b[i];sort(a+1,a+n+1,hgs);bit.n=n; for(i=n;i>0;i--){nxt[i]=p[a[i].dig];p[a[i].dig]=i;} for(i=1;i<=n;i++)if(p[i])bit.add(p[i],1); getint(m);for(i=1;i<=m;i++){getint(q[i].l);getint(q[i].r);q[i].o=i;} sort(q+1,q+m+1,ckh);j=1;for(i=1;i<=m;i++){ while(j<q[i].l){if(nxt[j])bit.add(nxt[j],1);j++;} q[i].ans=bit.que(q[i].r)-bit.que(q[i].l-1); }sort(q+1,q+m+1,ccb);for(i=1;i<=m;i++)printf("%d\n",q[i].ans);return 0; }
I used BIT for the first time, having learnt a lot.
However there is a special solution called "Mo Dui", which could also solve it.
Waiting for someone's explanation because I'm a WEAK DISH...
If you have better solution, please show your solution through comments, and I'll take it seriously.
(Comments are welcomed and it is recommended that you reply in English.)
Mon, 22 Feb 2016 01:09:43 +0800
你这压行压得也太难看了吧。。
Sat, 29 Jun 2019 16:20:56 +0800
backup and restore windows 10 how to backup windows 10 os How do I make backups for Windows 10 You can learn by visiting this website very easily.
Fri, 31 Jul 2020 11:50:05 +0800
Positive site. where did u come up with the information on this posting? I'm pleased I discovered it though. ill be checking back soon to find out what additional posts you include.
Fri, 31 Jul 2020 14:09:20 +0800
Thanks for sharing this useful info..
Fri, 31 Jul 2020 23:02:03 +0800
Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts.
Sat, 01 Aug 2020 18:16:56 +0800
Great survey. I'm sure you're getting a great response.
Sat, 01 Aug 2020 23:04:04 +0800
Thanks for sharing nice information with us. i like your post and all you share with us is uptodate and quite informative. i would like to bookmark the page so i can come here again to read you. as you have done a wonderful job.
Sun, 02 Aug 2020 13:27:11 +0800
Nice to read your article! I am looking forward to sharing your adventures and experiences.
Thu, 06 Aug 2020 11:43:01 +0800
These are some great tools that i definitely use for SEO work. This is a great list to use in the future..
Mon, 10 Aug 2020 23:00:02 +0800
Your blog provided us with valuable information to work with. Each & every tips of your post are awesome. Thanks a lot for sharing. Keep blogging.
Tue, 11 Aug 2020 11:50:25 +0800
I think this is an informative post and it is very useful and knowledgeable. therefore. I would like to thank you for the efforts you have made in writing this article.
Tue, 11 Aug 2020 16:22:01 +0800
Great survey. I'm sure you're getting a great response.
Sun, 13 Sep 2020 00:19:29 +0800
Most of the time I don’t make comments on websites, but I'd like to say that this article really forced me to do so. Really nice post!
Sun, 31 Jan 2021 18:43:23 +0800
Thank you very much for this great post.
Fri, 23 Apr 2021 13:07:39 +0800
The Girls here will give all sorts of sexual fun and enjoyment.
<a href="https://www.escortsingoa.net/"> Goa Escorts</a>
Sun, 02 May 2021 16:05:06 +0800
A very awesome blog post. We are really grateful for your blog post. You will find a lot of approaches after visiting your post.
Sun, 02 May 2021 16:06:32 +0800
I like this post. And I guess that they having fun reading this post. they shall take a good site to make a piece of information. thanks for sharing it with me.
Mon, 10 May 2021 22:50:31 +0800
Excellent article. Very interesting to read. I really love to read such a nice article. Thanks! keep rocking.
Sat, 17 Jul 2021 14:48:08 +0800
The Hot and sexy Girls here are to give all sorts of fun and enjoyment here.
Tue, 14 Sep 2021 15:41:20 +0800
rtj ruj to jtrj jkm,
Wed, 03 Nov 2021 14:53:43 +0800
A debt of gratitude is in order for imparting decent data to us. I like your post and all you share with us is forward-thinking and very enlightening, I might want to bookmark the page so I can come here again to understand you, as you have worked effectively
Tue, 01 Feb 2022 21:46:08 +0800
I’m prompted while using the surpassing in addition to preachy checklist you give in such very little timing. 메이저사이트
Mon, 28 Mar 2022 04:42:35 +0800
The comments here were just as instructive as your post CBT
Fri, 27 May 2022 23:42:06 +0800
I’ve been surfing online greater than three hours these days, but I by no means found any interesting article like yours. It¡¦s beautiful value sufficient for me. In my view, if all website owners and bloggers made excellent content as you probably did, the net will likely be a lot more helpful than ever before. 먹튀검증
Sat, 04 Jun 2022 23:58:21 +0800
Very interesting points you have noted , regards for putting up. 腳架
Tue, 14 Jun 2022 03:41:12 +0800
Good day. i am doing research right now and your blog really helped me. macbook回收
Sat, 20 Aug 2022 02:16:56 +0800
The NJMCDirect online portal has eventually replaced the old queuing system. Whenever once violates the traffic or parking rules. njmcdirect.com The traffic officers provide a traffic ticket stating your offenses and fine to pay. These compel you to pay the fines within the stated time frame. Violators need to visit the court and queue for long hours. However, the New Jersey Meadowlands Commission
Mon, 03 Oct 2022 21:27:55 +0800
hello I was very impressed with the setup you used with this website. I use blogs my self so good job. definatly adding to bookmarks. 攝影器材
Sat, 05 Nov 2022 03:00:43 +0800
I’m not sure exactly how I discovered your blog because I had been researching information on Real Estate in Altamonte Springs, FL, but anyway, I have had a pleasant time reading it, keep it up! 바카라사이트
Sat, 19 Nov 2022 04:38:38 +0800
There are a few interesting points in time in this posting but I do not determine if I see these people center to heart. There may be some validity but Let me take hold opinion until I take a look at it further. Very good write-up , thanks and we want much more! Included in FeedBurner likewise 온라인바카라
Fri, 30 Dec 2022 19:22:04 +0800
Thank you for the information you provide, it helped me a lot.
Fri, 30 Dec 2022 19:22:49 +0800
Very interesting blog. A lot of blogs I see these days don't really provide anything that I'm interested in, but I'm most definitely interested in this one. Just thought that I would post
Sat, 18 Feb 2023 15:20:37 +0800
I have been talking about this subject a lot lately with my father so hopefully this will get him to see my point of view. Fingers crossed!
Sat, 18 Feb 2023 15:21:34 +0800
This is exceptionally engaging, however , it is vital that will mouse tap on the association Thanks for the valuable information and insights you have so provided here.
Sat, 18 Feb 2023 15:22:18 +0800
Positive site, where did u come up with the information on this posting? I'm pleased I discovered it though, ill be checking back soon to find out what additional posts you include
Sat, 18 Feb 2023 15:22:56 +0800
This is highly informatics, crisp and clear. I think that everything has been described in systematic manner so that reader could get maximum information and learn many things.
Thu, 02 Mar 2023 12:53:23 +0800
We are the best escorts service provider in Dehradun. We provide you with escorts who are attractive and confident, with a beautiful charming personality. We have an assorted team of girls who would be willing to serve your needs. Our Dehradun Escorts services are discreet, trustworthy and professional.
Thu, 02 Mar 2023 12:54:59 +0800
Welcome to one of the top escort service in Dehradun. Escorts you can trust and rely on are hard to find these days, but with us you're in good hands.
Sun, 23 Apr 2023 10:29:15 +0800
Thanks you!
Xây nhà trọn gói tại tphcm Thi cong alu Giá thi công nhà khung thép Sua nha gia re Giam sat cong trinh Xay nha gia re WinconsSat, 28 Sep 2024 22:00:49 +0800
Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with extra information? It is extremely helpful for me.Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info. estadísticas de vasco da gama contra athletico paranaense
Mon, 30 Sep 2024 17:59:33 +0800
I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article...When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your.Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome!Thanks for sharing the such information with us to read this...We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work. oil for hemorrhoids
Fri, 25 Oct 2024 03:14:14 +0800
This is just the information I am finding everywhere. Thanks for your blog, I just subscribe your blog. This is a nice blog..This is really nice to read..informative post is very good to read..thanks a lot! In Mold Labeling
Thu, 31 Oct 2024 03:34:31 +0800
I would like to say that this blog really convinced me to do it! Thanks, very good post.I’ve a undertaking that I am simply now operating on, and I have been at the look out for such info.It was wondering if I could use this write-up on my other website, I will link it back to your website though.Great Thanks. Acrylate Leveling Agent For Ink
Tue, 05 Nov 2024 18:05:28 +0800
I love seeing blog that understand the value of providing a quality resource for free.We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work.i never know the use of adobe shadow until i saw this post. thank you for this! this is very helpful. deliverance ministry
Fri, 08 Nov 2024 23:21:21 +0800
Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign.Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!!! titaniuminvest
Sat, 09 Nov 2024 04:27:35 +0800
Positive site, where did u come up with the information on this posting? I'm pleased I discovered it though, ill be checking back soon to find out what additional posts you include.Thank you because you have been willing to share information with us. we will always appreciate all you have done here because I know you are very concerned with our. lebaran idul fitri 2025
Sat, 09 Nov 2024 23:34:06 +0800
Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info.This site seems to get a good amount of visitors. Ariana Grande Phone Number 2024
Sun, 17 Nov 2024 00:38:02 +0800
I love seeing blog that understand the value of providing a quality resource for free.We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work.i never know the use of adobe shadow until i saw this post. thank you for this! this is very helpful. fintechzoom.com
Tue, 19 Nov 2024 03:43:34 +0800
Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!..Hello, this weekend is good for me, since this time i am reading this enormous informative article here at my home. Chuan Park
Sun, 24 Nov 2024 02:14:22 +0800
I havent any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us.This particular is usually apparently essential and moreover outstanding truth along with for sure fair-minded and moreover admittedly useful My business is looking to find in advance designed for this specific useful stuffs… NEW YORK FAKE ID
Mon, 25 Nov 2024 05:46:07 +0800
I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You.This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. instytutum firmagic
Fri, 29 Nov 2024 23:36:20 +0800
I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article.Thank you because you have been willing to share information with us. we will always appreciate all you have done here because I know you are very concerned with our. convert m to inches
Thu, 05 Dec 2024 18:13:57 +0800
Admiring the time and effort you put into your blog and detailed information you offer!..Great post, and great website. Thanks for the information! Thanks for all your help and wishing you all the success in your business. Solar Generator For House
Fri, 13 Dec 2024 23:40:40 +0800
We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work.Really a great addition. I have read this marvelous post. Thanks for sharing information about it. I really like that. Thanks so lot for your convene. Solar Panel For Lithium Ion Batteries