[www.luogu.org] P1972 HH's necklace Solution

酱油 posted @ Tue, 16 Feb 2016 21:08:37 +0800 in OI life with tags solution , 2727 readers

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.)

Comments (66)

[Reply]

orz hhw said:
Mon, 22 Feb 2016 01:09:43 +0800

你这压行压得也太难看了吧。。

[Reply]

backup and restore w said:
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.

[Reply]

made a post said:
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.

[Reply]

my website said:
Fri, 31 Jul 2020 14:09:20 +0800

Thanks for sharing this useful info..

[Reply]

over here said:
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.

[Reply]

read the article said:
Sat, 01 Aug 2020 18:16:56 +0800

Great survey. I'm sure you're getting a great response.

[Reply]

see this here said:
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.

[Reply]

talking to said:
Sun, 02 Aug 2020 13:27:11 +0800

Nice to read your article! I am looking forward to sharing your adventures and experiences.

[Reply]

this link said:
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..

[Reply]

go to the website said:
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.

[Reply]

on front page said:
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.

[Reply]

helpful resources said:
Tue, 11 Aug 2020 16:22:01 +0800

Great survey. I'm sure you're getting a great response.

[Reply]

quầy kệ siêu thị said:
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!

[Reply]

free iptv said:
Sun, 31 Jan 2021 18:43:23 +0800

Thank you very much for this great post.

[Reply]

Anamika SHukla said:
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>

[Reply]

Goa Escorts said:
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.

[Reply]

Escorts service in G said:
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.

[Reply]

Delhi Escorts said:
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.

[Reply]

Delhi Escorts said:
Sat, 17 Jul 2021 14:48:08 +0800

The Hot and sexy Girls here are to give all sorts of fun and enjoyment here.

[Reply]

Chennai Escort serv said:
Tue, 14 Sep 2021 15:41:20 +0800

rtj ruj to jtrj jkm,

[Reply]

Bangalore Escorts said:
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

[Reply]

AAA said:
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. 메이저사이트

[Reply]

AAA said:
Mon, 28 Mar 2022 04:42:35 +0800

The comments here were just as instructive as your post CBT

[Reply]

AAA said:
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. 먹튀검증

[Reply]

AAA said:
Sat, 04 Jun 2022 23:58:21 +0800

Very interesting points you have noted , regards for putting up. 腳架

[Reply]

AAA said:
Tue, 14 Jun 2022 03:41:12 +0800

Good day. i am doing research right now and your blog really helped me. macbook回收

[Reply]

njmcdirect.com said:
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

[Reply]

meidir said:
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. 攝影器材

[Reply]

meidir said:
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! 바카라사이트

[Reply]

meidir said:
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 온라인바카라

[Reply]

Escorts Service in M said:
Fri, 30 Dec 2022 19:22:04 +0800

Thank you for the information you provide, it helped me a lot.

[Reply]

Escorts Service in A said:
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

[Reply]

Low Rate Call Girls said:
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!

[Reply]

Patna Escort Service said:
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.

[Reply]

Escort in Kanpur said:
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

[Reply]

Escort in Connaught said:
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.

[Reply]

shivani02 said:
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.

[Reply]

shivani02 said:
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.

Mussoorie Escorts || Escorts in Rishikesh || Haridwar Escorts Service || Escorts Service in Roorkee ||

[Reply]

SUA NHA GIA RE said:
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 Wincons

[Reply]

seo said:
Sat, 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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
Sun, 17 Nov 2024 00:38:02 +0800

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
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

[Reply]

seo said:
Tue, 07 Jan 2025 17:51:21 +0800

[Reply]

seo said:
Fri, 10 Jan 2025 21:17:29 +0800

Wow! Such an amazing and helpful post this is. I really really love it. It's so good and so awesome. I am just amazed. I hope that you continue to do your work like this in the future alsoReally i am impressed from this post....the person who create this post it was a great human. Automatic Meat Slicer Machine

[Reply]

seo said:
Sun, 19 Jan 2025 13:20:31 +0800

[Reply]

seo said:
Wed, 19 Feb 2025 05:12:32 +0800

Excellent article. Very interesting to read. I really love to read such a nice article. Thanks! keep rocking.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. Arina East Residences

[Reply]

seo said:
Sat, 01 Mar 2025 18:41:06 +0800

I have read all the comments and suggestions posted by the visitors for this article are very fine,We will wait for your next article so only.Thanks!I guess I am not the only one having all the enjoyment here keep up the good work. Hey what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you. market global ai

[Reply]

seo said:
Thu, 20 Mar 2025 20:32:36 +0800

Nice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post.Anyways I am here now and could just like to say thank for a tremendous post and a all round entertaining website. Please do keep up the great work. Bitcoineer

[Reply]

seo said:
Sun, 23 Mar 2025 06:53:03 +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.Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place.. The Continuum

[Reply]

seo said:
Mon, 31 Mar 2025 03:54:27 +0800

Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info.I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business. Artisan 8

[Reply]

seo said:
Fri, 04 Apr 2025 04:45:47 +0800

Quando utilizzi un servizio autentico, sarai in grado di fornire istruzioni, condividere materiali e scegliere lo stile di formattazione. Questa è la mia prima visita qui. Dai tonnellate di commenti sui tuoi articoli, immagino di non essere l'unico a divertirsi qui! Mi chiedevo se potessi usare questo articolo sul mio altro sito web, ma lo collegherò al tuo sito web. Grazie mille. brae soul color

[Reply]

seo said:
Fri, 04 Apr 2025 04:51:51 +0800

To jest tak wspaniałe źródło, które udostępniasz i rozdajesz je za darmo. Uwielbiam oglądać blogi, które rozumieją wartość dostarczania wysokiej jakości zasobu za darmo. Przyznaję, że nie byłem na tej stronie internetowej od dłuższego czasu... ale to była kolejna radość zobaczyć To jest tak ważny temat i ignorowany przez tak wielu, nawet profesjonalistów. Dziękuję za pomoc w uświadamianiu ludziom możliwych problemów. rare paris

[Reply]

seo said:
Mon, 28 Apr 2025 11:49:31 +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.A very awesome blog post. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. The Sen

[Reply]

seo said:
Mon, 05 May 2025 03:01:18 +0800

Hey, was für einen brillanten Beitrag ich gefunden habe, und glauben Sie mir, ich habe die ganze letzte Woche nach einem ähnlichen Beitrag gesucht und bin kaum darauf gestoßen. Vielen Dank, ich werde nach weiteren Beiträgen von Ihnen Ausschau halten. Es ist aufregend, wenn Ihre Website oder Ihr Blog zum ersten Mal online geht. Bis Sie erkennen, dass niemand außer Ihnen und Ihren Angehörigen da ist. Klaviertransport Wien

Soy Sauce's Blog

[www.luogu.org] P1972 HH's necklace Solution

酱油

Categories

Bulletin

New Comments

New Messages

Links

RSS

Meta

Calendar

Counter

May
Sun	Mon	Tue	Wed	Thu	Fri	Sat
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Soy Sauce's Blog

[www.luogu.org] P1972 HH's necklace *Solution*

酱油

Categories

Bulletin

New Comments

New Messages

Links

RSS

Meta

Calendar

Counter

[www.luogu.org] P1972 HH's necklace Solution