2 solutions

  • 0
    @ 2024-3-31 17:54:49

    提供五种写法供参考。

    优先队列写法(洛谷要开O2优化才能过)

    #include <iostream>
#include <queue>
#define int long long
#define endl '\n'
#define QAQ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
int a[N];
struct p{
    int x,id;
    bool operator <(const p&r) const//从小到大
    {
        if(x!=r.x)
            return x<r.x;
        else
            return id<r.id;
    }
    bool operator >(const p&r) const//从大到小
    {
        if(x!=r.x)
            return x>r.x;
        else
            return id>r.id;
    }
};
​
priority_queue <p> q;//从大到小的优先队列（后面的小于前面的（大根堆
priority_queue <p,vector<p>,greater<p>> q1;//从小到大的优先队列（后面的都要大于前面的（小根堆
void solve()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        q1.push((p){a[i],i});
        while(i-q1.top().id>=k)//如果已经超出窗口范围就删掉
            q1.pop();
        if(i>=k)//当i≥k,每移动一格就输出队头（最小值）
            cout<<q1.top().x<<' ';
    }
    cout<<endl;
    for(int i=1;i<=n;i++)//同理
    {
        q.push((p){a[i],i});
        while(i-q.top().id>=k)//如果已经超出窗口范围就删掉
            q.pop();
        if(i>=k)//当i≥k,每移动一格就输出队头（最大值）
            cout<<q.top().x<<' ';
    }
}
​
signed main()
{
    QAQ;
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    
    return 0;
}
​

    单调队列写法

    #include <iostream>
#include <cmath>
#include <deque>
#define int long long
#define endl '\n'
#define QAQ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
struct Num{
    int num,id;
}a[N];
deque <Num> deq;
​
void solve()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].num;
        a[i].id=i;
    }
    for(int i=1;i<=n;i++)
    {
        while((!deq.empty())&&a[i].num<=deq.back().num)//保持单调递增
            deq.pop_back();
        if((!deq.empty())&&i-deq.front().id+1>k)//超出窗口就删掉
            deq.pop_front();
        deq.push_back(a[i]);
        if(i>=k)
            cout<<deq.front().num<<' ';
    }
    cout<<endl;
    deq.clear();
    for(int i=1;i<=n;i++)
    {
        while((!deq.empty())&&a[i].num>=deq.back().num)//保持单调递减
            deq.pop_back();
        if((!deq.empty())&&i-deq.front().id+1>k)
            deq.pop_front();
        deq.push_back(a[i]);
        if(i>=k)
            cout<<deq.front().num<<' ';
    }
}
signed main()
{
    QAQ;
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    
}
​

    并查集写法（一位佬提供的

    #include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef pair<int,int> PII;
PII s[N];
int ans[N];
struct DSU{
  vector<int> f;
  DSU(int n):f(n){
    iota(f.begin(),f.end(),0);
  }
  int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);
  }
  void merge(int a,int b){
    int fa=find(a),fb = find(b);
    if(fa == fb)return ;
    f[fb] = fa;
  }
};
int main(){
  int n, k ;
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n >> k;
  for(int i=1;i<=n;i++){
    cin >> s[i].first;
    s[i].second = i; 
  }
  sort(s + 1,s + n + 1);
  {// 最小
    DSU ds(n + 2);
    for(int i = 1; i <= n ;i ++){
      int x = s[i].second,w = s[i].first;
      int l = max(x - k + 1,1),r = x;
      for(int j = ds.find(l);j <= r; j = ds.find(j)){
        ans[j] = w;
        ds.merge(j + 1,j);
      }
    }
    for(int i=1;i <= n - k + 1;i++){
      cout << ans[i] <<" \n"[i == n - k + 1];
    }
  }
  {// 最大
    DSU ds(n + 2);
    for(int i = n; i;i --){
      int x = s[i].second,w = s[i].first;
      int l = max(x - k + 1,1),r = x;
      for(int j = ds.find(l);j <= r; j = ds.find(j)){
        ans[j] = w;
        ds.merge(j + 1,j);
      }
    }
    for(int i=1;i <= n - k + 1;i++){
      cout << ans[i] <<" \n"[i == n - k + 1];
    }
  }
}

    线段树写法

    #include <iostream>
