[SPOJ] DQUERY - D-query (歸併樹)
題目連結:http://www.spoj.com/problems/DQUERY/
本題的另外一種解法,構造方式與上一種不同,這裡的構造方式是將每個相同的數字由左至右連邊(如圖)
那這樣對於一個詢問$[L, R]$,就變成詢問$[L,R]$中大於$R$的數有多少個,因為每個數字最終必須往外伸出去。
而詢問$[L,R]$中大於$R$的數有多少個,其實可以用一種跟線段樹很像的做法做,節點存的是排序好的$[L,R]$,那詢問就直接二分搜就好,不過建立的過程退化成$O(n log n)$查詢則變成$O( n log^2 n)$
本題的另外一種解法,構造方式與上一種不同,這裡的構造方式是將每個相同的數字由左至右連邊(如圖)
那這樣對於一個詢問$[L, R]$,就變成詢問$[L,R]$中大於$R$的數有多少個,因為每個數字最終必須往外伸出去。
而詢問$[L,R]$中大於$R$的數有多少個,其實可以用一種跟線段樹很像的做法做,節點存的是排序好的$[L,R]$,那詢問就直接二分搜就好,不過建立的過程退化成$O(n log n)$查詢則變成$O( n log^2 n)$
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
const int N = 30000 + 5;
const int INF = 1<<30;
class LiSan{
private:
vector<int> v;
public:
void init(){v.clear();}
void insert(int x){v.PB(x);}
int size(){return v.size();}
void done(){
sort(ALL(v));
v.resize(distance(v.begin(), unique(ALL(v))));
}
int get(int x){
return distance(v.begin(), lower_bound(ALL(v), x));
}
} lisan;
class SegTree{
private:
vector<int> nodes[4*N];
int size;
inline int lc(int x){return (x<<1)+1;}
inline int rc(int x){return (x<<1)+2;}
void build(int l, int r, int id, int arr[]){
if(r-l==1){
nodes[id].PB(arr[l]);
return;
}
int mid = (l+r)>>1;
build(l, mid, lc(id), arr);
build(mid, r, rc(id), arr);
int _=0;
for(int i=0;i<(int)nodes[lc(id)].size();++i){
while(_ < (int)nodes[rc(id)].size() and \
nodes[rc(id)][_] < nodes[lc(id)][i]){
nodes[id].PB(nodes[rc(id)][_++]);
}
nodes[id].PB(nodes[lc(id)][i]);
}
while(_ < (int)nodes[rc(id)].size()) nodes[id].PB(nodes[rc(id)][_++]);
}
int query(int ql, int qr, int l, int r, int id, int x){
if(qr <= l or r <= ql) return 0;
if(ql <= l and r <= qr)
return distance(lower_bound(ALL(nodes[id]), x), nodes[id].end());
int mid=(l+r)>>1;
int ll = query(ql, qr, l, mid, lc(id), x);
int rr = query(ql, qr, mid, r, rc(id), x);
return ll+rr;
}
public:
void build(int n, int arr[]){
size=n;
build(0, n, 0, arr);
}
int query(int l, int r, int x){
return query(l, r, 0, size, 0, x);
}
} seg;
int arr[N], pos[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n; cin>>n;
fill(pos, pos+n, INF);
for(int i=0;i<n;i++){
cin>>arr[i];
lisan.insert(arr[i]);
}
lisan.done();
for(int i=n-1;i>=0;--i){
int x = lisan.get(arr[i]);
arr[i] = pos[x];
pos[x]=i;
}
seg.build(n, arr);
int q; cin>>q;
while(q--){
int l, r; cin>>l>>r;
cout<<seg.query(l-1, r, r)<<'\n';
}
return 0;
}
留言
張貼留言