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

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

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

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


Login *


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