线段树做了一遍 t了三个点可能是我太弱
代码如下
#include<iostream>@H_404_9@ #include<cstdio>@H_404_9@ #include<cctype>@H_404_9@ using@H_404_9@ namespace std; #define@H_404_9@ in = read()@H_404_9@ typedef long@H_404_9@ long@H_404_9@ ll; const@H_404_9@ ll size = 8000000@H_404_9@ + 10000@H_404_9@; #define@H_404_9@ left (rt<<1)@H_404_9@ #define@H_404_9@ right (rt<<1|1)@H_404_9@ #define@H_404_9@ lson l,mid,left@H_404_9@ #define@H_404_9@ rson mid+1,r,right@H_404_9@ #define@H_404_9@ mid ((l + r)>>1)@H_404_9@ ll n,m; ll tree[size]; inline ll read(){ ll num = 0@H_404_9@,f = 1@H_404_9@; char@H_404_9@ ch = getchar(); while@H_404_9@ (!isdigit(ch)){ if@H_404_9@(ch == '-'@H_404_9@) f = -1@H_404_9@; ch = getchar(); } while@H_404_9@ (isdigit(ch)){ num = num*10@H_404_9@ + ch - '0'@H_404_9@; ch = getchar(); } return@H_404_9@ num*f; } inline ll pushup(ll rt){ tree[rt]=min(tree[left],tree[right]);} void@H_404_9@ buildtree(ll l,ll r,ll rt){ if@H_404_9@ (l == r){ tree[rt] in@H_404_9@ ; return@H_404_9@;} buildtree(lson); buildtree(rson); pushup(rt); } ll query(ll from@H_404_9@,ll to,ll l,ll rt){ if@H_404_9@(from@H_404_9@ <= l && to >= r) return@H_404_9@ tree[rt]; ll ans = 0x7fffffff@H_404_9@; if@H_404_9@(from@H_404_9@ <= mid) ans = query(from@H_404_9@,to,lson); if@H_404_9@(to > mid) ans = min(ans,query(from@H_404_9@,rson)); return@H_404_9@ ans; } int@H_404_9@ main(){ n in@H_404_9@; m in@H_404_9@; buildtree(1@H_404_9@,n,1@H_404_9@); printf("0\n"@H_404_9@); ll t = 1@H_404_9@; for@H_404_9@(;;){ printf("%lld\n"@H_404_9@,query(1@H_404_9@,t,1@H_404_9@,1@H_404_9@)); t ++; if@H_404_9@(t == m) break@H_404_9@; } ll leftpoint = 1@H_404_9@,rightpoint = m; for@H_404_9@(int@H_404_9@ i=1@H_404_9@;i<=n-m;i++){ printf("%lld\n"@H_404_9@,query(leftpoint,rightpoint,1@H_404_9@)); leftpoint ++; rightpoint ++; } } //COYG@H_404_9@ @H_404_9@
后来改单调队列 于是题目变成了滑动窗口
慢慢滑 进队。。出队 队首肯定最小
代码如下
#include<iostream>@H_404_9@ #include<cstdio>@H_404_9@ #include<cctype>@H_404_9@ using namespace std; #define in = read()@H_404_9@ typedef long long ll; const ll size = 2000000@H_404_9@ + 100000@H_404_9@; ll n,m@H_404_9@; ll a[size]; ll q[size]@H_404_9@,p[size]; inline ll read@H_404_9@(){ ll num = 0@H_404_9@,f = 1@H_404_9@; char ch = getchar(); while@H_404_9@ (!isdigit(ch)){ if@H_404_9@(ch == '-'@H_404_9@) f = -1@H_404_9@; ch = getchar(); } while@H_404_9@ (isdigit(ch)){ num = num*10@H_404_9@ + ch - '0'@H_404_9@; ch = getchar(); } return@H_404_9@ num*f@H_404_9@; } int@H_404_9@ main(){ n in; m@H_404_9@ in; for@H_404_9@(int@H_404_9@ i=1@H_404_9@;i<=n;i++) a[i] in; printf@H_404_9@("0\n"@H_404_9@); /* 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("%d\n",ans); l ++; } */@H_404_9@ ll h = 1@H_404_9@,t = 0@H_404_9@; for@H_404_9@(int@H_404_9@ i=1@H_404_9@;i<n;i++){ while@H_404_9@(h <= t && q[t]@H_404_9@ >= a[i]) t --; q[++ t]@H_404_9@ = a[i]; p[t] = i; while@H_404_9@(p[h] <= i - m@H_404_9@) h ++; printf@H_404_9@("%d@H_404_9@\n"@H_404_9@,q[h]@H_404_9@); } } //COYG @H_404_9@
