本文共 1375 字，大约阅读时间需要 4 分钟。
题意：
最少需要多少个区间能完全覆盖整个区间[1,n]
分析：
dp[i]表示覆盖[1,i]最少需要的区间数，对于区间[a,b],dp[b]=min(dp[a...b-1])+1;用线段树来维护区间最小值。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef pair PII;typedef long long ll;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define All 1,N,1#define N 50010#define read freopen("in.txt", "r", stdin)const ll INFll = 0x3f3f3f3f3f3f3f3fLL;const int INF= 0x7ffffff;const int mod = 1000000007;struct seg{ int s,e;}g[N*10];int minv[N*4],n,q;void pushup(int rt){ minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);}void build(int l,int r,int rt){ if(l==r){ if(l==1)minv[rt]=0; else minv[rt]=INF; return; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt);}void update(int p,int l,int r,int rt,int v){ if(l==r){ minv[rt]=min(minv[rt],v); return; } int m=(l+r)>>1; if(p<=m)update(p,lson,v); else update(p,rson,v); pushup(rt);}int query(int L,int R,int l,int r,int rt){ if(l>=L&&r<=R) return minv[rt]; int tmp=INF; int m=(l+r)>>1; if(L<=m)tmp=min(tmp,query(L,R,lson)); if(R>m)tmp=min(tmp,query(L,R,rson)); return tmp;}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); for(int i=0;i
转载于:https://www.cnblogs.com/zsf123/p/4909767.html