#include <cmath>
#define int long long
#define endl '\n'
#define QAQ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
struct Tree{
    int l,r,minn,maxx;
}tree[4*N];
int n,k,x,y;
int a[N];
void pre()//预处理最值
{
    for(int i=1;i<=4*N;i++)
    {
        tree[i].minn=1e18;
        tree[i].maxx=-1e18;
    }
}
void build(int root,int l,int r)//建立二叉树 储存每个窗口最大最小值
{
    tree[root].l=l;
    tree[root].r=r;
    if(l>r)
        return ;
    if(l==r)
    {
        tree[root].minn=a[l];
        tree[root].maxx=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    tree[root].minn=min(tree[root*2].minn,tree[root*2+1].minn);
    tree[root].maxx=max(tree[root*2].maxx,tree[root*2+1].maxx);
}
int query1(int root,int l,int r)//查询最小值
{
    if(l>r)
        return 0;
    if(x<=l&&y>=r)
        return tree[root].minn;
    int mid=(l+r)>>1;
    int sum=1e18;
    if(x<=mid)
        sum=min(sum,query1(root*2,l,mid));
    if(y>mid)
        sum=min(sum,query1(root*2+1,mid+1,r));
    return sum;
    
}
int query2(int root,int l,int r)//查询最大值
{
    if(l>r)
        return 0;
    if(x<=l&&y>=r)
        return tree[root].maxx;
    int mid=(l+r)>>1;
    int sum=-1e18;
    if(x<=mid)
        sum=max(sum,query2(root*2,l,mid));
    if(y>mid)
        sum=max(sum,query2(root*2+1,mid+1,r));
    return sum;
    
}
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    pre();
    build(1,1,n);
    for(int i=k;i<=n;i++)//最小
    {
        x=i-k+1;
        y=i;
        cout<<query1(1,1,n)<<' ';
    }
    cout<<endl;
    for(int i=k;i<=n;i++)//最大
    {
        x=i-k+1;
        y=i;
        cout<<query2(1,1,n)<<' ';
    }
}
​
signed main()
{
    QAQ;
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    
    return 0;
}
​

    ST表（Sparse Table，稀疏表）---解决RMQ问题

    #include <iostream>
#include <cmath>
#define int long long
#define endl '\n'
#define QAQ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
int f[25][N];
int n,k;
void pre1()//预处理存最小
{
    for(int i=1;i<=log2(n);i++)
    {
        for(int j=1;j<=n-(1<<i)+1;j++)
        {
            f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
        }
    }
}
int query1(int l,int r)//查询区间最小值
{
    int s=log2(r-l+1);
    return min(f[s][l],f[s][r-(1<<s)+1]);
}
void pre2()//预处理存最大
{
    for(int i=1;i<=log2(n);i++)
    {
        for(int j=1;j<=n-(1<<i)+1;j++)
        {
            f[i][j]=max(f[i-1][j],f[i-1][j+(1<<(i-1))]);
        }
    }
}
int query2(int l,int r)//查询区间最大值
{
    int s=log2(r-l+1);
    return max(f[s][l],f[s][r-(1<<s)+1]);
}
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>f[0][i];
    pre1();
    for(int i=1;i<=n-k+1;i++)
        cout<<query1(i,i+k-1)<<' ';
    cout<<endl;
    pre2();
    for(int i=1;i<=n-k+1;i++)
        cout<<query2(i,i+k-1)<<' ';
    
}
​
signed main()
{
    QAQ;
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    
    return 0;
}

    线段树写法在oj上MLE了但是在落谷过了的。

    • 0
      @ 2022-2-11 15:54:08

      双向单调队列

      #include <bits/stdc++.h>
using namespace std;
struct sd{
	int num,val;
}rr;
deque<sd>d1;//单增
deque<sd>d2;//单减
int add[3][1000005];
int main(){
	int n,m,x,cnt=1;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		rr.num=i;rr.val=x;
		while(!d1.empty()&&x>=d1.back().val){
			d1.pop_back();
		}
		while(!d2.empty()&&x<=d2.back().val){
			d2.pop_back();
		}
		d1.push_back(rr);
		d2.push_back(rr);
		while(i-m>=d1.front().num&&!d1.empty()){
			d1.pop_front();
		}
		while(i-m>=d2.front().num&&!d2.empty()){
			d2.pop_front();
		}
		if(i>=m){
			add[0][cnt]=d1.front().val;
			add[1][cnt]=d2.front().val;
			cnt++;
		}
	}
	for(int i=1;i<cnt;i++){
		printf("%d ",add[1][i]);
	}
	printf("\n");
	for(int i=1;i<cnt;i++){
		printf("%d ",add[0][i]);
	}
	return 0;
}
      • 1

      【基础】滑动窗口

      Information

      ID
      1108
      Time
      1000ms
      Memory
      16MiB
      Difficulty
      6
      Tags
      # Submissions
      20
      Accepted
      10
      Uploaded By
      1. About
      2. Contact Us
      3. Privacy
      4. Terms of Service
      5. Copyright Complaint
      6. Language
      7. Legacy mode
      8. Theme
      2. 蜀ICP备2021003932号-1
      3. Worker 0, 42ms
      4. Powered by Hydro v4.18.0 Community