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

酱油 posted @ Tue, 16 Feb 2016 21:08:37 +0800 in OI life with tags solution , 2559 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.)

Small_feed Comments (39)
1
[Reply]
Avatar_small
orz hhw said:
Mon, 22 Feb 2016 01:09:43 +0800

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

2
[Reply]
Avatar_small
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.

3
[Reply]
Avatar_small
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.

4
[Reply]
Avatar_small
my website said:
Fri, 31 Jul 2020 14:09:20 +0800

Thanks for sharing this useful info..

5
[Reply]
Avatar_small
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.

6
[Reply]
Avatar_small
read the article said:
Sat, 01 Aug 2020 18:16:56 +0800

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

7
[Reply]
Avatar_small
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.

8
[Reply]
Avatar_small
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.

9
[Reply]
Avatar_small
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..

10
[Reply]
Avatar_small
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.

11
[Reply]
Avatar_small
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.

12
[Reply]
Avatar_small
helpful resources said:
Tue, 11 Aug 2020 16:22:01 +0800

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

13
[Reply]
Avatar_small
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!

14
[Reply]
Avatar_small
free iptv said:
Sun, 31 Jan 2021 18:43:23 +0800

Thank you very much for this great post.

15
[Reply]
Avatar_small
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>

16
[Reply]
Avatar_small
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.

17
[Reply]
Avatar_small
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.

18
[Reply]
Avatar_small
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.

19
[Reply]
Avatar_small
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.

21
[Reply]
Avatar_small
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

22
[Reply]
Avatar_small
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. 메이저사이트

23
[Reply]
Avatar_small
AAA said:
Mon, 28 Mar 2022 04:42:35 +0800

The comments here were just as instructive as your post CBT

24
[Reply]
Avatar_small
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. 먹튀검증

25
[Reply]
Avatar_small
AAA said:
Sat, 04 Jun 2022 23:58:21 +0800

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

26
[Reply]
Avatar_small
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回收

27
[Reply]
Avatar_small
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

28
[Reply]
Avatar_small
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. 攝影器材

29
[Reply]
Avatar_small
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! 바카라사이트

30
[Reply]
Avatar_small
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 온라인바카라

31
[Reply]
Avatar_small
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.

32
[Reply]
Avatar_small
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

33
[Reply]
Avatar_small
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!

34
[Reply]
Avatar_small
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.

35
[Reply]
Avatar_small
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

36
[Reply]
Avatar_small
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.

37
[Reply]
Avatar_small
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.  

38
[Reply]
Avatar_small
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. 


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter