【数据结构】[luoguP1440]求m区间内的最小值

题目

线段树做了一遍 t了三个点可能是我太弱
代码如下

#include<iostream> #include<cstdio> #include<cctype> using namespace std; #define in = read() typedef long long ll; const ll size = 8000000 + 10000; #define left (rt<<1) #define right (rt<<1|1) #define lson l,mid,left #define rson mid+1,r,right #define mid ((l + r)>>1) ll n,m; ll tree[size]; inline ll read(){ ll num = 0,f = 1; char ch = getchar(); while (!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)){ num = num*10 + ch - '0'; ch = getchar(); } return num*f; } inline ll pushup(ll rt){ tree[rt]=min(tree[left],tree[right]);} void buildtree(ll l,ll r,ll rt){ if (l == r){ tree[rt] in ; return;} buildtree(lson); buildtree(rson); pushup(rt); } ll query(ll from,ll to,ll l,ll rt){ if(from <= l && to >= r) return tree[rt]; ll ans = 0x7fffffff; if(from <= mid) ans = query(from,to,lson); if(to > mid) ans = min(ans,query(from,rson)); return ans; } int main(){ n in; m in; buildtree(1,n,1); printf("0n"); ll t = 1; for(;;){ printf("%lldn",query(1,t,1,1)); t ++; if(t == m) break; } ll leftpoint = 1,rightpoint = m; for(int i=1;i<=n-m;i++){ printf("%lldn",query(leftpoint,rightpoint,1)); leftpoint ++; rightpoint ++; } } //COYG 

后来改单调队列 于是题目变成了滑动窗口
慢慢滑 进队。。出队 队首肯定最小
代码如下

#include<iostream> #include<cstdio> #include<cctype> using namespace std; #define in = read() typedef long long ll; const ll size = 2000000 + 100000; ll n,m; ll a[size]; ll q[size],p[size]; inline ll read(){ ll num = 0,f = 1; char ch = getchar(); while (!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)){ num = num*10 + ch - '0'; ch = getchar(); } return num*f; } int main(){ n in; m in; for(int i=1;i<=n;i++) a[i] in; printf("0n"); /* ll l = 1; for(int i=1;i<m;i++){ ll ans = 0x7fffffff; for(int j=1;j<=l;j++) if(a[j] < ans) ans = a[j]; printf("%dn",ans); l ++; } */ ll h = 1,t = 0; for(int i=1;i<n;i++){ while(h <= t && q[t] >= a[i]) t --; q[++ t] = a[i]; p[t] = i; while(p[h] <= i - m) h ++; printf("%dn",q[h]); } } //COYG