程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4343 Interval query（倍增思想+貪心）

HDU 4343 Interval query（倍增思想+貪心）

編輯：關於C++

題意：給定n(n<=100000)個區間（左閉右開）和m(m<=100000)次詢問[l, r]，問所有在[l, r]區間內最多有多少個兩兩不相交的區間。，

思路：首先貪心的思想，去除掉包含其他區間的大區間，這樣做肯定不會影響結果。

然後對於所有區間，按照左端點升序排序，那麼由於這時所有區間不相互包含，他們的右端點也是遞增的。

那麼對於每個詢問，肯定是從左到右去盡可能多的區間，這個貪心容易想到。

對數據離散化，記錄從每個點開始的經過i個區間所達到的最近距離，這一步用到了倍增的思想，因為如果一個點一個點順序找，那麼時間復雜度和空間復雜度都無法承受。

具體來說，用f[i][j]記錄從i出發經過2^j個區間所達到的最近點，那麼可以得出遞推關系

f[i][j] = f[ f[i][j-1] ][j-1];

那麼對於每個詢問，我們將詢問ql,qr也離散化,只需找到從ql最多經過多少區間使得其不超過qr即可。

ps：半夜睡不著真是心痛，起來補題.........

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
#define pii (pair)
//#pragma comment(linker, /STACK:1024000000,1024000000) 
using namespace std;  

const int maxn = 100000 + 100;
const int INF = 0x3f3f3f3f;
int n, m;
struct Node {
	int l, r;
	bool operator < (const Node& A) const {
		if(l == A.l) return r > A.r;
		return l < A.l;
	}
} node[maxn]; 
int discret[2*maxn];
int fa[2*maxn][20];

int solve(int l, int r) {
	int ans = 0;
	for(int i = 16; i >= 0; i--) {
		int t = fa[l][i];
	//	cout << t << endl;
		if(t == r) return ans+(1<= 0; i--) {
		//	cout << node[i].l << endl;
			if(i == node[cnt2].l) {
				fa[i][0] = min(node[cnt2].r, fa[i+1][0]);
				while(i == node[cnt2].l) cnt2--;
			}
			else fa[i][0] = fa[node[cnt2+1].l][0];
		}
		for(int i = 1; i < 17; i++) {
			for(int j = 0; j < cnt; j++) if(fa[j][i-1] != INF) fa[j][i] = fa[ fa[j][i-1] ][i-1];
		}
		for(int i = 0; i < m; i++) {
			int l, r; scanf(%d%d, &l, &r);
			l = lower_bound(discret, discret+cnt, l) - discret;
			r = upper_bound(discret, discret+cnt, r) - discret - 1;
	//		cout << l <<   << r << endl;
			printf(%d
, solve(l, r));
		}
	//cout << fa[0][0] << endl;
	}
	return 0;
}