2 条题解

  • 1
    @ 2024-5-19 10:38:36

    这什么数据,暴力拿全分???

    #include <bits/stdc++.h>
    using namespace std;
    struct node{
      int x,y;  
    }a[100005];
    bool cmp(node l,node v){
        return l.x<v.x;
    }
    int main(){
        int m,n,t,k;
        cin>>m>>n;
        for(int i=1;i<=m;i++){
            cin>>a[i].x;
            a[i].y=i;   
        }
        sort(a+1,a+1+m,cmp);
        for(int i=1;i<=n;i++){
            cin>>t>>k;
            for(int j=1;j<=m;j++){
                if(a[j].y>=t&&a[j].y<=k){
                    cout<<a[j].x<<" ";
                    break;
                }
            }
        }
        return 0;
    }
    
    • 0
      @ 2024-5-17 17:18:52

      题目大意: n 个查询,每次询问一个区间 [L,R] 中 ai 的最大值

      思路

      标准的RMQ问题,求区间最大值,用ST表维护

      参考代码
          int log2m = log2(m);
          for (int j = 1; j <= log2m; ++j)
              for (int i = 1; i <= n - (1 << j) + 1; ++i)
                  f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
      
      • 1

      信息

      ID
      740
      时间
      1000ms
      内存
      256MiB
      难度
      2
      标签
      (无)
      递交数
      46
      已通过
      30
      上传者