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